Nearest Common Ancestors 【LCA树上倍增】

题目链接POJ-1330


题目描述

在这里插入图片描述
In the figure, each node is labeled with an integer from {1, 2,…,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is.

For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest common ancestor of y and z is y.

Write a program that finds the nearest common ancestor of two distinct nodes in a tree.


思路

题目是求最近公共祖先的裸题,然后给定a,b默认a是b的父亲节点;所以我们需要一个并查集来维护一下根节点。然后剩下的就是裸的LCA问题了;

LCA代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

#define MAX_N 500050
#define MAX_M 500050

int head[MAX_N], cnt = 0, fa[MAX_N][30], dfn[MAX_N], pre[MAX_N];
int n, m, t;

struct Node{
int to, val, next;
}edge[MAX_M * 2];

void init()
{
cnt = 0;
memset(head, -1, sizeof(head));
memset(dfn, 0, sizeof(dfn));
for(int i = 1; i <= n; i++)
pre[i] = i;
}

int Find(int x)
{
return x == pre[x] ? pre[x] : pre[x] = Find(pre[x]);
}

void Union(int x, int y)
{
x = Find(x);
y = Find(y);
if(x != y)
pre[y] = x;
}

void add(int x, int y)
{
edge[cnt].to = y;
edge[cnt].next = head[x];
head[x] = cnt++;
}

void dfs(int u)
{
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if(!dfn[v])
{
dfn[v] = dfn[u] + 1;
fa[v][0] = u;
dfs(v);
}
}
}

int lca(int x, int y)
{
if(dfn[x] < dfn[y])
{
swap(x, y);
}
for(int i = 20; i >= 0; i--)
{
if(dfn[fa[x][i]] >= dfn[y])
{
x = fa[x][i];
}
}
if(x == y)
return x;
for(int i = 20; i >= 0; i--)
{
if(fa[x][i] != fa[y][i])
{
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}

int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d", &n);
init();
for(int i = 0; i < n - 1; i++)
{
int x, y;
scanf("%d %d", &x, &y);
Union(x, y);
add(x, y);
add(y, x);
}
int root = Find(pre[1]);
dfn[root] = 1, fa[root][0] = 0;
dfs(root);
for(int i = 1; i <= 20; i++)
{
for(int j = 1; j <= n; j++)
{
fa[j][i] = fa[fa[j][i-1]][i-1];
}
}
int x, y;
scanf("%d %d", &x, &y);
printf("%d\n", lca(x, y));
}
return 0;
}
-------------本文结束,感谢您的阅读!-------------