又是非常好的树链剖分
题意
有n个点的树，有m次操作
操作是在x-y的链上的每一个点，放入一个数字z
然后让你输出每个点出现次数最多的数是什么
首先将其看成一个序列操作（也就是树链拆成的一条条链）
要在 u 到 v 之间加上 数字z 那么就 d[u].pb(z) d[v+1].pb(z) （有点像差分 但是和差分又不一样）
并且记录一个maxz
然后开一个线段树 1 到maxz
从该序列的头开始遍历 （头不可能有 -z ）
for(auto v:d[i]) 如果 v大于0 在线段树v位置加一 表示v数字加一个 否则在-v 减一 表示去掉一个
然后就是最大值线段树 答案就是最大值的下标 注意可以加一个maxnum 递归返回其结果 （具体实现见线段树！！！！）
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) typedef pair<int,int>pii; ////////////////////////////////// const int N=1e5+10; int t[N<<2],maxnum[N<<2],pos,head[N<<1],n,m; void up(int pos) { if(t[pos<<1]<t[pos<<1|1])maxnum[pos]=maxnum[pos<<1|1]; else maxnum[pos]=maxnum[pos<<1]; t[pos]=max(t[pos<<1],t[pos<<1|1]); } void build(int l,int r,int pos) { if(l==r){t[pos]=0;maxnum[pos]=l;return; } int m=(l+r)>>1; build(lson);build(rson);up(pos); } void upnode(int x,int v,int l,int r,int pos) { if(l==r){t[pos]+=v;return;} int m=(l+r)>>1; if(x<=m)upnode(x,v,lson); else upnode(x,v,rson); up(pos); } int cnt,id[N],fa[N],top[N],siz[N],son[N],dep[N],ans[N],a,b,c; vector<int>d[N]; struct Edge { int to,nex; }edge[N<<1]; void add(int a,int b) { edge[++pos]=(Edge){b,head[a]}; head[a]=pos; } void dfs1(int x,int f) { fa[x]=f;dep[x]=dep[f]+1;siz[x]=1;son[x]=0; for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to;if(v==f)continue; dfs1(v,x);siz[x]+=siz[v]; if(siz[son[x]]<siz[v])son[x]=v; } } void dfs2(int x,int topf) { top[x]=topf;id[x]=++cnt; if(son[x])dfs2(son[x],topf); for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(v==son[x]||v==fa[x])continue; dfs2(v,v); } } void UP(int x,int y,int v) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); d[id[top[x]]].push_back(v); d[id[x]+1].push_back(-v); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); d[id[x]].push_back(v); d[id[y]+1].push_back(-v); } void init() { cnt=pos=0;CLR(head,0);dep[1]=son[0]=0; } int main() { while(~RII(n,m)) { if(!n&&!m)break; init(); rep(i,1,n-1)RII(a,b),add(a,b),add(b,a); dfs1(1,1);dfs2(1,1); int maxx=1; rep(i,1,m)RIII(a,b,c),UP(a,b,c),maxx=max(maxx,c); build(1,maxx,1); rep(i,1,n) { int len=d[i].size(); for(int j=0;j<len;j++) { int v=d[i][j]; if(v>0)upnode(v,1,1,maxx,1); if(v<0) upnode(-v,-1,1,maxx,1); } ans[i]=maxnum[1]; if(t[1]==0)ans[i]=0; } rep(i,1,n) printf("%d ",ans[id[i]]); rep(i,1,n+5)d[i].clear(); } return 0; }