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:

 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 }