# bzoj 3307 雨天的尾巴

### Description

N个点，形成一个树状结构。有M次发放，每次选择两个点x,y

20 50

8 6

10 6

18 6

20 10

7 20

2 18

19 8

1 6

14 20

16 10

13 19

3 14

17 18

11 19

4 11

15 14

5 18

9 10

12 15

11 14 87

12 1 87

14 3 84

17 2 36

6 5 93

17 6 87

10 14 93

5 16 78

6 15 93

15 5 16

11 8 50

17 19 50

5 4 87

15 20 78

1 17 50

20 13 87

7 15 22

16 11 94

19 8 87

18 3 93

13 13 87

2 1 87

2 6 22

5 20 84

10 12 93

18 12 87

16 10 93

8 17 93

14 7 36

7 4 22

5 9 87

13 10 16

20 11 50

9 16 84

10 17 16

19 6 87

12 2 36

20 9 94

9 2 84

14 1 94

5 5 94

8 17 16

12 8 36

20 17 78

12 18 50

16 8 94

2 19 36

10 18 36

14 19 50

4 12 50

87

36

84

22

87

87

22

50

84

87

50

36

87

93

36

94

16

87

50

50

1<=N,M<=100000

1<=a,b,x,y<=N

1<=z<=10^9

### 题解

#include <cstdio>
#include <algorithm>
#define mid (l + r >> 1)
#define lson t[rt].l, l, mid
#define rson t[rt].r, mid + 1, r
using namespace std;
const int N = 100010;
struct edge {
int to,next;
}e[N << 1];
int st[N], siz[N], top[N], son[N], fa[N], deep[N], p[N];
int tot, n, m, x, y, root[N];
void add(int x, int y) {
e[++tot].next = st[x];
e[tot].to = y, st[x] = tot;
}
void dfs1(int now) {
siz[now] = 1, p[++p[0]] = now;
for (int i = st[now]; i; i = e[i].next)
if (e[i].to != fa[now]) {
fa[e[i].to] = now, deep[e[i].to] = deep[now] + 1;
dfs1(e[i].to), siz[now] += siz[e[i].to];
if (siz[son[now]] < siz[e[i].to])
son[now] = e[i].to;
}
}
void dfs2(int now, int tp) {
top[now] = tp;
if (son[now]) dfs2(son[now], tp);
for (int i = st[now]; i; i = e[i].next)
if (e[i].to != fa[now] && e[i].to != son[now])
dfs2(e[i].to, e[i].to);
}
int lca(int x, int y) {
while (top[x] != top[y]) deep[top[x]] > deep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
return deep[x] > deep[y] ? y : x;
}
struct datas {
int x, y, z;
}q[N];
bool comp(datas a, datas b) {
return a.z < b.z;
}
struct segt {
int l, r, typ, val;
}t[N * 50];
int sz, ref[N];
void update(int rt) {
t[rt].val = max(t[t[rt].l].val, t[t[rt].r].val);
t[rt].typ = (t[t[rt].l].val >= t[t[rt].r].val) ? t[t[rt].l].typ : t[t[rt].r].typ;
}
void inserts(int &rt, int l, int r, int pos, int v) {
if (!rt) rt = ++sz;
if (l == r) { t[rt].val += v, t[rt].typ = ref[l]; return; }
if (pos <= mid) inserts(lson, pos, v);
else            inserts(rson, pos, v);
update(rt);
}
void merges(int &x, int y, int l, int r) {
if (!y) return;
if (!x) { x = y; return; }
if (l == r) { t[x].val += t[y].val; return; }
merges(t[x].l, t[y].l, l, mid);
merges(t[x].r, t[y].r, mid + 1, r);
update(x);
}
main() {
scanf("%d%d", &n, &m);
for (int i = 1; i < n; ++i)
scanf("%d%d", &x, &y),
for (int i = 1; i <= n; ++i) root[i] = ++sz;
deep[1] = 1, dfs1(1), dfs2(1, 1);
for (int i = 1; i <= m; ++i)
scanf("%d%d%d", &q[i].x, &q[i].y, &q[i].z);
sort(q + 1, q + 1 + m, comp);
for (int i = 1, d = 0; i <= m; ++i) {
int a = q[i].x, b = q[i].y, c = lca(a, b);
if (q[i].z > q[i - 1].z) ref[++d] = q[i].z;
inserts(root[a], 0, m, d, 1), inserts(root[b], 0, m, d, 1), inserts(root[c], 0, m, d, -1);
if (c != 1) inserts(root[fa[c]], 0, m, d, -1);
}
for (int i = n; i > 1; --i) merges(root[fa[p[i]]], root[p[i]], 0, m);
for (int i = 1; i <= n; ++i) printf("%d\n", t[root[i]].typ);
}