1 条题解
-
0
#include <bits/stdc++.h> #define ll long long using namespace std; const int N=200005; int n,m,k,s,t,Q,f[N][21],de[N],d[N]; queue<int> q; vector<int> e[N]; void dfs(int u){ for (int v:e[u]){ if (v!=f[u][0]){ f[v][0]=u; de[v]=de[u]+1; dfs(v); } } } int lca(int u,int v){ if (de[u]<de[v]) swap(u,v); for (int k=de[u]-de[v],o=0;k;k>>=1,++o) if (k&1) u=f[u][o]; if (u==v) return u; for (int j=20;j>=0;--j) if (f[u][j]!=f[v][j]) u=f[u][j],v=f[v][j]; return f[u][0]; } int main(){ freopen("in.txt","r",stdin); cin>>n>>k>>Q; for (int i=1;i<n;++i){ cin>>s>>t; e[s].push_back(t); e[t].push_back(s); } dfs(1); for (int j=1;j<=20;++j) for (int i=1;i<=n;++i) f[i][j]=f[f[i][j-1]][j-1]; memset(d,0x3f,sizeof(d)); for (int i=1;i<=k;++i) cin>>s,d[s]=0,q.push(s); while (!q.empty()){ int u=q.front(); q.pop(); for (int v:e[u]){ if (d[v]>d[u]+1){ d[v]=d[u]+1; q.push(v); } } } int u,v; while (Q--){ cin>>u>>v; int p=lca(u,v); cout<<min(de[u]+de[v]-2*de[p],d[u]+d[v])<<"\n"; } }
- 1
信息
- ID
- 783
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 7
- 已通过
- 4
- 上传者