目录
显示
题目链接
https://www.luogu.org/problem/P4281
题解
先考虑两个点的情况,显然,树上两点间的最短简单路径一定过这两个点的 LCA。
接下来把结论推广到三个点。我们对这三个点两两求一遍 LCA,会发现其中两个 LCA 位于同一个点。
那么我们将集合点设置为那个单独的 LCA 位置就可以了。
为什么这样是正确的呢?事实上,那个单独的 LCA 位置也是三个 LCA 位置最深的一个,这也就确保了移动距离会尽可能小。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int v,next; }e[1000005]; int head[500005],dep[500005],cnt,fa[500005][25],path[500005]; void addedge(int u,int v) { e[++cnt].v=v; e[cnt].next=head[u]; head[u]=cnt; } void dfs(int cur,int d) { dep[cur]=d; path[d]=cur; for(int i=head[cur];i;i=e[i].next) if(dep[e[i].v]==-1)dfs(e[i].v,d+1); for(int i=0;(1<<i)<=d;i++) fa[cur][i]=path[d-(1<<i)]; path[d]=0; return; } int lca(int x,int y) { if(dep[x]>dep[y])swap(x,y); for(int i=20;i>=0;i--) if(dep[y]-dep[x]-(1<<i)>=0)y=fa[y][i]; if(x==y)return x; for(int i=20;i>=0;i--) if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } return fa[x][0]; } int calc_dep(int x,int y) { return dep[x]+dep[y]-2*dep[lca(x,y)]; } int main() { int n,m; scanf("%d%d",&n,&m); memset(dep,-1,sizeof(dep)); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } dfs(1,0); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); int l1=lca(x,y),l2=lca(x,z),l3=lca(y,z); int ans; if(l1==l2)ans=l3; else if(l1==l3)ans=l2; else ans=l1; printf("%d %d\n",ans,calc_dep(ans,x)+calc_dep(ans,y)+calc_dep(ans,z)); } return 0; }