Rockdu's Blog

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<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=500000+100;
const int max2=20;
struct edge
{
	int v;
	int next;
}e[maxn*2];

int head[maxn];
int p[maxn][max2+5];
int d[maxn];
int edc;
int n,m;

void adde(int u,int v)
{
	e[++edc].v=v;
	e[edc].next=head[u];
	head[u]=edc;
}

void dfs(int now,int fa)
{
	d[now]=d[fa]+1;
	p[now][0]=fa;
	for(int i=1;i<=max2;i++)
		p[now][i]=p[p[now][i-1]][i-1];
	
	for(int i=head[now];i!=-1;i=e[i].next)
	{
		int v=e[i].v;
		if(v!=fa)
			dfs(v,now);
	}
}

int lca(int a,int b)
{
	if(d[a]<d[b]) swap(a,b);
	for(int i=max2;i>=0;i--)
		if(d[a]-(1<<i)>=d[b])
			a=p[a][i];
	if(a==b)
		return a;
	for(int i=max2;i>=0;i--)
		if(p[a][i]!=p[b][i])
		{
			a=p[a][i];
			b=p[b][i];
		}
	return p[a][0];
}

int main()
{
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n-1;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			adde(a,b);
			adde(b,a);
		}
	dfs(1,0);
	for(int i=1;i<=m;i++)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			int t1=lca(a,b);
			int t2=lca(b,c);
			int t3=lca(a,c);
			if(t1==t2)
			{
				printf("%d %d\n",t3,d[t3]-d[t1]+d[b]-d[t1]+d[a]-d[t3]+d[c]-d[t3]);
				continue;
			}
			if(t2==t3)
			{
				printf("%d %d\n",t1,d[t1]-d[t2]+d[b]-d[t2]+d[a]-d[t1]+d[c]-d[t1]);
				continue;
			}
			if(t3==t1)
				printf("%d %d\n",t2,d[t2]-d[t3]+d[b]-d[t3]+d[a]-d[t2]+d[c]-d[t2]);
		}
	return 0;
}