树剖LCA会TLE?
查看原帖
树剖LCA会TLE?
643818
I_AK_CTS楼主2024/11/5 19:29
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5+5;
vector<int> G[N];
int n,k,q,tp[N],fa[N],dep[N],hson[N],sz[N],dis[N];
void dfs1(int x)
{
	for(auto v:G[x])
	{
		if(dep[v]) continue;
		dep[v]=dep[x]+1;
		fa[v]=x;
		dfs1(v);
		sz[x]+=sz[v];
		if(hson[x]==-1||sz[hson[x]]<sz[v])
			hson[x]=v;
	}
}
void dfs2(int x,int t)
{
	tp[x]=t;
	if(hson[x]==-1) return ;
	dfs2(hson[x],t);
	for(auto v:G[x])
		if(v!=hson[x]&&v!=fa[x]) dfs2(v,v);
}
int LCA(int x,int y)
{
	while(tp[x]!=tp[y])
	{
		if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
		x=fa[tp[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	return x;
}
queue<int> Q;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k>>q;
	memset(dis,0x3f,sizeof(dis));
	for(int i=1,u,v;i<n;i++)
	{
		cin>>u>>v;
		G[u].pb(v),G[v].pb(u);
	}
	for(int i=1,x;i<=k;i++)
	{
		cin>>x;
		dis[x]=0;
		Q.push(x);
	}
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(auto v:G[x]) if(dis[v]==0x3f3f3f3f) dis[v]=dis[x]+1,Q.push(v);
	}
	dep[1]=1;
	memset(hson,-1,sizeof(hson));
	dfs1(1),dfs2(1,1);
	while(q--)
	{
		int u,v;
		cin>>u>>v;
		int L=LCA(u,v);
		cout<<min(dep[u]+dep[v]-dep[L]*2,dis[u]+dis[v])<<'\n';
	}
	return 0;
}
2024/11/5 19:29
加载中...