3 条题解
-
2
#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
#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
EnergeticPlayer LV 9 @ 2021-5-10 18:05:10
因为题目告诉你了给出的是一棵树
那么两点的简单路径就是两点到他们的最近公共祖先
然后可以先选择 为根节点 ，然后求出每个节点的深度。
又由于节点边的长度都为1，那么一个点的深度就是他到根节点的距离。
这样两点 之间简单路径长度就为
dep[u]+dep[v]-2*dep[LCA(u,v)]然后判断是否可行就是判断路径长度是否为 的倍数，如果不是，输出
-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; }
小狼
LV 10
@ 2023-10-14 8:56:33
- 1
