Description
Input
Output
Sample Input
6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6
Sample Output
5 2
2 5
4 1
6 0
HINT
題解
lca運用。
求三個結點到一個結點距離之和最小的結點以及距離和。
求出給出三點中，每兩個點的lca，其中有兩個相同，答案則為另一個。（因為是樹）
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,zz=0,head[500002];
struct bian
{int to,nx;} e[1000002];
int h[500002],fa[500002][20],vis[500002];
void insert(int x,int y)
{zz++; e[zz].to=y; e[zz].nx=head[x]; head[x]=zz;
zz++; e[zz].to=x; e[zz].nx=head[y]; head[y]=zz;
}
void dfs(int x)
{
vis[x]=1;
for(int i=1;i<=18;i++)
{if(h[x]<(1<<i)) break;
fa[x][i]=fa[fa[x][i-1]][i-1];
}
int i=head[x];
while(i)
{if(!vis[e[i].to])
{h[e[i].to]=h[x]+1;
fa[e[i].to][0]=x;
dfs(e[i].to);
}
i=e[i].nx;
}
}
int lca(int x,int y)
{
if(h[x]<h[y]) swap(x,y);
int dis=h[x]-h[y];
for(int i=0;i<=18;i++)
{if((1<<i)&dis) x=fa[x][i];}
for(int i=18;i>=0;i--)
{if(fa[x][i]!=fa[y][i])
{x=fa[x][i]; y=fa[y][i];}
}
if(x==y) return x;
else return fa[x][0];
}
int cal(int x,int y)
{int t=lca(x,y); return h[x]+h[y]-2*h[t];}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{int x,y;
scanf("%d%d",&x,&y);
insert(x,y);
}
dfs(1);
for(int i=1;i<=m;i++)
{int x,y,z,a,b,c,t,ans;
scanf("%d%d%d",&x,&y,&z);
a=lca(x,y); b=lca(x,z); c=lca(y,z);
if(a==b) t=c;
else if(b==c) t=a;
else t=b;
ans=cal(x,t)+cal(y,t)+cal(z,t);
printf("%d %d\n",t,ans);
}
return 0;
}