[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=1832
[算法]
最近公共祖先
[代码]
#include<bits/stdc++.h> using namespace std; #define MAXN 500010 #define MAXLOG 20 struct edge { int to,nxt; } e[MAXN << 1]; int i,n,m,u,v,a,b,c,tot,l1,l2,l3,t; int head[MAXN],depth[MAXN]; int anc[MAXN][MAXLOG]; inline void addedge(int u,int v) { tot++; e[tot] = (edge){v,head[u]}; head[u] = tot; } inline void dfs(int u) { int i,v; for (i = 1; i < MAXLOG; i++) { if (depth[u] < (1 << i)) continue; anc[u][i] = anc[anc[u][i - 1]][i - 1]; } for (i = head[u]; i; i = e[i].nxt) { v = e[i].to; if (v != anc[u][0]) { depth[v] = depth[u] + 1; anc[v][0] = u; dfs(v); } } } inline int lca(int u,int v) { int i,t; if (depth[u] > depth[v]) swap(u,v); t = depth[v] - depth[u]; for (i = 0; i < MAXLOG; i++) { if (t & (1 << i)) v = anc[v][i]; } if (u == v) return u; for (i = MAXLOG - 1; i >= 0; i--) { if (anc[u][i] != anc[v][i]) { u = anc[u][i]; v = anc[v][i]; } } return anc[u][0]; } inline int dist(int x,int y) { return depth[x] + depth[y] - 2 * depth[lca(x,y)]; } int main() { scanf("%d%d",&n,&m); for (i = 1; i < n; i++) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } dfs(1); for (i = 1; i <= m; i++) { scanf("%d%d%d",&a,&b,&c); l1 = lca(a,b); l2 = lca(b,c); l3 = lca(a,c); if (l1 == l2) t = l3; else if (l2 == l3) t = l1; else t = l2; printf("%d %d ",t,dist(a,t) + dist(b,t) + dist(c,t)); } return 0; }