P4281一直不过有点绝望
查看原帖
P4281一直不过有点绝望
293127
doitagain楼主2021/6/1 09:43
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAXN 500005
using namespace std;
vector<int>s[MAXN];
int n,m,lg[MAXN],fa[MAXN][20],dep[MAXN];
struct hh
{
	int pos,d;
}fw[5];
int abs(int x)
{
	if (x<0) return -x;
	return x;
}
void start1()
{    
   int t=2;
	lg[0]=0,lg[1]=0;
	for (int i=2;i<=n;i++)
	{
		if (i==t)
		{
			t=t*2;
			lg[i]=lg[i-1]+1;
		}
		else 
		lg[i]=lg[i-1];
	}
}
void start2(int x,int Fa)
{
	fa[x][0]=Fa;
	dep[x]=dep[Fa]+1;
	for (int i=1;i<=dep[lg[dep[x]]];i++)
	fa[x][i]=fa[fa[x][i-1]][i-1];
	for (int i=0;i<s[x].size();i++)
	if (s[x][i]!=Fa)
	start2(s[x][i],x);
	return ;
}
int LCA(int x,int y)
{
	if (dep[x]<dep[y])
	swap(x,y);
	while (dep[x]>dep[y])
	x=fa[x][lg[dep[x]-dep[y]]];
	if (x==y)
	return x;
	for (int i=lg[dep[x]];i>=0;i--)
	{
		if (fa[x][i]!=fa[y][i])
		  {
		  	x=fa[x][i];
		  	y=fa[y][i];
		  }
	}
	return fa[x][0];
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		s[x].push_back(y);
		s[y].push_back(x);
	}
	start1();
	dep[0]=0;
	start2(1,0);
	for (int i=1;i<=m;i++)
	{
	     int a1,a2,a3,t1,t2,t3,t;
	     scanf("%d%d%d",&a1,&a2,&a3);
		 t1=LCA(a1,a2);
		 t2=LCA(a2,a3);
		 t3=LCA(a1,a3);
		 if (t1==t2)
		 {
		 	t=t3;
		 
		  } 
		  if (t2==t3)
		   {
		   	t=t1;
		   	
		   }
		   if (t1==t3)
		   {
		   	t=t2;
		   }
		   	printf("%d %d\n",t,dep[a1]+dep[a2]+dep[a3]-dep[t1]-dep[t2]-dep[t3]);
		   	
	}
	return 0;
}
2021/6/1 09:43
加载中...