「bzoj1787 / 1832」「Ahoi2008」Meet 紧急集合 (LCA倍增)

BZOJ 1787
BZOJ 1832
题意：给一棵无权无根树，每次询问三元组$(x,y,z)$，求树上到$x,y,z$的距离最短的那个点，输出距离。
很容易想到就是三对$LCA$取最小值。
这里主要是想要讲的是树上三个点的三对$LCA$必有两个相同
然后其实这题答案就是那个不一样的那个$LCA$。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 500000 + 1, LOGS = 20;

    vector<int > G[MAXN];

    int n, m, dep[MAXN], pre[MAXN][LOGS + 1];

    void dfs(int u, int fa) {
        dep[u] = dep[fa] + 1, pre[u][0] = fa;
        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 != fa) dfs(v, u);
        }
    }
    int LCA(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 dist(int u, int v) {
        return (dep[u] - 1) + (dep[v] - 1) - 2 * (dep[LCA(u, v)] - 1);
    }
    int getans(int x, int y, int z, int gl) {
        return dist(x, gl) + dist(y, gl) + dist(z, gl);
    }

    void clean() {
        ms(dep, 0), ms(pre, 0);
    }
    int solve() {

        clean();
        scanf("%d%d", &n, &m);
        for (int x, y, i = 1; i < n; ++i) {
            scanf("%d%d", &x, &y);
            G[x].push_back(y), G[y].push_back(x);
        }

        dfs(1, 0);

        while (m--) {

            int x, y, z; scanf("%d%d%d", &x, &y, &z);
            int mind = 1000000000, pos = 0;

            int lca = LCA(x, y);
            int tmp = getans(x, y, z, lca);
            if (tmp < mind) mind = tmp, pos = lca;

            lca = LCA(y, z);
            tmp = getans(x, y, z, lca);
            if (tmp < mind) mind = tmp, pos = lca;

            lca = LCA(x, z);
            tmp = getans(x, y, z, lca);
            if (tmp < mind) mind = tmp, pos = lca;

            lca = LCA(LCA(x, y), z);
            tmp = getans(x, y, z, lca);
            if (tmp < mind) mind = tmp, pos = lca;

            printf("%d %d\n", pos, mind);

        }

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}