记录 dfs 序列, dfn[tot] 记录第 tot 次访问的节点
然后查两点在 dfs 序中出现的第一次 id[u] id[v]
然后 找 dep[k] = min( dep[i] ) {i 属于 [id[u], id[v]]}
最后 dfn[k] 就是所求..
感觉弄来弄去 就是 在映射... 无非就是 求一段序列深度最小的节点编号
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 2e5+10;
- int n, cnt, tot, dp[N][21]; // dp[i][j] [i, i+(1<<j)-1]
- vector<int> G[N]; map<string ,int> mp;
- string s1,s2,s[N];
- int dfn[N], id[N], dep[N];
- int getId(string str)
- {
- if(mp[str])
- return mp[str];
- mp[str] = ++cnt;
- s[cnt] = str;
- return cnt;
- }
- void dfs(int u,int fa,int d)
- {
- id[u] = tot;
- dfn[tot] = u;
- dep[tot++] = d;
- for(int i=0; i<G[u].size(); i++) {
- int v = G[u][i];
- dfs(v, u, d+1);
- dfn[tot] = u;
- dep[tot++] = d;
- }
- return ;
- }
- void st_init(int sz)
- {
- for(int i=1; i<=sz; i++)
- dp[i][0] = i;
- for(int j=1; (1<<j)<=sz; j++)
- {
- for(int i=1; i+(1<<j)-1<=sz; i++)
- {
- int x = dp[i][j-1];
- int y = dp[i+(1<<(j-1))][j-1];
- if(dep[x] <dep[y])
- dp[i][j] = x;
- else
- dp[i][j] = y;
- }
- }
- }
- void init()
- {
- tot = 1;
- dfs(1, 0, 0);
- st_init(tot-1);
- }
- int query(int u,int v)
- {
- u = id[u], v = id[v];
- if(v < u)
- swap(v,u);
- int t = log2(v-u+1);
- int x = dp[u][t];
- int y = dp[v-(1<<t)+1][t];
- if(dep[x] < dep[y])
- return x;
- else
- return y;
- }
- int main()
- {
- freopen("in.txt","r",stdin);
- iOS::sync_with_stdio(0);
- cin>> n;
- for(int i=0; i<n; i++) {
- cin>> s1>> s2;
- int u = getId(s1);
- int v = getId(s2);
- G[u].push_back(v);
- }
- init();
- int m; cin>> m;
- for(int i=0; i<m; i++) {
- cin>> s1>> s2;
- int u = getId(s1);
- int v = getId(s2);
- int x = dfn[query(u,v)];
- cout << s[x] <<"\n";
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2858458.html