题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1787
并不是直接求三个点的LCA，因为要保证三个点到终点的距离和最小，所以稍微想一下就会看出，对于三个点两两的LCA，一定有某两个LCA是相等的，那么另一个LCA就是我们要选中的终点
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<bits/stdc++.h> #define MAXN 500050 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } int n,m,fa[MAXN][20],deep[MAXN]; vector<int>v[MAXN]; void dfs(int x){ for(int i=1; i<20; i++)fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=0; i<v[x].size(); i++){ int to=v[x][i]; if(to==fa[x][0])continue; deep[to]=deep[x]+1; fa[to][0]=x; dfs(to); } } inline int lca(int x,int y){ if(deep[x]<deep[y])swap(x,y); int num=deep[x]-deep[y]; for(int i=19; i>=0; i--){ if(num>=(1<<i)){ num-=(1<<i); x=fa[x][i]; } } for(int i=19; i>=0; i--){ if(fa[x][i]!=fa[y][i]){ x=fa[x][i]; y=fa[y][i]; } } if(x!=y)x=fa[x][0]; return x; } int main(){ n=rd(),m=rd(); for(int i=1; i<n; i++){ int x=rd(),y=rd(); v[x].push_back(y); v[y].push_back(x); } dfs(1); while(m--){ int x=rd(),y=rd(),z=rd(); int xx=lca(x,y),yy=lca(x,z),zz=lca(y,z); if(xx==yy && yy==zz)printf("%d %d\n",xx,deep[x]+deep[y]+deep[z]-deep[xx]*3); else if(xx==yy)printf("%d %d\n",zz,deep[x]+deep[y]+deep[z]-deep[zz]-deep[xx]*2); else if(xx==zz)printf("%d %d\n",yy,deep[x]+deep[y]+deep[z]-deep[yy]-deep[xx]*2); else if(yy==zz)printf("%d %d\n",xx,deep[x]+deep[y]+deep[z]-deep[xx]-deep[yy]*2); } return 0; } |
