题目简述
给定一棵树,节点之间的距离为 $1$,树上有 $k$ 个传送门,可以从一个传送门瞬间传送到另一个传送门,有 $q$ 此询问,问 $u$ 和 $v$ 之间的最短距离是多少。
题目分析
首先考虑没有传送门,我们可以直接求两个点的 LCA,再用高度容斥计算即可。
如果有传送门,那么有用与不用两种选择,如果用的话,那么最优的方法一定是 $u$ 到离它最近的传送门的距离,再加上 $v$ 到离它最近的传送门的距离,这个可以直接用 bfs 预处理,最后在与不用的法案比较一下。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,k,Q,deep[N],fa[N][40],dis[N];
vector<int> G[N];
queue<int> q;
void dfs(int u,int father)
{
deep[u]=deep[father]+1;
fa[u][0]=father;
for(int i=1;i<=30;i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int v:G[u])
if(v!=father) dfs(v,u);
return;
}
int lca(int u,int v)
{
if(deep[u]<deep[v])
swap(u,v);
int temp=deep[u]-deep[v];
for(int i=0;i<=30;i++)
if(temp>>i&1)
u=fa[u][i];
if(u==v) return u;
for(int i=30;i>=0;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
void bfs()
{
while(!q.empty())
{
int u=q.front();q.pop();
for(int v:G[u])
if(dis[v]==dis[0])
dis[v]=dis[u]+1,q.push(v);
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k>>Q;
memset(dis,0x3f,sizeof dis);
for(int x=0,y=0,i=1;i<n;i++)
{
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1,0);
for(int x=0,i=1;i<=k;i++)
cin>>x,q.push(x),dis[x]=0;
bfs();
for(int x=0,y=0,i=1;i<=Q;i++)
cin>>x>>y,cout<<min(dis[x]+dis[y],deep[x]+deep[y]-2*deep[lca(x,y)])<<"\n";
return 0;
}
标签:int,题解,bfs,fa,传送门,P10289,push,GESP,dis
From: https://www.cnblogs.com/zhuluoan/p/18134475