题目大意：给定一颗含有$n$个结点的树，每次选择两个结点$x$和$y$，对从$x$到$y$的路径上发放一带$z$类型的物品。问完成所有操作后每个结点发放最多的时哪种物品。
普通的树链剖分貌似也可以做这道题，可以记录一个$c$数组用来记录结点中每种物品的个数，然后暴力乱搞。空间可能会炸。
这时候我们需要一种新算法：树上差分。
关于树上差分，有需要的同学可以去看大佬的博客，我这里说一下思想。
对于序列的差分，我们都知道，假设让序列中$i-j$的数都加上$z$，那么直接让差分数组$b[i]+=z$，$b[j]-=z$即可。放到一颗树中（其实这里变成了子树和），让路径上$s-t$的结点都加上$k$，我们只需在$s,t$加上$k$，在$lca(s,t),fa[lca(s,t)]$减去$k$即可。实际上树上差分的实现形式多种多样，我们可以根据题目需要来作改动。
对于此题，我们不妨用$\log n$的时间把路径$x,y$拆分成$[a_1,b_1],[a_2,b_2],\cdots ,[a_k,b_k]$这样多个区间的形式，每次在$a_i$处加上$z$，在$b_i+1$处减去$z$。写起来是这样的：
inline void chai(int x,int y,int c)
{
while(top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
Add(dfn[top[x]],c);Add(dfn[x]+1,-c);
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
Add(dfn[x],c);Add(dfn[y]+1,-c);
}
个数可以用线段树维护。其实正解应该是动态开点+线段树合并之类的高级算法，但是我不会QAQ。所以只写了较为普通的线段树维护。时间复杂度$n\log n$。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200005;
int n,m;
int size[maxn],son[maxn],dep[maxn],fa[maxn];
int dfn[maxn],cnt,w[maxn],top[maxn],ans[maxn];//w[dfn[x]]=x; ans[w[i]]=sum;
int head[maxn*2],jishu;
int Head[maxn*2],Jishu;
struct node
{
int next,to,val;
}edge[maxn*2],Edge[maxn*2];//Edge chai
struct tre
{
int maxx,pos;
}tree[maxn*4];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void add(int from,int to)
{
edge[++jishu].next=head[from];
edge[jishu].to=to;
head[from]=jishu;
}
inline void Add(int from,int val)
{
Edge[++Jishu].next=Head[from];
Edge[Jishu].val=val;
Head[from]=Jishu;
}
inline void dfs_son(int now,int f,int deep)
{
dep[now]=deep;
fa[now]=f;
size[now]=1;
int maxson=-1;
for (int i=head[now];i;i=edge[i].next)
{
int to=edge[i].to;
if (to==f) continue;
dfs_son(to,now,deep+1);
size[now]+=size[to];
if (maxson<size[to]) maxson=size[to],son[now]=to;
}
}
inline void dfs(int now,int tp)
{
dfn[now]=++cnt;
top[now]=tp;
w[cnt]=now;
if (son[now]) dfs(son[now],tp);
for (int i=head[now];i;i=edge[i].next)
{
int to=edge[i].to;
if (dfn[to]) continue;
dfs(to,to);
}
}
inline void pushup(int index)
{
if (tree[index*2].maxx>=tree[index*2+1].maxx) tree[index].maxx=tree[index*2].maxx,tree[index].pos=tree[index*2].pos;
else tree[index].maxx=tree[index*2+1].maxx,tree[index].pos=tree[index*2+1].pos;
}
inline void build(int index,int l,int r)
{
if (l==r){tree[index].maxx=0;tree[index].pos=l;return;}
int mid=(l+r)>>1;
build(index*2,l,mid);
build(index*2+1,mid+1,r);
pushup(index);
}
inline void update(int index,int l,int r,int pos,int k)
{
if (l==r){tree[index].maxx+=k;return;}
int mid=(l+r)>>1;
if (pos<=mid) update(index*2,l,mid,pos,k);
if (pos>mid) update(index*2+1,mid+1,r,pos,k);
pushup(index);
}
inline void chai(int x,int y,int c)
{
while(top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
Add(dfn[top[x]],c);Add(dfn[x]+1,-c);
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
Add(dfn[x],c);Add(dfn[y]+1,-c);
}
signed main()
{
n=read(),m=read();
for (int i=1;i<n;i++)
{
int x=read(),y=read();
add(x,y);add(y,x);
}
dfs_son(1,0,1);
dfs(1,1);
for (int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
chai(x,y,z);
}
build(1,1,100000);
//for (int i=1;i<=n;i++) cout<<w[i]<<endl;
for (int i=1;i<=n;i++)
{
for (int j=Head[i];j;j=Edge[j].next)
{
if (Edge[j].val>0) update(1,1,100000,Edge[j].val,1);
else update(1,1,100000,-Edge[j].val,-1);
}
ans[w[i]]=tree[1].maxx?tree[1].pos:0;
}
//cout<<Jishu;
for (int i=1;i<=n;i++) printf("%lld\n",ans[i]);
return 0;
}