问题 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行,每行表示每个询问的结果
样例输入
6
1 2
1 3
2 4
2 5
3 6
2
2 6
5 6
样例输出
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)]);
}
}
}