求助
  • 板块灌水区
  • 楼主zengxi2111
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/12/2 09:09
  • 上次更新2023/12/2 11:40:14
查看原帖
求助
730134
zengxi2111楼主2023/12/2 09:09
#include<bits/stdc++.h>
using namespace std;
vector<int> to[100000];
int sons[100000];
int shen[100000];
bool flag[100000];
int fa[100000][17];
vector<int> ans;
int a;
void LCA()
{
	for(int i=1;i<=a;i++)
	{
		for(int j=2;j<=17;j++)
		{
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	return ;
}
int o;
int dg(int x,int y,int z)
{
	if(z==0)return 200000;
	int o1=20;
	for(int i=1;i<=z;i++)
	{
		if(fa[x][i]==fa[y][i])
		{
			o1=i;
			break;
		}
	}
	if(o1==20) return 200000;
	if(dg(fa[x][o1-1],fa[y][o1-1],z-2)==200000)return fa[x][o1];
	else return dg(fa[x][o1-1],fa[y][o1-1],z-2);
}
int mete(int p,int q)
{
	int summ=shen[p]+shen[q];
	if(shen[q]>shen[p])swap(p,q);
	while(shen[p]>shen[q])
	{
		for(int i=1;i<=17;i++)
		{
			if(shen[fa[q][i]]>shen[p])
			{
				o=i-1;
				break;
			}
			q=fa[q][o];
		}
	}
	return summ-shen[dg(p,q,17)];
}
int main(){	
	cin>>a;
	queue<int> d;
	int n,m;
	sons[1]=0; 
	int people=0;
	for(int i=1;i<=a;i++)
	{
		fa[i][1]=i;
		sons[i]=-1;
		shen[i]=100000;
	}
	for(int i=1;i<a;i++)
	{
		cin>>n>>m;
		sons[n]++;
		sons[m]++;
		to[n].push_back(m); 
		to[m].push_back(n); 
	}
	d.push(1);
	flag[1]=1;
	shen[1]=0;
	int l;
	int i=1;
	while(i<=a)
	{
		l=d.front();
		for(int j=1;j<=sons[l];j++)
		{
			if(flag[to[l][j]]==0)
			{
				fa[to[l][j]][1]=l;
				i++;
				d.push(to[l][j]);
				flag[to[l][j]]=1;
				shen[to[l][j]]=shen[l]+1;
			}
		}
		d.pop();
	}
	LCA();
	int q;
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		cin>>n>>m;
		ans.push_back(mete(n,m));
	} 
	for(int i=1;i<=q;i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}
2023/12/2 09:09
加载中...