倍增50分,8~18没过 SOS
查看原帖
倍增50分,8~18没过 SOS
341864
sgxsz楼主2024/9/5 21:06
#include<bits/stdc++.h>
using namespace std;

inline int read(){
	register int x=0,ch=getchar();
	while(ch<'0'||ch>'9')	ch=getchar();
	while(ch<='9'&&ch>='0'){  x=(x<<1)+(x<<3)+(ch^48);	ch=getchar();  }
	return x;
}
int tot,head[300000],to[500000],last[500000];
inline void add(int x,int y){
	to[++tot]=y;  last[tot]=head[x];  head[x]=tot;
	to[++tot]=x;  last[tot]=head[y];  head[y]=tot;
}
int n,k;
int sd[300000],st[300000][20];
inline void sdycl(int x){
	register int i,t=sd[x];
	for(i=head[x];i;i=last[i]){
		if(sd[to[i]])	continue;
		sd[to[i]]=t+1;	st[to[i]][0]=x;
		sdycl(to[i]);
	}
}
inline void stycl(){
	register int i,j;
	for(i=1;i<=log2(n);i++)
		for(j=2;j<=n;j++)
			st[j][i]=st[st[j][i-1]][i-1];
}
int f[300000],a[300000];
inline void bfs(){
	queue<int>q;
	register int i,j,t;
	for(i=1;i<=k;i++){
		q.push(a[i]);	f[a[i]]=0;
	}
	while(q.size()){
		t=q.front();	q.pop();
		for(i=head[t];i;i=last[i]){
			if(f[to[i]]!=1e8)	continue;
			f[to[i]]=f[t]+1;
			q.push(to[i]);
		}
	}
}
inline int tiao(int x,int d){
	for(int i=log2(n);i>=0;i--)
		if(sd[st[x][i]]>=d)	x=st[x][i];
	return x;
}
inline int find(int x,int y){
	if(x==y)	return 0;
	int len=0;
	for(int i=log2(n);i>=0;i--){
		if(st[x][i]!=st[y][i]){
			x=st[x][i];	y=st[y][i];
			len+=(1<<i);
		}
	}
	len++;
	return len<<1;
}

int main()
{
	register int i,j,q,x,y;
	cin>>n>>k>>q;
	for(i=1;i<n;i++)	add(read(),read());
	sd[1]=1;	st[1][0]=1;
	sdycl(1);	stycl();
	
	for(i=1;i<=k;i++)	a[i]=read();
	for(i=1;i<=n;i++)	f[i]=1e8;
	bfs();
	
	int len1,len2,t;
	while(q--){
		x=read();	y=read();
		len1=f[x]+f[y];
		
		if(sd[x]<sd[y])			len2=sd[y]-sd[x],y=tiao(y,sd[x]);
		else if(sd[x]>sd[y])	len2=sd[x]-sd[y],x=tiao(x,sd[y]);
		len2+=find(x,y);
		
		printf("%d\n",min(len1,len2));
	}
	return 0;
}
2024/9/5 21:06
加载中...