3 条题解

  • 2
    @ 2023-10-14 8:56:33
    #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;
    }
    
    
    • 1
      @ 2023-3-25 17:33:47
      #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;
      }
      
      • 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;
        }
        
        • 1

        信息

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