问题 ***的距离

问题 G: 点的距离

时间限制: 5 Sec 内存限制: 128 MB
提交: 57 解决: 19
[提交][状态][讨论版][命题人:add_lm][Edit] [TestData]

题目链接：http://acm.ocrosoft.com/problem.php?cid=1691&pid=6

题目描述

给定一棵有n个结点的树，Q个询问，每次询问点x到点y亮点之间的距离

输入

第一行一个n，表示有n个节。

接下来有n-1行，每行2个整数x，y表示x，y之间有一条连边。

然后一个整数Q，表示有Q次询问，接下来Q行每行2个整数x，y表示询问x到y的距离。

输出

输出Q行，每行表示每个询问的结果

样例输入

样例输出

3

4

思路：裸的倍增求lca的题目

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 4e5 + 5;

int dep[maxn];

int First[maxn], Next[maxn * 2], v[maxn * 2], num_edge;

int Fa[maxn];

int st[maxn][25];

void ins(int x, int y)//建边

{

    v[++num_edge] = y;

    Next[num_edge] = First[x];

    First[x] = num_edge;

}

void dfs(int x, int fa)//无向图中需要记录父节点防止死循环

{

    Fa[x] = fa;

    for (int i = First[x]; i != -1; i = Next[i])

    {

         int to = v[i];

         if (to == fa)continue;

         dep[to] = dep[x] + 1;

         dfs(to, x);

    }

}

int get_lca(int x, int y)

{

    if (dep[x] < dep[y])swap(x, y);//确定x的深度比y大，方便处理

    //得到同一深度

    for (int i = 20; i >= 0; i--)

    {

         if (dep[st[x][i]] >= dep[y])

         {

             x = st[x][i];

         }

    }

    //若此时两者节点相同，说明y就是x和y的公共祖先

    if (x == y)

    {

         return x;

    }

    //一起往上跳

    for (int i = 20; i >= 0; i--)

    {

         if (st[x][i] != st[y][i])

         {

             x = st[x][i];

             y = st[y][i];

         }

    }

    //公共祖先就是其父节点

    return  st[x][0];

}

int main()

{

    int n;

    while (cin >> n)

    {

         memset(First, -1, sizeof(First));

         num_edge = 0;

         dep[1] = 1;//初始化根节点深度

         for (int i = 1; i < n; i++)

         {

             int x, y;

             scanf("%d %d", &x, &y);

             ins(x, y), ins(y, x);

         }

         dfs(1, 0);

         for (int i = 1; i <= n; i++)st[i][0] = Fa[i];//建立ST表

         for (int i = 1; i <= 20; i++)

         {

             for (int j = 1; j <= n; j++)

             {

                  st[j][i] = st[st[j][i - 1]][i - 1];

             }

         }

         int q;

         scanf("%d", &q);

         while (q--)

         {

             int x, y;

             scanf("%d %d", &x, &y);

             printf("%d\n", dep[x] + dep[y] - 2 * dep[get_lca(x, y)]);

         }


    }


}