1 条题解

  • 0
    @ 2023-12-17 14:21:16
    #include<bits/stdc++.h>
    using namespace std;
    int n,q,f[100005][25],lg[100005],dep[100005];
    vector<int>e[100005];
    void dfs(int u,int fa)
    {
    	dep[u]=dep[fa]+1,f[u][0]=fa;
    	for(int i=1;i<=lg[dep[u]];i++)f[u][i]=f[f[u][i-1]][i-1];
    	for(int i=0;i<e[u].size();i++){
    		if(e[u][i]^fa)dfs(e[u][i],u);
    	}
    }
    int lca(int x,int y)
    {
    	if(dep[x]<dep[y])swap(x,y);
    	while(dep[x]>dep[y])x=f[x][lg[dep[x]-dep[y]]];
    	if(x==y)return x;
    	for(int i=lg[x];i>=0;i--)
    	{
    		if(f[x][i]^f[y][i])x=f[x][i],y=f[y][i];
    	}
    	return f[x][0];
    }
    int main()
    {
    	cin>>n;
    	for(int i=1,x,y;i<n;i++)
    	{
    		cin>>x>>y;
    		e[x].push_back(y),e[y].push_back(x);
    	}
    	for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
    	cin>>q;
    	dfs(1,0);
    	for(int i=1,x,y,t;i<=q;i++)
    	{
    		cin>>x>>y;
    		t=lca(x,y);
    		cout<<dep[x]-dep[t]+dep[y]-dep[t]<<endl;
    	}
    	return 0;
    }
    
    
    • 1

    信息

    ID
    541
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    (无)
    递交数
    1
    已通过
    1
    上传者