桂林电子科技大学第三届ACM程序设计竞赛 D题

链接：https://ac.nowcoder.com/acm/contest/558/D
来源：牛客网
小猫在研究树。
小猫在研究树上的距离。
给定一棵N个点的树，每条边边权为1。
Q次询问，每次给定a,b,c，请你输出a到b的路径上离c最近的点的编号。
题意：给你一棵树，然后有Q次询问。每次给出树上a, b, c三个节点。
输出a到b的路径上离c最近的点的编号
思路：LCA
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
int head[maxn], tot;
struct Edge {
    int u, v, next;
}edge[maxn];
int father[maxn], depth[maxn], size[maxn], son[maxn], top[maxn];
int L[maxn], R[maxn], Index;
void init() {
    memset(head, -1, sizeof(head));
    tot = 1;
}
void add(int u, int v) {
    edge[++tot].u = u; edge[tot].v = v;
    edge[tot].next = head[u];
    head[u] = tot;
}
void dfs1(int u, int fa) {
    size[u] = 1;
    son[u] = 0;
    father[u] = fa;
    depth[u] = depth[fa] + 1;
    int maxson = -1;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int to = edge[i].v;
        if (to == fa) {
            continue;
        }
        dfs1(to, u);
        size[u] += size[to];
        if (size[to] > maxson) {
            maxson = size[to];
            son[u] = to;
        }
    }
}
void dfs2(int u, int topf) {
    top[u] = topf;
    L[u] = R[u] = ++Index;
    if (son[u]) {
        dfs2(son[u], topf);
    }
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int to = edge[i].v;
        if (L[to] || to == son[u]) {
            continue;
        }
        dfs2(to, to);
    }
    R[u] = Index;
}
int LCA(int x, int y) {
    while (top[x] != top[y]) {
        if (depth[top[x]] < depth[top[y]]) {
            swap(x, y);
        }
        x = father[top[x]];
    }
    if (depth[x] > depth[y]) {
        return y;
    }
    return x;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    init();
    int n, m, s, u, v;
    scanf("%d", &n);
    for (int i = 1; i <= n - 1; i++) {
        scanf("%d%d", &u, &v);
        add(u, v); add(v, u);
    }
    dfs1(1, 1);
    dfs2(1, 1);
    int a, b, c;
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        int lca1 = LCA(a, b);
        int lca2 = LCA(a, c);
        int lca3 = LCA(b, c);
        int lca4 = LCA(lca2, c);
        int lca5 = LCA(lca3, c);
        int lca6 = LCA(lca1, c);
        if (depth[lca1] >= depth[c]) {
            printf("%d\n", lca1);  
            continue;
        }
        int res[5], tmp[5];
        res[0] = depth[a] + depth[c] - 2 * depth[lca2];
        res[1] = depth[b] + depth[c] - 2 * depth[lca3];
        res[2] = depth[lca2] + depth[c] - 2 * depth[lca4];
        if (depth[lca2] < depth[lca1]) {
            res[2] = 1e9;
        }
        res[3] = depth[lca3] + depth[c] - 2 * depth[lca5];
        if (depth[lca3] < depth[lca1]) {
            res[3] = 1e9;
        }
        res[4] = depth[lca1] + depth[c] - 2 * depth[lca6];
        tmp[0] = a; tmp[1] = b; tmp[2] = lca2; tmp[3] = lca3; tmp[4] = lca1;
        int ans = 1e9;
        for (int i = 0; i < 5; i++) {
            ans = min(ans, res[i]);
        }
        for (int i = 0; i < 5; i++) {
            if (ans == res[i]) {
                printf("%d\n", tmp[i]);
                break;
            }
        }
    }
    return 0;
}