Codeforces 832D(LCA)

Codeforces 832D
分6种情况求两条路径交即可。
路径交的求法:
设$d(a, b)$为$a$到$b$的距离,则路径交为$\frac{d(a, c) +d(b, c) - d(a, b)}{2} +1$
由于三个点的$lca$一定不会一一不同(即$lca(a,b), lca(a, c), lca(b, c)$一定不会完全相同),所以以上公式是正确的

Codeforces Submission

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5, logs = 19;
vector<int> G[MAXN];
int n, q, dep[MAXN], pre[MAXN][logs + 1];
void dfs(int u, int pa) {
dep[u] = dep[pa] + 1, pre[u][0] = pa;
for (int i = 1; i <= logs; i++) pre[u][i] = pre[pre[u][i - 1]][i - 1];
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (v != pa) {
dfs(v, u);
}
}
}
int getLCA(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
for (int i = logs; i >= 0; i--) if (dep[pre[a][i]] >= dep[b]) a = pre[a][i];
if (a == b) return a;
for (int i = logs; i >= 0; i--) if (pre[a][i] != pre[b][i]) a = pre[a][i], b = pre[b][i];
return pre[a][0];
}
int getdist(int a, int b) {
return dep[a] + dep[b] - 2 * dep[getLCA(a, b)];
}
int getAns(int a, int b, int c) {
return (getdist(a, c) + getdist(b, c) - getdist(a, b)) / 2 + 1;
}
void clean() {
for (int i = 1; i <= n; i++) {
G[i].clear(), dep[i] = 0;
for (int j = 0; j <= logs; j++) pre[i][j] = 0;
}
}
void solve() {
clean();
for (int p, i = 2; i <= n; i++) {
scanf("%d", &p);
G[i].push_back(p), G[p].push_back(i);
}
dfs(1, 0);
while (q--) {
int a, b, c, ans = 0;
scanf("%d%d%d", &a, &b, &c);
ans = max(ans, getAns(a, b, c));
ans = max(ans, getAns(a, c, b));
ans = max(ans, getAns(b, c, a));
ans = max(ans, getAns(b, a, c));
ans = max(ans, getAns(c, a, b));
ans = max(ans, getAns(c, b, a));
printf("%d\n", ans);
}
}
int main() {
scanf("%d%d", &n, &q), solve();
return 0;
}

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