spoj QTREE2(倍增LCA)

spoj QTREE2
把一条路径根据$LCA$拆成两条链,然后判断第$k$个点在哪条链上即可
注意求LCA的时候要判断深度大小,以及树上的路径权值和不要误认为是距离了

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define pb push_back
using namespace std;
const int MAXN = 20000 + 5, logs = 20;
struct data {LL v, wi;}ed[MAXN * 2];
LL en, n, fa[MAXN], dep[MAXN], pre[MAXN][logs + 1], far[MAXN];
vector<LL> G[MAXN];
void clean() {
en = 0;
for (LL i = 0; i <= n; i++) {
far[i] = fa[i] = dep[i] = 0, G[i].clear();
for (LL j = 0; j <= logs; j++) pre[i][j] = 0;
}
}
void ins(LL u, LL v, LL c) {
en++, ed[en] = (data){v, c}, G[u].pb(en);
en++, ed[en] = (data){u, c}, G[v].pb(en);
}
void dfs(LL u, LL pa) {
dep[u] = dep[pa] + 1, fa[u] = pa, pre[u][0] = pa;
for (LL i = 1; i <= logs; i++) pre[u][i] = pre[pre[u][i - 1]][i - 1];
for (LL i = 0; i < (LL)G[u].size(); i++) {
LL v = ed[G[u][i]].v, wi = ed[G[u][i]].wi;
if (v != pa) {
far[v] = far[u] + wi;
dfs(v, u);
}
}
}
LL getlca(LL a, LL b) {
if (dep[a] < dep[b]) swap(a, b);
for (LL i = logs; i >= 0; i--) if (dep[pre[a][i]] >= dep[b]) a = pre[a][i];
if (a == b) return a;
for (LL i = logs; i >= 0; i--) if (pre[a][i] != pre[b][i]) a = pre[a][i], b = pre[b][i];
return pre[a][0];
}
LL dist(LL u, LL v) {
LL lca = getlca(u, v);
return far[u] + far[v] - 2 * far[lca];
}
LL pc(LL u, LL k) {
LL dt = dep[u] - k + 1;
for (LL i = logs; i >= 0; i--) if (dep[pre[u][i]] >= dt) u = pre[u][i];
return u;
}
LL kth(LL u, LL v, LL w) {
LL lca = getlca(u, v);
LL dt = dep[u] - dep[lca];
if (dt + 1 >= w) {
return pc(u, w);
} else return pc(v, dep[u] + dep[v] - 2 * dep[lca] - w + 2);
}
void solve() {
scanf("%lld", &n);
clean();
for (LL x, y, c, i = 1; i < n; i++) {
scanf("%lld%lld%lld", &x, &y, &c);
ins(x, y, c);
}
dfs(1, 0);
char s[10];
while (true) {
scanf("%s", s);
if (s[1] == 'O') break;
if (s[1] == 'I') {
LL u, v;
scanf("%lld%lld", &u, &v);
printf("%lld\n", dist(u, v));
} else {
if (s[1] == 'T') {
LL u, v, k;
scanf("%lld%lld%lld", &u, &v, &k);
printf("%lld\n", kth(u, v, k));
}
}
}
}
int main() {
LL T; scanf("%lld", &T);
while (T--) solve();
return 0;
}

------ 本文结束 ------