1 #include <bits/stdc++.h>  2 using namespace std;  3   4 const int MAXN = 1000010;  5 int rmq[2 * MAXN]; //rmq数组，就是欧拉序列对应的深度序列  6   7 struct ST {  8     int mm[2 * MAXN];  9     int dp[2 * MAXN][20]; //最小值对应的下标 10     void init(int n) { 11         mm[0] = -1; 12         for(int i = 1; i <= n; i++) { 13             mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1]; 14             dp[i][0] = i; 15         } 16         for(int j = 1; j <= mm[n]; j++) 17             for(int i = 1; i + (1 << j) - 1 <= n; i++) 18                 dp[i][j] = rmq[dp[i][j - 1]] < 19                            rmq[dp[i + (1 << (j - 1))][j - 1]] ? dp[i][j - 1] : dp[i + (1 << (j - 1))][j - 1]; 20     } 21     int query(int a, int b) { //查询[a,b]之间最小值的下标 22         if(a > b)swap(a, b); 23         int k = mm[b - a + 1]; 24         return rmq[dp[a][k]] <= 25                rmq[dp[b - (1 << k) + 1][k]] ? dp[a][k] : dp[b - (1 << k) + 1][k]; 26     } 27 }; 28 //边的结构体定义 29 struct Edge { 30     int to, next; 31 }; 32  33 Edge edge[MAXN * 2]; 34  35 int tot, head[MAXN]; 36 int F[MAXN * 2]; //欧拉序列，就是dfs遍历的顺序，长度为2*n-1,下标从1开始 37 int P[MAXN];//P[i]表示点i在F中第一次出现的位置 38 int cnt; 39 ST st; 40 map<string, int> Hash_zh; 41 map<int, string> Hash_fa; 42  43 void init() { 44     tot = 0; 45     memset(head, -1, sizeof(head)); 46     Hash_zh.clear(); 47     Hash_fa.clear(); 48 } 49  50 void addedge(int u, int v) { //加边，无向边需要加两次 51     edge[tot].to = v; 52     edge[tot].next = head[u]; 53     head[u] = tot++; 54 } 55  56 void dfs(int u, int pre, int dep) { 57     F[++cnt] = u; 58     rmq[cnt] = dep; 59     P[u] = cnt; 60     for(int i = head[u]; i != -1; i = edge[i].next) { 61         int v = edge[i].to; 62         if(v == pre)continue; 63         dfs(v, u, dep + 1); 64         F[++cnt] = u; 65         rmq[cnt] = dep; 66     } 67 } 68 void LCA_init(int root, int node_num) { //查询LCA前的初始化 69     cnt = 0; 70     dfs(root, root, 0); 71     st.init(2 * node_num - 1); 72 } 73  74 int query_lca(int u, int v) { //查询u,v的lca编号 75     return F[st.query(P[u], P[v])]; 76 } 77  78 bool flag[MAXN]; 79  80 int main() { 81     int T, N; 82     int u, v, cnt; 83     string str_u, str_v; 84     while(~scanf("%d", &N)) { 85         init(); 86         cnt = 1; 87         memset(flag, false, sizeof(flag)); 88         for(int i = 1; i <= N; i++) { 89             //scanf("%d%d", &u, &v); 90             cin >> str_u >> str_v; 91             if (Hash_zh[str_u] == 0) { 92                 Hash_fa[cnt] = str_u; 93                 Hash_zh[str_u] = cnt ++; 94             } 95             if (Hash_zh[str_v] == 0) { 96                 Hash_fa[cnt] = str_v; 97                 Hash_zh[str_v] = cnt ++; 98             } 99             u = Hash_zh[str_u];100             v = Hash_zh[str_v];101             addedge(u, v);102             addedge(v, u);103             flag[v] = true;104         }105         int root;106         for(int i = 1; i <= N; i++) {107             if(!flag[i]) {108                 root = i;109                 break;110             }111         }112         LCA_init(root, N);113         int query_n;114         scanf ("%d", &query_n);115         for (int i = 1; i <= query_n; ++ i) {116             //scanf("%d%d", &u, &v);117             cin >> str_u >> str_v;118 119             if (str_u == str_v) {120                 cout << str_u << endl;121                 continue;122             }123 124             u = Hash_zh[str_u];125             v = Hash_zh[str_v];126             cout << Hash_fa[query_lca(u, v)] << endl;127         }128     }129     return 0;130 }