树链剖分做法
显然可以树链剖分维护链上信息，操作离线，按 $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$。
合并线段树其实比较简单，核心代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//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);
}
递归合并即可，记两棵线段树重合部分大小为 $\textit{size}$，则合并复杂度为 $\mathcal O(size)$。
在需要线段树合并时，通常给所有节点开一个公共空间存储。
AC 代码
时间复杂度：$\mathcal O((n+m)\log n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
//#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;
}
