树上倍增#8#9WA求调
查看原帖
树上倍增#8#9WA求调
1060212
Saturation楼主2024/8/15 14:50
#include<bits/stdc++.h>
using namespace std;
const int N=1100000;
int n,m;
int e[N],h[N],ne[N],idx;
int f[N][30];
int d[N];
void add(int x,int y)
{
	e[++idx]=y;
	ne[idx]=h[x];
	h[x]=idx++;
}
void dfs(int u,int dep)
{
	d[u]=dep;
	for(int i=h[u];~i;i=ne[i])
	{
		int v=e[i];
		if(!d[v])
		{
			f[v][0]=u;
			dfs(v,dep+1);
		}
	}
}
void build()
{
	for(int j=1;j<=log2(n);j++)
	{
		for(int i=1;i<=n;i++)
		{
			if(d[i]>(1<<j))
			{
				f[i][j]=f[f[i][j-1]][j-1];
			}
		}
	}
}
int lca(int x,int y)
{
	if(d[x]<d[y])
	{
		swap(x,y);
	}
	for(int i=log2(n);i>=0;i--)
	{
		if(d[f[x][i]]>=d[y])
		{
			x=f[x][i];
		}
	}
	if(x==y)
	{
		return x;
	}
	for(int i=log2(n);i>=0;i--)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
int dist(int x,int y)
{
	return d[x]+d[y]-2*d[lca(x,y)];
}
int in()
{
	 int ans=0,ff=1;
	 int c=getchar();
	 for(;!isdigit(c);c=getchar())
	 {
		 if(c=='-')
		 {
			ff=-1;
		 }
	 }
	 for(;isdigit(c);c=getchar())
	 {
		 ans=ans*10+c-'0';
	 }
	 return ans*ff;
}
void out(int x)
{
	 if(x<0)
	 {
		 putchar('-');
		 x=-x;
	 }
	 if(x>=10)
	 {
		 out(x/10);
	 }
	 putchar(x%10+'0');
}
int main()
{
	memset(h,-1,sizeof h);
	n=in();
	m=in();
	for(int i=1;i<=n-1;i++)
	{
		int x=in(),y=in();
		add(x,y);
		add(y,x);
	}
	dfs(1,1);
	build();
	for(int i=1;i<=m;i++)
	{
		int x=in(),y=in(),z=in();
		int xy=lca(x,y),yz=lca(y,z),xz=lca(x,z);
		int a=dist(x,xy)+dist(y,xy)+dist(z,xy);
		int b=dist(x,yz)+dist(y,yz)+dist(z,yz);
		int c=dist(x,xz)+dist(y,xz)+dist(z,xz);
		int ans1=min(min(a,b),c);
//		cout<<xy<<' '<<xz<<' '<<yz<<'\n';
		if(ans1==a)
		{
			out(xy);
		}
		else if(ans1==b)
		{
			out(yz);
		}
		else
		{
			out(xz);
		}
		printf(" ");
		out(ans1);
		puts("");
	}
	return 0;
}


2024/8/15 14:50
加载中...