LCA - Lowest Common Ancestor

LCA - Lowest Common Ancestor

https://www.luogu.com.cn/problem/SP14932
题目描述

A tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree. - Wikipedia
The lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with N nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself). - Wikipedia
Your task in this problem is to find the LCA of any two given nodes v and w in a given tree T.

For example the LCA of nodes 9 and 12 in this tree is the node number 3.
Input

The first line of input will be the number of test cases. Each test case will start with a number N the number of nodes in the tree, 1 <= N <= 1,000. Nodes are numbered from 1 to N. The next N lines each one will start with a number M the number of child nodes of the Nth node, 0 <= M <= 999 followed by M numbers the child nodes of the Nth node. The next line will be a number Q the number of queries you have to answer for the given tree T, 1 <= Q <= 1000. The next Q lines each one will have two number v and w in which you have to find the LCA of v and w in T, 1 <= v, w <= 1,000.
Input will guarantee that there is only one root and no cycles.
Output

For each test case print Q + 1 lines, The first line will have “Case C:” without quotes where C is the case number starting with 1. The next Q lines should be the LCA of the given v and w respectively.
Example

Input:

1. 1
2. 7
3. 3 2 3 4
4. 0
5. 3 5 6 7
6. 0
7. 0
8. 0
9. 0
10. 2
11. 5 7
12. 2 7

复制代码

Output:

1. Case 1:
2. 3
3. 1

复制代码

输入格式

无
输出格式

无
代码

倍增算法

1. #include <bits/stdc++.h>
2. #define endl "\n"
3. using namespace std;
4. vector<int> dep;         // 存储深度
5. vector<vector<int>> fa;  // 存储跳跃点
6. vector<vector<int>> e;   // 存储边
7. void dfs(int x, int y) {
8.   for (int i = 1; i <= 9; i++) {
9.     fa[x][i] = fa[fa[x][i - 1]][i - 1];
10.   }
12.   for (auto i : e[x]) {
13.     dfs(i, x);
14.   }
15. }
17. int lca(int u, int v) {
18.   if (dep[u] < dep[v]) swap(u, v);
20.   for (int i = 9; i >= 0; i--) {
21.     if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
22.   }
23.   if (u == v) return v;
25.   for (int i = 9; i >= 0; i--) {
26.     if (fa[u][i] != fa[v][i]) {
27.       u = fa[u][i];
28.       v = fa[v][i];
29.     }
30.   }
31.   return fa[u][0];
32. }
34. void solve() {
35.   int N;  // 节点数
36.   cin >> N;
37.   dep    = vector<int>(N + 1);
38.   fa     = vector<vector<int>>(N + 1, vector<int>(10, 0));
39.   e      = vector<vector<int>>(N + 1);
40.   dep[1] = 1;
41.   for (int i = 1; i <= N; i++) {
42.     int sonNum;  // 子节点数量
43.     cin >> sonNum;
45.     while (sonNum--) {
46.       int sonNode;
47.       cin >> sonNode;
48.       e[i].push_back(sonNode);
49.       fa[sonNode][0] = i;
50.       dep[sonNode]   = dep[i] + 1;
51.     }
52.   }
54.   dfs(1, 0);
56.   int queryNum;
57.   cin >> queryNum;  // 查询次数
58.   while (queryNum--) {
59.     int u, v;
60.     cin >> u >> v;
61.     cout << lca(u, v) << endl;
62.   }
63. }
65. int main() {
66.   ios::sync_with_stdio(false);
67.   cin.tie(nullptr);
68.   int T;
69.   cin >> T;
70.   for (int i = 1; i <= T; i++) {
71.     cout << "Case " << i << ":" << endl;
72.     solve();
73.   }
74.   return 0;
75. }

复制代码

tarjan算法

1. #include <bits/stdc++.h>
2. #define endl "\n"
3. using namespace std;
4. vector<bool> vis;                      // 存储是否访问
5. vector<int> fa;                        // 存储父节点
6. vector<vector<int>> e;                 // 存储子节点
7. vector<vector<pair<int, int>>> query;  // 需要查询的
8. vector<int> ans;                       // 存储答案
10. int find(int x) {
11.   if (x == fa[x]) return x;
12.   return fa[x] = find(fa[x]);
13. }
15. void tarjan(int x) {
16.   vis[x] = true;
18.   for (auto son : e[x]) {
19.     if (!vis[son]) {
20.       tarjan(son);
21.       fa[son] = x;
22.     }
23.   }
25.   for (auto q : query[x]) {
26.     int y = q.first, id = q.second;
27.     if (vis[y]) {
28.       ans[id] = find(y);
29.     }
30.   }
31. }
32. void solve() {
33.   int N;  // 节点数
34.   cin >> N;
35.   fa = vector<int>(N + 1);
36.   e  = vector<vector<int>>(N + 1);
37.   query.resize(N + 1);
38.   vis = vector<bool>(N + 1, false);
40.   for (int i = 1; i <= N; i++) {
41.     fa[i] = i;
42.   }
44.   // 输入子节点
45.   for (int i = 1; i <= N; i++) {
46.     int sonNum;
47.     cin >> sonNum;
48.     while (sonNum--) {
49.       int sonNode;
50.       cin >> sonNode;
51.       e[i].push_back(sonNode);
52.     }
53.   }
55.   int queryNum;
56.   cin >> queryNum;
57.   ans = vector<int>(queryNum + 1);
58.   for (int i = 1; i <= queryNum; i++) {
59.     int u, v;
60.     cin >> u >> v;
61.     query[u].push_back({ v, i });
62.     query[v].push_back({ u, i });
63.   }
65.   tarjan(1);
67.   for (int i = 1; i <= queryNum; i++) {
68.     cout << ans[i] << endl;
69.   }
70. }
72. int main() {
73.   ios::sync_with_stdio(false);
74.   cin.tie(nullptr);
75.   int T;
76.   cin >> T;
77.   for (int i = 1; i <= T; i++) {
78.     cout << "Case " << i << ":" << endl;
79.     solve();
80.   }
81.   return 0;
82. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。