首先显然众数可以用权值线段树来维护，但是由于我们要对每一个点开一棵权值线段树，所以树剖分解为区间的话标记不好打。
（虽然可以用类似序列差分的方式用 vector 存储）
显而易见地考虑树上差分 + 线段树合并，这大概是个套路吧。
没啥好解释的，注意合并的时候代码实现的细节。
BFS 大法好。
代码： 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
using namespace std;
const int N = 1e5;
const int M = 1e5;
const int Z = 1e9;
int n,m;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5];
int q[N + 5],head,tail;
inline int getlca(int x,int y)
{
while(top[x] ^ top[y])
dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
return dep[x] < dep[y] ? x : y;
}
struct node
{
int max,mode;
int ls,rs;
} seg[(N << 6) + 10];
int rt[N + 5];
int merge(int x,int y,int tl,int tr)
{
if(!x || !y)
return x | y;
if(tl == tr)
{
seg[x].max += seg[y].max;
if(seg[x].max > 0)
seg[x].mode = tl;
return x;
}
int mid = tl + tr >> 1;
seg[x].ls = merge(seg[x].ls,seg[y].ls,tl,mid),seg[x].rs = merge(seg[x].rs,seg[y].rs,mid + 1,tr);
if(seg[seg[x].ls].max >= seg[seg[x].rs].max)
seg[x].max = seg[seg[x].ls].max,seg[x].mode = seg[seg[x].ls].mode;
else
seg[x].max = seg[seg[x].rs].max,seg[x].mode = seg[seg[x].rs].mode;
return x;
}
void insert(int x,int k,int &p,int tl,int tr)
{
static int tot = 0;
if(!p)
p = ++tot;
if(tl == tr)
{
seg[p].max += k;
if(seg[p].max > 0)
seg[p].mode = tl;
return ;
}
int mid = tl + tr >> 1;
x <= mid ? insert(x,k,seg[p].ls,tl,mid) : insert(x,k,seg[p].rs,mid + 1,tr);
if(seg[seg[p].ls].max >= seg[seg[p].rs].max)
seg[p].max = seg[seg[p].ls].max,seg[p].mode = seg[seg[p].ls].mode;
else
seg[p].max = seg[seg[p].rs].max,seg[p].mode = seg[seg[p].rs].mode;
}
int ans[N + 5];
int main()
{
scanf("%d%d",&n,&m);
int u,v;
for(register int i = 1;i < n;++i)
scanf("%d%d",&u,&v),add(u,v),add(v,u);
dep[q[++tail] = 1] = 1;
for(register int p;head < tail;)
{
sz[p = q[++head]] = 1;
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
fa[to[i]] = p,dep[to[i]] = dep[p] + 1,q[++tail] = to[i];
}
for(register int i = n;i;--i)
{
sz[fa[q[i]]] += sz[q[i]];
if(!son[fa[q[i]]] || sz[q[i]] > sz[son[fa[q[i]]]])
son[fa[q[i]]] = q[i];
}
for(register int i = 1;i <= n;++i)
top[q[i]] = q[i] == son[fa[q[i]]] ? top[fa[q[i]]] : q[i];
int w;
for(;m;--m)
{
scanf("%d%d%d",&u,&v,&w);
int lca = getlca(u,v);
insert(w,1,rt[u],1,Z),insert(w,1,rt[v],1,Z),insert(w,-1,rt[lca],1,Z),insert(w,-1,rt[fa[lca]],1,Z);
}
for(register int i = n;i;--i)
ans[q[i]] = seg[rt[q[i]]].mode,rt[fa[q[i]]] = merge(rt[fa[q[i]]],rt[q[i]],1,Z);
for(register int i = 1;i <= n;++i)
printf("%d\n",ans[i]);
}