参考：https://www.cnblogs.com/pczhou/p/4297132.html
rmq-sthttps://www.cnblogs.com/five20/p/7531644.html
代码：
#include<iostream> #include<cmath> #include<map> #include<vector> #include<algorithm> #include<string> #define maxn 100010 using namespace std; map<string, int>mp; vector<int>v[2 * maxn]; int p[4 * maxn], pos[2 * maxn], dep[2 * maxn],pre[4*maxn][20]; string name[2 * maxn]; int cnt, n, m; void dfs(int i, int d) { pos[i] = cnt; p[cnt++] = i; dep[i] = d; if (v[i].empty()) return; for (int j = 0;j < v[i].size();j++) { int u = v[i][j]; dfs(u, d + 1); p[cnt++] = i; } } void rmq()//区间最值查询 查dep的最小值 { for (int i = 0;i < 4 * maxn;i++) pre[i][0] = i; for (int j = 1;(1<<(j-1))<4*maxn ;j++) for (int i = 0;i+(1<<(j-1))<4*maxn;i++) pre[i][j] = dep[p[pre[i][j - 1]]] < dep[p[pre[i + (1 << (j - 1))][j - 1]]] ? pre[i][j - 1] : pre[i + (1 << (j - 1))][j - 1]; } string lca(int a, int b) { int k = floor(log(b - a + 1) / log(2)); int x = pre[a][k], y = pre[b - (1 << k) + 1][k]; return dep[p[x]] < dep[p[y]] ? name[p[x]] : name[p[y]]; } void init() { cnt = 0; mp.clear(); for (int i = 0;i < 2 * maxn;i++) v[i].clear(); } int main() { while (cin >> n) { init(); while (n--) { string name1, name2; cin >> name1 >> name2; if (mp.find(name1) == mp.end()) { mp[name1] = cnt; name[cnt++] = name1; } if (mp.find(name2) == mp.end()) { mp[name2] = cnt; name[cnt++] = name2; } v[mp[name1]].push_back(mp[name2]); } cnt = 0; dfs(0, 0); rmq(); cin >> m; while (m--) { string name1, name2; cin >> name1 >> name2; int a = mp[name1], b = mp[name2]; cout << (pos[a] < pos[b] ? lca(pos[a], pos[b]) : lca(pos[b], pos[a])) << endl; } } return 0; }
