线段树合并

P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node{int v,nxt;
}e[N*2];
int n,m;
int first[N],tot=0;
int dep[N],fa[N][20],lg[N];
int ls[N*50],rs[N*50],rt[N],cnt=0;
int sum[N*50],res[N*50];
int ans[N];
void add(int u1,int v1){e[++tot].v=v1;e[tot].nxt=first[u1];first[u1]=tot;
}
void dfs(int u,int f){dep[u]=dep[f]+1;fa[u][0]=f;for(int i=1;i<=lg[dep[u]];++i)fa[u][i]=fa[fa[u][i-1]][i-1];for(int i=first[u];i;i=e[i].nxt){int v1=e[i].v;if(v1==f)  continue;dfs(v1,u);}
}
void pushup(int k){if(sum[ls[k]]<sum[rs[k]]){res[k]=res[rs[k]];sum[k]=sum[rs[k]];}else{res[k]=res[ls[k]];sum[k]=sum[ls[k]];}
}
int update(int ro,int x,int y,int z,int t){if(!ro)  ro=++cnt;if(x==y){sum[ro]+=t;res[ro]=z;return ro;}int mid=(x+y)/2;if(z<=mid)  ls[ro]=update(ls[ro],x,mid,z,t);else  rs[ro]=update(rs[ro],mid+1,y,z,t);pushup(ro);return ro;
}
int lca(int x,int y){if(dep[x]<dep[y])  swap(x,y);while(dep[x]>dep[y]){x=fa[x][lg[dep[x]-dep[y]]];}if(x==y)  return x;for(int i=lg[dep[x]];i>=0;--i)if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}return fa[x][0];
}
int merge(int a,int b,int x,int y){if(!a)  return b;if(!b)  return a;if(x==y){sum[a]+=sum[b];return a;}int mid=(x+y)/2;ls[a]=merge(ls[a],ls[b],x,mid);rs[a]=merge(rs[a],rs[b],mid+1,y);pushup(a);return a;
}
void calc(int u){for(int i=first[u];i;i=e[i].nxt){int v1=e[i].v;if(v1==fa[u][0])  continue;calc(v1);rt[u]=merge(rt[u],rt[v1],1,1e5);}ans[u]=res[rt[u]];if(sum[rt[u]]==0)  ans[u]=0;
}
int main(){cin>>n>>m;memset(first,0,sizeof(first));memset(dep,0,sizeof(dep));memset(lg,0,sizeof(lg));lg[0]=-1;for(int i=1;i<n;++i){int ui,vi;scanf("%d%d",&ui,&vi);add(ui,vi);add(vi,ui);lg[i]=lg[i>>1]+1;}lg[n]=lg[n>>1]+1;dep[0]=0;dfs(1,0);while(m--){int xi,yi,zi;scanf("%d%d%d",&xi,&yi,&zi);rt[xi]=update(rt[xi],1,1e5,zi,1);rt[yi]=update(rt[yi],1,1e5,zi,1);int anc=lca(xi,yi);rt[anc]=update(rt[anc],1,1e5,zi,-1);rt[fa[anc][0]]=update(rt[fa[anc][0]],1,1e5,zi,-1);}calc(1);for(int i=1;i<=n;++i)printf("%d\n",ans[i]);return 0;
}