不难发现三个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); } }