1552：【例 1】点的距离
时间限制: 1000 ms 内存限制: 524288 KB 提交数: 168 通过数: 75
【题目描述】
给定一棵 nn 个点的树，QQ 个询问，每次询问点 xx 到点 yy 两点之间的距离。
【输入】
第一行一个正整数 nn，表示这棵树有 nn 个节点；
接下来 n−1n−1 行，每行两个整数 x,yx,y表示 x,yx,y 之间有一条连边；
然后一个整数 QQ，表示有 QQ 个询问；
接下来 QQ 行每行两个整数 x,yx,y 表示询问 xx 到 yy 的距离。
【输出】
输出 QQ 行，每行表示每个询问的答案。
【输入样例】
6
1 2
1 3
2 4
2 5
3 6
2
2 6
5 6
【输出样例】
3
4
【提示】
数据范围与提示：
对于全部数据，1≤n≤105,1≤x,y≤n1≤n≤105,1≤x,y≤n
【来源】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100005
using namespace std;
int n,q;
struct edge
{
int next,v;
}edges[maxn*2];
int cnt;
int head[maxn];
void init()
{
memset(head,-1,sizeof(head));
cnt=0;
}
void addedge(int u,int v)
{
edges[cnt].next=head[u];
edges[cnt].v=v;
head[u]=cnt++;
}
int dep[maxn];
int f[maxn][21];
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1;
for(int i=0;i<=19;i++)
f[u][i+1]=f[f[u][i]][i];
for(int i=head[u];i!=-1;i=edges[i].next)
{
int v=edges[i].v;
if(v==fa)
continue;
f[v][0]=u;
dfs(v,u);
}
}
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];
}
int main()
{
scanf("%d",&n);
int x,y;
init();
for(int i=1;i<=n-1;i++)
{scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
dfs(1,0);
scanf("%d",&q);
int a,b;
while(q--)
{
scanf("%d%d",&a,&b);
printf("%d\n",dep[a]+dep[b]-2*dep[lca(a,b)]);
}
return 0;
}
