1787: [Ahoi2008]Meet 紧急集合
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
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
2 5
4 1
6 0
HINT
题解：
n-1条边，很明显这是一棵树
那么题目就是求3个点的LCA
我们将3个点x,y,z分别求出x,y的LCA，设为a，x,z的为b，y,z的为c
则a,b,c 3个点中必有两个相等，答案就是另外一个（自已画画图就知道了）
那么再求3个点到它的距离就OK了。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int n,m,i,j,x,y,z,a,b,c,t,p[],r[],f[][];
int tot,head[],Next[],to[];
void add(int x,int y)
{
tot++;
to[tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
void dfs(int x)
{
int i;
for(i=head[x];i!=-;i=Next[i])
if(p[to[i]]==)
{
p[to[i]]=;
r[to[i]]=r[x]+;
f[to[i]][]=x;
dfs(to[i]);
}
}
int LCA(int a,int b)
{
int i;
if(r[a]<r[b]) swap(a,b);
for(i=;i>=;i--)
if(f[a][i]&&r[f[a][i]]>=r[b]) a=f[a][i];
if(a==b) return a;
for(i=;i>=;i--)
if(f[a][i]&&f[b][i]&&f[a][i]!=f[b][i])
{
a=f[a][i];
b=f[b][i];
}
return f[a][];
}
int dis(int x,int y)
{
int a=LCA(x,y);
return r[x]+r[y]-*r[a];
}
int main()
{
scanf("%d%d",&n,&m);
for(i=;i<=n;i++)
head[i]=-;
for(i=;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
p[]=;
r[]=;
dfs();
for(j=;j<=;j++)
for(i=;i<=n;i++)
f[i][j]=f[f[i][j-]][j-];
for(i=;i<=m;i++)
{
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;
printf("%d %d\n",t,dis(x,t)+dis(y,t)+dis(z,t));
}
return ;
}