Codeforces 832D(LCA)

Codeforces 832D
题意：给定一颗树$n$，并有$q$次询问，每次询问指定三个点$a，b，c$：意思是有两个人任选两个点作为各自起点，剩下的那个点作为终点，两个人各自从起点走向终点，求路径上重合的点数，现在要求在这三个点可能的选择方式中，求重合点数的最大值 (This solution has been updated in August 12th, 2018.)

分6种情况求两条路径交即可。
路径交的求法：
设$d(a, b)$为$a$到$b$的距离，则路径交为$\frac{d(a, c) +d(b, c) - d(a, b)}{2} +1$

Codeforces Submission

#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;
}