hihoCoder week17 最近公共祖先·三 lca st表

记录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; }

 

转载于:https://www.cnblogs.com/Draymonder/p/10010241.html

总结

以上是生活随笔为你收集整理的hihoCoder week17 最近公共祖先·三 lca st表的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。