题解 | 聚会题解

不难发现三个LCA一定有两个重合，且一定是深度小的，但是深度大的那个点会更优（有两个点到它那里最优），那么找出深度大的那个lca就好了，它一定是公共点...，距离预处理深度即可。

#include <bits/stdc++.h>
#define ll long long
#define il inline
const ll inf = 1e18;

namespace io {

#define in(a) a = read()
#define out(a) write(a)
#define outn(a) out(a), putchar('\n')

#define I_int ll
inline I_int read() {
    I_int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
char F[200];
inline void write(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
}
#undef I_int

}
using namespace io;

using namespace std;

#define N 500010
int n = read(), m = read();
int lim, f[N][25], dep[N];
int head[N], cnt;
struct edge {
    int to, nxt;
}e[N<<1];

void ins(int u, int v) {
    e[++cnt] = (edge) {v, head[u]};
    head[u] = cnt; 
}

void dfs(int u) {
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to; if(v == f[u][0]) continue;
        f[v][0] = u; dep[v] = dep[u] + 1;
        for(int j = 1; j <= lim; ++j) f[v][j] = f[f[v][j-1]][j-1];
        dfs(v);
    }
}

int lca(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = lim; i >= 0; --i) if(dep[f[x][i]] >= dep[y]) x = f[x][i];
    if(x == y) return x;
    for(int i = lim; i >= 0; --i) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}

ll dis(int u, int v) {
    return dep[u] + dep[v] - 2ll * dep[lca(u, v)];
} 

int main() {
    for(int i = 1, x, y; i < n; ++i) in(x), in(y), ins(x, y), ins(y, x);
    lim = log(n) / log(2) + 1;
    dep[1] = 1; dfs(1); 
    for(int i = 1; i <= m; ++i) {
        int x = read(), y = read(), z = read();
        int t1 = lca(x, y), t2 = lca(x, z), t3 = lca(y, z), t;
        if(t1 == t2) t = t3; else if(t2 == t3) t = t1; else if(t1 == t3) t = t2; 
        ll ans = dis(x, t) + dis(y, t) + dis(z, t);
        out(t), putchar(' '), outn(ans);
    }
}