3 条题解

  • 1
    @ 2021-5-10 18:05:10

    因为题目告诉你了给出的是一棵树

    那么两点的简单路径就是两点到他们的最近公共祖先

    然后可以先选择 11 为根节点 ,然后求出每个节点的深度。

    又由于节点边的长度都为1,那么一个点的深度就是他到根节点的距离。

    这样两点 u,vu,v 之间简单路径长度就为 dep[u]+dep[v]-2*dep[LCA(u,v)]

    然后判断是否可行就是判断路径长度是否为 22 的倍数,如果不是,输出 -1

    如果是就选择深度较大的一边,然后往上跳路径长度的一半就是答案了

    我因为傻逼,直接跳到了根节点去,我是sb/kk

    /*
       @author:Pitiless0514
       @qq:3071106789
    */
    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    const int N = 4e6;
    int n,q,nex[N],first[N],v[N],num;
    void add(int from,int to){
    	nex[++num]=first[from];
    	first[from]=num;
    	v[num]=to;
    }
    int dep[N],siz[N],f[N][34];
    void dfs(int x,int fa){
    	dep[x]=dep[fa]+1;
    	
    	/*for(int i=1;i<=20;i++){
    		f[x][i]=f[f[x][i-1]][i-1];
    	}*/
    	for(int i=first[x];i;i=nex[i]){
    		int to=v[i];
    		if(to==fa) continue;
    		f[to][0]=x;
    		dfs(to,x);
    	}
    }
    int power(int a,int b){
    	int ans=1;
    	while(b){
    		if(b&1) ans=(ans*a);
    		a=(a*a);
    		b>>=1;
    	}
    	return ans;
    }
    int LCA(int x,int y){
    	if(dep[x]<dep[y]) swap(x,y);
    	for(int i=20;i>=0;i--){
    		if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    		if(x==y) return x;
    	}
    	for(int i=20;i>=0;i--){
    		if(f[x][i]!=f[y][i]){
    			x=f[x][i];y=f[y][i];
    		}
    	}
    	return f[x][0];
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0),cout.tie(0);
    	cin>>n;
    	for(int i=1;i<=n-1;i++){
    		int u,v;
    		cin>>u>>v;
    		add(u,v);
    		add(v,u);
    	}
    	dfs(1,-1);
    	for(int j=1;j<=30;j++){
    		for(int i=1;i<=n;i++){
    			f[i][j]=f[f[i][j-1]][j-1];
    		}
    	}
    	cin>>q;	
    	
    	for(int i=1;i<=q;i++){
    		int s,t;
    		cin>>s>>t;
    		if(s==t){
    			cout<<s<<" "<<0<<"\n";
    			continue;
    		}
    		int lca=LCA(s,t);
    
    	//	cout<<dep[s]<<" "<<dep[t]<<"\n";
    		if((dep[s]+dep[t]-dep[lca]*2)%2){
    			cout<<-1<<"\n";
    			continue;
    		}
    		int wh=(dep[s]+dep[t] -2*dep[lca])/2;
    		//cout<<wh<<" ";
    		/*if(dep[s]==dep[t]){
    			cout<<1<<" "<<dep[s]-1<<"\n";
    			continue;
    		}*/
    		if(dep[s]>dep[t]){
    			int can=wh;
    			int to=dep[s]-wh;
    			int now=s;
    			while(1){
    				if(wh==0){
    					break;
    				}
    				int k=i;
    				for(int i=0;i<=30;i++){
    					if(power(2,i)>wh){
    						k=i-1;
    						break;
    					}
    				}
    				now=f[now][k];
    				wh-=power(2,k);
    			}
    			cout<<now<<" "<<can<<"\n";
    		}
    		if(dep[s]<=dep[t]){
    			int can=wh;
    			//int to=dep[t]-wh;
    			int now=t;
    			while(1){
    				if(wh==0){
    					break;
    				}
    				int k=i;
    				for(int i=0;i<=30;i++){
    					if(power(2,i)>wh){
    						k=i-1;
    						break;
    					}
    				}
    				now=f[now][k];
    				wh-=power(2,k);
    			//	cout<<now<<" "<<wh<<"\n"; 
    			}
    			cout<<now<<" "<<can<<"\n";
    		}
    		
    	}
    	
    	return 0;
    }
    

    信息

    ID
    99
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    53
    已通过
    30
    上传者