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
| #include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x));
#define for_edge(i, x) for(RG int i = head[x]; i; i = e[i].next)
#define OPERATOR(Name, key, opt) inline bool operator opt (const Name &a, const Name &b) { return a.key opt b.key; }
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(50010);
struct edge { int next, to; } e[maxn << 1];
int head[maxn], e_num, n, P, Q, fa[20][maxn], dep[maxn], pos[maxn], end_pos[maxn], cnt, q_cnt;
inline void add_edge(int from, int to) { e[++e_num] = (edge) {head[from], to}; head[from] = e_num; }
struct Matrix { int x1, y1, x2, y2, k; } t[maxn << 2];
struct Node { int x, y, k, id; } q[maxn], pl[maxn], pr[maxn];
struct InNode { int l, r, x, val; } L[maxn];
OPERATOR(Matrix, k, <); OPERATOR(Node, x, <); OPERATOR(InNode, x, <);
void dfs(int x)
{
pos[x] = ++cnt;
for(RG int i = 1; i <= 15; i++) fa[i][x] = fa[i - 1][fa[i - 1][x]];
for_edge(i, x)
{
int to = e[i].to; if(to == fa[0][x]) continue;
fa[0][to] = x; dep[to] = dep[x] + 1; dfs(to);
}
end_pos[x] = cnt;
}
template<int T>
inline int LCA(int a, int b)
{
if(dep[a] < dep[b]) std::swap(a, b);
for(RG int i = 15; ~i; i--)
if(dep[fa[i][a]] > dep[b]) a = fa[i][a];
if(fa[0][a] == b) return T ? a : b;
a = fa[0][a];
for(RG int i = 15; ~i; i--)
if(fa[i][a] != fa[i][b]) a = fa[i][a], b = fa[i][b];
return T ? a : fa[0][a];
}
int c[maxn], ans[maxn];
inline void update(int x, int v) { while(x <= n) c[x] += v, x += x & -x; }
inline int query(int x) { int Ans = 0; while(x) Ans += c[x], x -= x & -x; return Ans; }
void Div(int l, int r, int ql, int qr)
{
if(ql > qr) return;
if(l == r) { for(RG int i = ql; i <= qr; i++) ans[q[i].id] = t[l].k; return; }
int mid = (l + r) >> 1, tl = 0, tr = 0, cntL = 0, p = 1;
for(RG int i = l; i <= mid; i++)
L[++cntL] = (InNode) {t[i].y1, t[i].y2, t[i].x1, 1},
L[++cntL] = (InNode) {t[i].y1, t[i].y2, t[i].x2 + 1, -1};
std::sort(L + 1, L + cntL + 1);
for(RG int i = ql; i <= qr; i++)
{
while(p <= cntL && L[p].x <= q[i].x) update(L[p].l, L[p].val), update(L[p].r + 1, -L[p].val), ++p;
int sum = query(q[i].y);
if(q[i].k <= sum) pl[++tl] = q[i];
else q[i].k -= sum, pr[++tr] = q[i];
}
for(RG int i = 1; i < p; i++) update(L[i].l, -L[i].val), update(L[i].r + 1, L[i].val);
for(RG int i = 1; i <= tl; i++) q[ql + i - 1] = pl[i];
for(RG int i = 1; i <= tr; i++) q[ql + tl + i - 1] = pr[i];
Div(l, mid, ql, ql + tl - 1);
Div(mid + 1, r, ql + tl, qr);
}
int main()
{
n = read(); P = read(); Q = read();
for(RG int i = 1, a, b; i < n; i++) a = read(), b = read(), add_edge(a, b), add_edge(b, a);
dep[1] = 1; dfs(1);
for(RG int i = 1, a, b, k; i <= P; i++)
{
a = read(); b = read(); k = read();
if(pos[a] > pos[b]) std::swap(a, b);
int lca = LCA<0>(a, b);
if(a != lca) t[++q_cnt] = (Matrix) {pos[a], pos[b], end_pos[a], end_pos[b], k};
else
{
int Lca = LCA<1>(a, b);
if(pos[Lca] != 1) t[++q_cnt] = (Matrix) {1, pos[b], pos[Lca] - 1, end_pos[b], k};
if(end_pos[Lca] != n) t[++q_cnt] = (Matrix) {pos[b], end_pos[Lca] + 1, end_pos[b], n, k};
}
}
for(RG int i = 1, a, b, k; i <= Q; i++)
{
a = read(); b = read(); k = read();
if(pos[a] > pos[b]) std::swap(a, b);
q[i] = (Node) {pos[a], pos[b], k, i};
}
std::sort(t + 1, t + q_cnt + 1);
std::sort(q + 1, q + Q + 1);
clear(c, 0);
Div(1, q_cnt, 1, Q);
for(RG int i = 1; i <= Q; i++) printf("%d\n", ans[i]);
return 0;
}
|