1 条题解
-
0
#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
- 上传者