首页 > 代码库 > Lowest Common Ancestor (LCA)
Lowest Common Ancestor (LCA)
题目链接
In a rooted tree, the lowest common ancestor (or LCA for short) of two vertices u and v is defined as the lowest vertex that is ancestor of both that two vertices.
Given a tree of N vertices, you need to answer the question of the form "r u v" which means if the root of the tree is at r then what is LCA of u and v.
Input
The first line contains a single integer N. Each line in the next N - 1 lines contains a pair of integer u andv representing a edge between this two vertices.
The next line contains a single integer Q which is the number of the queries. Each line in the next Q lines contains three integers r, u, v representing a query.
Output
For each query, write out the answer on a single line.
Constraints
20 points:
- 1 ≤ N, Q ≤ 100
40 points:
- 1 ≤ N, Q ≤ 105
- There is less than 10 unique value of r in all queries
40 points:
- 1 ≤ N, Q ≤ 2 × 105
Example
Input:41 22 31 421 4 22 4 2Output:12Explanation
- "1 4 2": if 1 is the root, it is parent of both 2 and 4 so LCA of 2 and 4 is 1.
- "2 4 2": the root of the tree is at 2, according to the definition, LCA of any vertex with 2 is 2.
题意：给出一棵Ｎ个结点的树，有Ｑ次询问，每次询问给出三个数ｒ，ｘ，ｙ。
求当以ｒ作为树根时，ｘ和ｙ的lca
解决本题，有两个关键的地方：
１. 每次询问的答案只可能是: x, y, r, lca(x, y), lca(x, r), lca(y, r)，这里的lca都是以１为树根时的lca
2. 如果 x = lca(u, v), 那么dist(x, root) + dist(x, u) + dist(x, v)的值是最小的。
Accepted Code:
1 /************************************************************************* 2 > File Name: TALCA.cpp 3 > Author: Stomach_ache 4 > Mail: sudaweitong@gmail.com 5 > Created Time: 2014年09月24日 星期三 17时39分16秒 6 > Propose: 7 ************************************************************************/ 8 #include <cmath> 9 #include <string>10 #include <cstdio>11 #include <vector>12 #include <fstream>13 #include <cstring>14 #include <iostream>15 #include <algorithm>16 using namespace std;17 /*Let‘s fight!!!*/18 19 const int MAX_N = 200050;20 const int MAX_LOG = 20;21 typedef pair<int, int> pii;22 int N, Q;23 int p[MAX_N][MAX_LOG], depth[MAX_N];24 vector<int> G[MAX_N];25 26 void dfs(int u, int fa, int d) {27 p[u][0] = fa;28 depth[u] = d;29 for (int i = 0; i < G[u].size(); i++) {30 int v = G[u][i];31 if (v != fa) dfs(v, u, d + 1);32 }33 }34 35 void init() {36 dfs(1, -1, 0);37 for (int k = 0; k + 1 < MAX_LOG; k++) {38 for (int v = 1; v <= N; v++) {39 if (p[v][k] < 0) p[v][k + 1] = -1;40 else p[v][k + 1] = p[p[v][k]][k];41 }42 }43 }44 45 int lca(int u, int v) {46 if (depth[u] > depth[v]) swap(u, v);47 for (int k = 0; k < MAX_LOG; k++) {48 if ((depth[v] - depth[u]) >> k & 1) {49 v = p[v][k];50 }51 }52 if (u == v) return u;53 for (int k = MAX_LOG - 1; k >= 0; k--) {54 if (p[u][k] != p[v][k]) {55 u = p[u][k];56 v = p[v][k];57 }58 }59 return p[u][0];60 }61 62 int dist(int u, int v) {63 int x = lca(u, v);64 return depth[u] + depth[v] - 2 * depth[x];65 }66 67 int main(void) {68 ios::sync_with_stdio(false);69 while (cin >> N) {70 for (int i = 1; i <= N; i++) G[i].clear();71 for (int i = 1; i < N; i++) {72 int u, v;73 cin >> u >> v;74 G[u].push_back(v);75 G[v].push_back(u);76 }77 78 init();79 cin >> Q;80 pii s[6];81 while (Q--) {82 int r, u, v;83 cin >> r >> u >> v;84 s[0].second = r;85 s[1].second = u;86 s[2].second = v;87 s[3].second = lca(r, u);88 s[4].second = lca(r, v);89 s[5].second = lca(u, v);90 for (int i = 0; i < 6; i++) {91 int x = s[i].second;92 s[i].first = dist(u, x) + dist(v, x) + dist(r, x);93 }94 sort(s, s + 6);95 cout << s[0].second << endl;96 }97 }98 return 0;99 }
Lowest Common Ancestor (LCA)