3 条题解
-
1
#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
- 标签
- 递交数
- 62
- 已通过
- 39
- 上传者