点的距离（LAC）

链接
题目描述
给定一棵 nn 个点的树，QQ 个询问，每次询问点 xx 到点 yy 两点之间的距离。

输入格式
第一行一个正整数 nn，表示这棵树有 nn 个节点；

接下来 n-1n−1 行，每行两个整数 x,yx,y 表示 x,yx,y 之间有一条连边；

然后一个整数 QQ，表示有 QQ 个询问；

接下来 QQ 行每行两个整数 x,yx,y 表示询问 xx 到 yy 的距离。

输出格式
输出 QQ 行，每行表示每个询问的答案。

样例
Input Output
6
1 2
1 3
2 4
2 5
3 6
2
2 6
5 6
3
4

LCA问题(least Common Ancestors,最近公共祖先问题),是指给定一棵有根树T,给出若干个查询LCA(u,v)(通常查询数量较大)，每次求树T中两个顶点u和v的最近公共祖先，即找到一个节点，同时是u和v的祖先，并且深度尽可能的大(尽可能远离树根).
ａｃ代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
int n,m,f[100010][18];
int head[100010],to[100010],nxt[100010],d[100010];
int total=0;
void add(int x,int y)
{
    total++;
    to[total]=y;
    nxt[total]=head[x];
    head[x]=total;
    return ;
}
void dfs(int x,int fa)
{
    f[x][0]=fa;
    for(int i=head[x];i;i=nxt[i])
    {
        d[to[i]]=d[x]+1;
        dfs(to[i],x);
    }
    return ;
}
void pre()
{
    for(int j=1;j<=17;j++)
    {
        for(int i=1;i<=n;i++)
            f[i][j]=f[f[i][j-1]][j-1];
    }
    return ;
}
int LCA(int x,int y)
{
    if(d[x]<d[y]) 
	swap(x,y);
    for(int i=17; i>=0; i--)
        if(d[f[x][i]]>=d[y])
            x=f[x][i];
    if(x==y) 
	return x;
    for(int i=17;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main()
{
	int x,y;
    scanf("%d",&n);
    for(int i=1; i<n; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    d[1]=1;
    dfs(1,0);
    pre();
  	scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",d[x]+d[y]-(d[LCA(x,y)]*2));
    }
}