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
195
196
197
198
199
200
201
202
203
//#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=10,V=1e5;
struct segTree{
struct node{
int l,r,lChild,rChild;
int cnt,maxId,maxCnt;
};
vector<node>t;
int create(node x){
t.push_back(x);
cerr<<"!!!!"<<t.size()-1<<endl;
return 2;
// return t.size()-1;
}
segTree(){
t.resize(0);
create({});
create({1,V});
}
void up(int p){
if(t[t[p].lChild].maxCnt>=t[t[p].rChild].maxCnt){
t[p].maxId=t[t[p].lChild].maxId;
}else{
t[p].maxId=t[t[p].rChild].maxId;
}
}
void add(int p,int x,int k){
cerr<<"add("<<p<<","<<x<<","<<k<<"):t["<<p<<"]=";
cerr<<"["<<t[p].l<<","<<t[p].r<<"]:cnt="<<t[p].cnt<<" maxId="<<t[p].maxId<<" maxCnt="<<t[p].maxCnt<<endl;
if(t[p].l==t[p].r){
t[p].cnt+=k;
t[p].maxId=t[p].l;
t[p].maxCnt=t[p].cnt;
}else{
int mid=t[p].l+t[p].r>>1;
if(x<=mid){
cerr<<"A------------\n";
if(!t[p].lChild){
int tmp=create({t[p].l,mid});
t[p].lChild=tmp;
}
add(t[p].lChild,x,k);
}else{
cerr<<"B================\n";
if(!t[p].rChild){
int tmp=create({mid+1,t[p].r});
t[p].rChild=tmp;
}
add(t[p].rChild,x,k);
}
}
up(p);
}
void add(int x,int k){
add(1,x,k);
}
int merge(int p,int q,segTree &tree){
if(!q){
return p;
}
if(!p){
return create(tree.t[q]);
}
if(t[p].l==t[p].r){
t[p].cnt+=tree.t[q].cnt;
t[p].maxId=t[p].l;
t[p].maxCnt=t[p].cnt;
return p;
}
t[p].lChild=merge(t[p].lChild,tree.t[q].lChild,tree);
t[p].rChild=merge(t[q].rChild,tree.t[q].rChild,tree);
up(p);
return p;
}
void merge(segTree &tree){
merge(1,1,tree);
}
int query(){
return t[1].maxId;
}
}t[N+1];
int n;
vector<int>g[N+1];
int dfn[N+1],order[N+1],dep[N+1],father[N+1],st[N+1][__lg(N+1)+1],reSt[N+1][__lg(N+1)+1];
void dfs0(int x,int fx){
father[x]=fx;
dep[x]=dep[fx]+1;
static int cnt;
dfn[x]=++cnt;
order[dfn[x]]=x;
for(int i:g[x]){
if(i==fx){
continue;
}
dfs0(i,x);
}
}
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 pre(){
dfs0(1,0);
for(int i=1;i<=n;i++){
st[i][0]=dep[order[i]];
reSt[i][0]=order[i];
}
for(int i=1;(1<<i)<=n;i++){
for(int x=1;x+(1<<i)-1<=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];
}
}
}
}
void dfs(int x,int fx){
for(int i:g[x]){
if(i==fx){
continue;
}
dfs(i,x);
t[x].merge(t[i]);
}
}
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;
int lcaXY=lca(x,y);
cerr<<"------------------------\nadd x:\n";
t[x].add(z,1);
cerr<<"------------------------\nadd y:\n";
t[y].add(z,1);
cerr<<"------------------------\nadd lca(x,y):\n";
t[lcaXY].add(z,-1);
if(father[lcaXY]){
cerr<<"------------------------\nadd father[lca(x,y)]:\n";
t[father[lcaXY]].add(z,-1);
}
}
dfs(1,0);
for(int i=1;i<=n;i++){
cout<<t[i].query()<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
/*
5 1
1 2
3 1
3 4
5 3
2 3 3
*/
这段代码中，第 $53,54$ 行如若改为以下代码，则会出现问题：
1
t[p].lChild=create({t[p].l,mid});
会发现，create({t[p].l,mid}) 的返回值为 $2$，而输出 t[p].lChild 却为 $0$。
这是因为，vector 扩容导致之前 t[p].lChild 的指针失效，从而出现错误。虽然这里没有指针，但是编译器先访问左侧，会计算出其指针，计算出右侧后往指针赋值。
例如，下列代码就是类似的：
1
--x=x++;
总而言之，同一条语句中，尽量避免同一变量，尤其注意涉及变量修改时。
