倍增lca50pts SOS
查看原帖
倍增lca50pts SOS
974005
shuaiqbr楼主2024/6/27 22:06
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int n,k,q1;
int e[N*2],h[N*2],ne[N*2],idx=1;
int chuan[N],deep[N],st[N][19];
int x,y,lca_m,t;
queue<int> q;
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
void dfs(int son,int father)
{
	deep[son]=deep[father]+1;
	st[son][0]=father;
	for(int i=1;i<=18;i++)
	{
		st[son][i]=st[st[son][i-1]][i-1];
	}
	for(int i=h[son];i!=0;i=ne[i])
	{
		int j=e[i];
		if(j!=father)
		{
			dfs(j,son);
		}
	}
	return;
}
int lca(int u,int v)
{
	int temp=u,step=0; 
	if(deep[u]<deep[v])
	{
		swap(u,v);
	}
	for(int i=18;i>=0;i--)
	{
		if(deep[st[u][i]]>=deep[v])
		{
			u=st[u][i];
		}
	}
	if(u==v) return u;
	for(int i=18;i>=0;i--)
	{
		if(st[u][i]!=st[v][i])
		{
			u=st[u][i],v=st[v][i];
		}
	}
	return st[u][0];
} 
int main(){
// 	memset(chuan,0x3f,sizeof(chuan));
//	cin>>n>>k>>q1;
	scanf("%d %d %d",&n,&k,&q1); 
	for(int i=1;i<=n;i++) chuan[i]=N;
	for(int i=1;i<=n-1;i++)
	{
//		cin>>x>>y;
		scanf("%d %d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=k;i++)
	{
		int c;
//		cin>>c;
		scanf("%d",&c);
		q.push(c); 
		chuan[c]=0;
	}
	while(q.size())
	{
		t=q.front();
		q.pop();
		for(int i=h[t];i!=0;i=ne[i])
		{
			int j=e[i];
			if(chuan[j]!=N)
			{
				q.push(j);
				chuan[j]=chuan[t]+1;
			}
		}
	}
	dfs(1,1);
	while(q1--)
	{
//		cin>>x>>y;
		scanf("%d %d",&x,&y);
		lca_m=lca(x,y);
//		cout<<min(deep[x]-deep[lca_m]+deep[y]-deep[lca_m],chuan[x]+chuan[y])<<endl;
		printf("%d\n",min(deep[x]-deep[lca_m]+deep[y]-deep[lca_m],chuan[x]+chuan[y]));
//		printf("%d %d\n",deep[x]-deep[lca_m]+deep[y]-deep[lca_m],chuan[x]+chuan[y]);
	}
} 

#2 #5 #20 TLE #4 #19 MLE #13 #14 #15 #16 #17 WA 求调

2024/6/27 22:06
加载中...