题目描述
给定一棵 n 个点的树,Q 个询问,每次询问点 x 到点 y 两点之间的距离。
输入格式
第一行一个正整数 n,表示这棵树有 n 个节点;
接下来 n-1 行,每行两个整数 x,y 表示 x,y 之间有一条连边;
然后一个整数 Q,表示有 Q 个询问;
接下来 Q 行每行两个整数 x,y 表示询问 x 到 y 的距离。
输出格式
输出 Q 行,每行表示每个询问的答案。
样例输入
6 1 2 1 3 2 4 2 5 3 6 2 2 6 5 6
样例输出
3 4
数据范围与提示
对于全部数据,1<= n,Q<= 10^5,1<= x,y<= n。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5+10;
int n,q,num;
int f[maxn],d[maxn];
int st[30][maxn];
int first[maxn],Next[2*maxn],v[2*maxn];
void road(int x,int y)
{
v[++num]=y;
Next[num]=first[x];
first[x]=num;
}
void dfs(int son,int father)
{
f[son]=father;
for(int i = first[son]; i!=-1; i=Next[i])
{
int to = v[i];
if(to==father)continue;
d[to]=d[son]+1;
dfs(to,son);
}
}
int g(int x,int y)
{
if(d[x]<d[y])swap(x,y);
for(int i = 20; i >= 0; i--)
if(d[st[i][x]]>=d[y])
x=st[i][x];
if(x==y)return x;
for(int i = 20; i >= 0; i--)
if(st[i][x]!=st[i][y])
x=st[i][x],y=st[i][y];
return f[x];
}
int main()
{
int x,y;
cin>>n;
memset(first,-1,sizeof(first));
num=0;
for(int i = 1; i < n; i++)
{
scanf("%d %d",&x,&y);
road(x,y),road(y,x);
}
d[1]=1;
dfs(1,0);
for(int i = 1; i <= n; i++)
st[0][i]=f[i];
for(int i = 1; i <= 20; i++)
for(int j = 1; j <= n; j++)
st[i][j]=st[i-1][st[i-1][j]];
scanf("%d",&q);
while(q--)
{
scanf("%d %d",&x,&y);
int father = g(x,y);
printf("%d\n",d[x]+d[y]-2*d[father]);
}
return 0;
}