首先村落里的一共有n座房屋，并形成一个树状结构。然后救济粮分m次发放，每次选择两个房屋(x,y)，然后对于x到y的路径上（含x和y)每座房子里发放一袋z类型的救济粮。
然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。
Solution
一看到链上操作，最后统计答案，自然而然的想到树上差分，a++ ，b++，lca--，fa[lca]--就可以完成一条链的操作。
但这道题加的东西有好多种类。
所以考虑对每个节点开一颗线段树，每次在对应位置加上。
然后我们DFS的时候，朴素的树上差分直接size[u]+=size[v] (son[u]==v)这回u和v是两颗线段树。
所以用线段数合并就行了。
由于这题涉及大量的线段树，所以我们的数组得开大点。
颜色需要提前离散化。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 100002
using namespace std;
int p[N][],head[N],tot,deep[N],tr[N*],L[N*],R[N*],num[N],rt[N],top,ans[N],toy;
struct zzh{
int n,to;
}e[N<<];
struct bi{
int a,b,d;
}q[N];
inline void add(int u,int v){
e[++tot].n=head[u];
e[tot].to=v;
head[u]=tot;
}
void dfs(int u,int fa){
for(int i=;(<<i)<=deep[u];++i)p[u][i]=p[p[u][i-]][i-];
for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){
int v=e[i].to;p[v][]=u;deep[v]=deep[u]+;
dfs(v,u);
}
}
inline int getlca(int a,int b){
if(deep[a]<deep[b])swap(a,b);
for(int i=;i>=;--i)if(deep[a]-(<<i)>=deep[b])a=p[a][i];
if(a==b)return a;
for(int i=;i>=;--i)if(p[a][i]!=p[b][i])a=p[a][i],b=p[b][i];
return p[a][];
}
void upd(int &cnt,int l,int r,int x,int y){
if(!cnt)cnt=++toy;
if(l==r){
tr[cnt]+=y;
return;
}
int mid=(l+r)>>;
if(mid>=x)upd(L[cnt],l,mid,x,y);
else upd(R[cnt],mid+,r,x,y);
tr[cnt]=max(tr[L[cnt]],tr[R[cnt]]);
}
int query(int &cnt,int l,int r){
if(!tr[cnt]||!cnt)return ;
if(l==r)return num[l];
int mid=(l+r)>>;
if(tr[L[cnt]]>=tr[R[cnt]])return query(L[cnt],l,mid);
else return query(R[cnt],mid+,r);
}
int merge(int &u,int v,int l,int r){
if(!u||!v)return u+v;
if(l==r){
tr[u]+=tr[v];
return u;
}
int mid=(l+r)>>;
L[u]=merge(L[u],L[v],l,mid);
R[u]=merge(R[u],R[v],mid+,r);
tr[u]=max(tr[L[u]],tr[R[u]]);
return u;
}
void dfs2(int u,int fa){
for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){
int v=e[i].to;
dfs2(v,u);
rt[u]=merge(rt[u],rt[v],,top);
}
ans[u]=query(rt[u],,top);
}
int main(){
int n,m,u,v;
scanf("%d%d",&n,&m);
for(int i=;i<n;++i)scanf("%d%d",&u,&v),add(u,v),add(v,u);
dfs(,);
for(int i=;i<=m;++i)scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].d),num[++top]=q[i].d;
sort(num+,num+top+);
top=unique(num+,num+top+)-num-;
for(int i=;i<=m;++i){
q[i].d=lower_bound(num+,num+top+,q[i].d)-num;
int lca=getlca(q[i].a,q[i].b);
upd(rt[q[i].a],,top,q[i].d,);upd(rt[q[i].b],,top,q[i].d,);
upd(rt[lca],,top,q[i].d,-);upd(rt[p[lca][]],,top,q[i].d,-);
}
dfs2(,);
for(int i=;i<=n;++i)printf("%d\n",ans[i]);
return ;
}