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
| #include<cstdio>
#include<algorithm>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
inline int read()
{
int data=0, w=1;
char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1, ch=getchar();
while(ch>='0'&&ch<='9') data=data*10+(ch^48), ch=getchar();
return data*w;
}
const int maxn(100010);
struct node { node *son[2]; int max, id; } *root[maxn], pool[maxn * 50], *pos;
struct edge { int next, to; } e[maxn << 1];
struct query { int next, to, id; } q[maxn << 1];
struct answer { int a, b, v, lca; } ans[maxn];
bool vis[maxn];
int head[maxn], e_num, fa[maxn], n, m, s, qhead[maxn], q_num, F[maxn], Ans[maxn];
inline void add_edge(int from, int to) { e[++e_num] = (edge) {head[from], to}; head[from] = e_num; }
inline void add_query(int from, int to, int id) { q[++q_num] = (query) {qhead[from], to, id}; qhead[from] = q_num; }
inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void dfs(int x)
{
vis[x] = true;
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == F[x]) continue;
F[to] = x; dfs(to); fa[find(to)] = find(x);
}
for(RG int i = qhead[x]; i; i = q[i].next)
{
int to = q[i].to; if(!vis[to]) continue;
ans[q[i].id].lca = find(to);
}
}
inline int Max(node *x) { return x ? x -> max : 0; }
inline int Id(node *x) { return x ? x -> id : 0; }
inline void pushup(node *x)
{
if(Max(x -> son[0]) >= Max(x -> son[1])) x -> max = Max(x -> son[0]), x -> id = Id(x -> son[0]);
else x -> max = Max(x -> son[1]), x -> id = Id(x -> son[1]);
if(!x -> max) x -> id = 0;
}
inline void Insert(node *&x, int pos, int val, int l = 1, int r = maxn - 10)
{
if(!x) x = ::pos++; if(l == r) { x -> max += val; x -> id = l; if(!x -> max) x -> id = 0; return; }
int mid = (l + r) >> 1;
if(pos <= mid) Insert(x -> son[0], pos, val, l, mid);
else Insert(x -> son[1], pos, val, mid + 1, r);
pushup(x); if(!x -> max) x -> id = 0;
}
inline node *Merge(node *x, node *&y, int l = 1, int r = maxn - 10)
{
if(!x) return y; if(!y) return x;
int mid = (l + r) >> 1; if(l == r) { x -> max += y -> max; x -> id = l; return x; }
x -> son[0] = Merge(x -> son[0], y -> son[0], l, mid);
x -> son[1] = Merge(x -> son[1], y -> son[1], mid + 1, r);
pushup(x); return x;
}
void solve(int x)
{
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == F[x]) continue;
solve(to); root[x] = Merge(root[x], root[to]);
}
Ans[x] = Id(root[x]);
}
int main()
{
#ifndef ONLINE_JUDGE
file(cpp);
#endif
pos = pool; n = read(); m = read();
for(RG int i = 1, a, b; i < n; i++) a = read(), b = read(), add_edge(a, b), add_edge(b, a);
for(RG int i = 1; i <= n; i++) fa[i] = i;
for(RG int i = 1, a, b, c; i <= m; i++)
a = read(), b = read(), c = read(), ans[i] = (answer) {a, b, c, 0}, add_query(a, b, i), add_query(b, a, i);
dfs(1);
for(RG int i = 1; i <= m; i++)
Insert(root[ans[i].a], ans[i].v, 1), Insert(root[ans[i].b], ans[i].v, 1), Insert(root[ans[i].lca], ans[i].v, -1),
Insert(root[F[ans[i].lca]], ans[i].v, -1);
solve(1); for(RG int i = 1; i <= n; i++) printf("%d\n", Ans[i]);
return 0;
}
|