【题解】Luogu P10289 [GESP样题 八级] 小杨的旅游

思路

首先不难发现是树上最短路，使用最近公共祖先求解。令 \(u,v\) 的 LCA 为 \(k\)，答案为 \(dep_u-dep_k+dep_v-dep_k\)。也可以在向上跳的同时累加步数。

然后考虑传送门，只要从 \(u,v\) 出发走到各自距离最近的传送门即可。使用 BFS 找到每个点距离最近的传送门。

最后答案为两者中较小值。

实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int INF=1e9;
int n,k,q,D;
int h[N],tot;
int fa[N][20],dep[N];
int f[N];
bool t[N],qvis[N];
struct Node{int to,nxt;
}e[2*N];
struct Qnode{int u,step;
};
queue<Qnode> Q;
void Add(int u,int v){tot++;e[tot].to=v;e[tot].nxt=h[u];h[u]=tot;
}
void bfs(){while(!Q.empty()){Qnode front=Q.front();int u=front.u,st=front.step;Q.pop();for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;if(!qvis[v]){Q.push(Qnode{v,st+1});qvis[v]=1;f[v]=st+1;}}}
}
void dfs(int u,int cur,int fath){fa[u][0]=fath;D=max(D,cur);dep[u]=cur;for(int i=1;i<=log(dep[u])/log(2);i++) fa[u][i]=fa[fa[u][i-1]][i-1];for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;if(v!=fath) dfs(v,cur+1,u);}
}
int LCA(int a,int b){if(dep[a]<dep[b]) swap(a,b);int dis=0;for(int i=log(D)/log(2);i>=0;i--){if(dep[fa[a][i]]>=dep[b]){a=fa[a][i];dis+=(1<<i);} }if(a==b) return dis;for(int i=log(D)/log(2);i>=0;i--){if(fa[a][i]!=fa[b][i]){a=fa[a][i];b=fa[b][i];dis+=2*(1<<i);}}dis+=2;return dis;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);memset(f,0x3f,sizeof(f));cin>>n>>k>>q;for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;Add(u,v),Add(v,u);}for(int i=1;i<=k;i++){int x;cin>>x;Q.push((Qnode){x,0});t[x]=1,qvis[x]=1,f[x]=0;}bfs();dfs(1,1,0);for(int i=1;i<=q;i++){int u,v;cin>>u>>v;cout<<min(LCA(u,v),f[u]+f[v])<<'\n';}return 0;
}

时间复杂度 \(O(n\log n)\)。