题目传送门
树链剖分做法
显然可以树链剖分维护链上信息，操作离线，按 \(z\) 从小到大操作即可。
时间复杂度 \(\mathcal O\left(m\log^2n\right)\)。
线段树合并做法
对于每一个点都开一个动态开点权值线段树记录收到的救济粮数量。
操作路径可以进行树上差分转化为 \(4\) 次操作。
即修改 \(x\sim y\) 的路径时，修改四个点：
- \(x,y\)，记录收到了 \(z\)。
- \(\operatorname{lca}(x,y)\)，记录减去 \(z\)。
- \(\textit{father}_{\operatorname{lca}(x,y)}\)，记录减去 \(z\)。
合并线段树其实比较简单，核心代码如下：
//this[a],that[b]
int merge(int x,int y){if(!x||!y){return x|y;}if(t[x].l==t[x].r){t[x].sum+=t[y].sum;t[x].max+=t[y].max;t[x].id=t[x].l;return x;}t[x].lChild=merge(t[x].lChild,t[y].lChild);t[x].rChild=merge(t[x].rChild,t[y].rChild);up(x);return x;
}
//root:根节点
void merge(segTree &x){merge(root,x.root);
}
递归合并即可，单次合并至多新增 \(\mathcal O(n\log n)\) 个节点，复杂度也是 \(\mathcal O(n\log n)\)。
在需要线段树合并时，通常给所有节点开一个公共空间存储。
AC 代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e5,V=1e5;
struct node{int l,r;int lChild,rChild;int sum,max,id;
}t[V*100];
int create(node x){static int size;t[++size]=x;return size;
}
struct segTree{int root;void build(int l,int r){root=create({l,r});}void up(int p){t[p].sum=t[t[p].lChild].sum+t[t[p].rChild].sum;if(t[t[p].lChild].max>=t[t[p].rChild].max){t[p].max=t[t[p].lChild].max;t[p].id=t[t[p].lChild].id;}else{t[p].max=t[t[p].rChild].max;t[p].id=t[t[p].rChild].id;}}void add(int p,int x,int k){if(t[p].l==t[p].r){t[p].sum+=k;t[p].max+=k;t[p].id=x;return;}int mid=t[p].l+t[p].r>>1;if(!t[p].lChild){t[p].lChild=create({t[p].l,mid});}if(x<=t[t[p].lChild].r){add(t[p].lChild,x,k); }if(!t[p].rChild){t[p].rChild=create({mid+1,t[p].r});}if(t[t[p].rChild].l<=x){add(t[p].rChild,x,k);}up(p);}void add(int x,int k){add(root,x,k);}//this[a],that[b]int merge(int x,int y){if(!x||!y){return x|y;}if(t[x].l==t[x].r){t[x].sum+=t[y].sum;t[x].max+=t[y].max;t[x].id=t[x].l;return x;}t[x].lChild=merge(t[x].lChild,t[y].lChild);t[x].rChild=merge(t[x].rChild,t[y].rChild);up(x);return x;}void merge(segTree &x){merge(root,x.root);}int query(){if(t[root].sum){return t[root].id;}else{return 0;}}
}seg[N+1];
int n,ans[N+1];
vector<int>g[N+1];
int father[N+1],depth[N+1],dfn[N+1],rnk[N+1],st[N+1][__lg(N)+1],rest[N+1][__lg(N)+1];
void dfs0(int x,int fx){father[x]=fx;depth[x]=depth[fx]+1;static int cnt;dfn[x]=++cnt;rnk[cnt]=x;for(int i:g[x]){if(i==fx){continue;}dfs0(i,x);}
}
void pre(){dfs0(1,0);for(int i=1;i<=n;i++){st[i][0]=depth[rnk[i]];rest[i][0]=rnk[i];}for(int i=1;(1<<i)<=n;i++){for(int x=1;x<=n;x++){if(st[x][i-1]<st[x+(1<<i-1)][i-1]){st[x][i]=st[x][i-1];rest[x][i]=rest[x][i-1];}else{st[x][i]=st[x+(1<<i-1)][i-1];rest[x][i]=rest[x+(1<<i-1)][i-1];}}}for(int i=1;i<=n;i++){seg[i].build(1,V);}
}
int lca(int u,int v){if(u==v){return u;}if(dfn[u]>dfn[v]){swap(u,v);}int s=__lg(dfn[v]-dfn[u]);if(st[dfn[u]+1][s]<st[dfn[v]-(1<<s)+1][s]){return father[rest[dfn[u]+1][s]];}else{return father[rest[dfn[v]-(1<<s)+1][s]];}
}
void dfs(int x,int fx){for(int i:g[x]){if(i==fx){continue;}dfs(i,x);seg[x].merge(seg[i]);}ans[x]=seg[x].query();
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int m;cin>>n>>m;for(int i=1;i<n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}pre();while(m--){int x,y,z;cin>>x>>y>>z;seg[x].add(z,1);seg[y].add(z,1);int p=lca(x,y);seg[p].add(z,-1);if(father[p]){seg[father[p]].add(z,-1);}}dfs(1,0); for(int i=1;i<=n;i++){cout<<ans[i]<<'\n';}cout<<'\n';cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}