1 条题解
-
0117爱好者 (mengqingyu) LV 10 @ 2024-7-27 15:21:06
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int N=1e6+10; int n,m; int deep[N],st[N][40]; int head[N],next[N],w[N],to[N]; int id_star=0; inline void add(int x,int y) { id_star++; to[id_star]=y; next[id_star]=head[x]; head[x]=id_star; } inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } inline void write(int x) { if(x<0) { putchar('-'); x=-x; } if(x>9) write(x/10); putchar(x%10+'0'); printf("\n"); } void dfs(int id,int father) { deep[id]=deep[father]+1; st[id][0]=father; for(int i=1;(1<<i) <= deep[id]+1;i++) st[id][i]=st[st[id][i-1]][i-1]; for(int j=head[id];j;j=next[j]) if(to[j]!=father) dfs(to[j],id); } inline int find(int u,int v) { if(deep[u]>deep[v])swap(u,v); for(int i=log2(deep[v])+1;i>=0;i--) { if(deep[u]<=deep[st[v][i]]) v=st[v][i]; if(u==v)return v; } for(int i=log2(deep[v])+1;i>=0;i--) { if(st[u][i]!=st[v][i]) { u=st[u][i];v=st[v][i]; } } return st[u][0]; } int main() { n=read(); for(int i=1;i<=n-1;i++) { int x,y; x=read();y=read(); add(x,y); add(y,x); } deep[0]=0; dfs(1,0); m=read(); for(int i=1;i<=m;i++) { int x,y; x=read();y=read(); int k=find(x,y); k=deep[k]; printf("%d\n",deep[x]+deep[y]-2*k); } }
- 1
信息
- ID
- 457
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 3
- 上传者