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 ≤ 10⁵

There is less than 10 unique value of r in all queries

40 points:

1 ≤ N, Q ≤ 2 × 10⁵

Example
Input:

4

1 2

2 3

1 4

2

1 4 2

2 4 2

Output:

1

2
Explanation

"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:

 /*************************************************************************

     > File Name: TALCA.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年09月24日 星期三 17时39分16秒

     > Propose:

  ************************************************************************/

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <vector>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /*Let's fight!!!*/

 const int MAX_N = ;

 const int MAX_LOG = ;

 typedef pair<int, int> pii;

 int N, Q;

 int p[MAX_N][MAX_LOG], depth[MAX_N];

 vector<int> G[MAX_N];

 void dfs(int u, int fa, int d) {

     p[u][] = fa;

     depth[u] = d;

     for (int i = ; i < G[u].size(); i++) {

         int v = G[u][i];

         if (v != fa) dfs(v, u, d + );

     }

 }

 void init() {

     dfs(, -, );

     for (int k = ; k +  < MAX_LOG; k++) {

           for (int v = ; v <= N; v++) {

             if (p[v][k] < ) p[v][k + ] = -;

             else p[v][k + ] = p[p[v][k]][k];

         }

     }

 }

 int lca(int u, int v) {

     if (depth[u] > depth[v]) swap(u, v);

     for (int k = ; k < MAX_LOG; k++) {

         if ((depth[v] - depth[u]) >> k & ) {

               v = p[v][k];

         }

     }

     if (u == v) return u;

     for (int k = MAX_LOG - ; k >= ; k--) {

           if (p[u][k] != p[v][k]) {

             u = p[u][k];

             v = p[v][k];

         }

     }

     return p[u][];

 }

 int dist(int u, int v) {

       int x = lca(u, v);

       return depth[u] + depth[v] -  * depth[x];

 }

 int main(void) {

     ios::sync_with_stdio(false);

     while (cin >> N) {

         for (int i = ; i <= N; i++) G[i].clear();

         for (int i = ; i < N; i++) {

             int u, v;

             cin >> u >> v;

             G[u].push_back(v);

             G[v].push_back(u);

         }

         init();

         cin >> Q;

         pii s[];

         while (Q--) {

             int r, u, v;

             cin >> r >> u >> v;

             s[].second = r;

             s[].second = u;

             s[].second = v;

             s[].second = lca(r, u);

             s[].second = lca(r, v);

             s[].second = lca(u, v);

             for (int i = ; i < ; i++) {

                   int x = s[i].second;

                   s[i].first = dist(u, x) + dist(v, x) + dist(r, x);

             }

             sort(s, s + );

             cout << s[].second << endl;

         }

     }

     return ;

 }

巴特西

Lowest Common Ancestor (LCA)

Input

Output

Constraints

Example

Explanation

最新文章

热门文章