1 条题解

  • 0
    @ 2024-6-2 10:47:09
    #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

    [GESP样题 八级] 小杨的旅游

    信息

    ID
    783
    时间
    1000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    7
    已通过
    4
    上传者