广西网站建设设计,做网站的需要哪些职位,纳税服务网站建设情况,中国建筑网官网防水证书查询学习链接【学习笔记】支配树_cz_xuyixuan的博客-CSDN博客
主要的求法是最后两个结论#xff1a; 定理4用来求sdom#xff0c;先搞一个dfs树#xff0c;然后将点按dfs序从大到小加入#xff0c;对每个点维护到当前根#xff08;即已加入点#xff09;路径上sdom最小是哪个…学习链接【学习笔记】支配树_cz_xuyixuan的博客-CSDN博客
主要的求法是最后两个结论 定理4用来求sdom先搞一个dfs树然后将点按dfs序从大到小加入对每个点维护到当前根即已加入点路径上sdom最小是哪个sdom的比较是对dfs序比记为home可以用带权并查集完成。加入一个点就先枚举所有能直接到达本身的相邻点用他们的home更新我然后加入我到dfs树父亲的边。
然后用推论1求idom写一个倍增求(sdom[x], x]路径上sdom最小的点即可。
模板题 HDU4694 建立根在n的支配树
#includebits/stdc.h
#define ll long long
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define pii pairint, int
#define fi first
#define sc second
using namespace std;
const int inf 1e9;
const int N 2e6 100;
const ll mod 998244353;void sol(int n, int m) {vectorvectorint adj(n 1), radj(n 1), tree_adj(n 1);for (int i 1; i m; i) {int x, y;cin x y;adj[x].pb(y);radj[y].pb(x);}int tim 0;vectorint rnk(n 1, 0), dfn(n 1, 0), tree_fa(n 1, 0);functionvoid(int) dfs [](int x) {rnk[x] tim, dfn[tim] x;for (int y : adj[x]) {if (!rnk[y]) {tree_fa[y] x;tree_adj[x].pb(y);dfs(y);}}};dfs(n);vectorint sdom(n 1, 0), rt(n 1, 0), home(n 1, 0);iota(all(sdom), 0);iota(all(rt), 0);iota(all(home), 0);functionint(int) get_home [](int x) {if (rt[x] x) {return home[x];}int tmp get_home(rt[x]);if (rnk[sdom[tmp]] rnk[sdom[home[x]]]) {home[x] tmp;}rt[x] rt[rt[x]];return home[x];};for (int i n; i 1; i--) {int x dfn[i];for (int y : radj[x]) {if (rnk[y] rnk[sdom[get_home(y)]] rnk[sdom[x]]) {sdom[x] sdom[get_home(y)];}}rt[x] tree_fa[x];}vectorint dep(n 1, 0);vectorvectorint jp(20, vectorint(n 1, 0)), mn(20, vectorint(n 1, 0));vectorint idom(n 1, 0);vectorll sum(n 1, 0);functionvoid(int) dfs_tree [](int x) {jp[0][x] tree_fa[x];mn[0][x] x;for (int j 1; j 20; j) {jp[j][x] jp[j - 1][jp[j - 1][x]];if (rnk[sdom[mn[j - 1][jp[j - 1][x]]]] rnk[sdom[mn[j - 1][x]]]) {mn[j][x] mn[j - 1][jp[j - 1][x]];} else {mn[j][x] mn[j - 1][x];}}int dt dep[x] - dep[sdom[x]];int ps x, cur x;for (int j 19; j 0; j--) {if (dt j 1) {if (rnk[sdom[mn[j][cur]]] rnk[sdom[ps]]) {ps mn[j][cur];}cur jp[j][cur];} }if (sdom[ps] sdom[x]) {idom[x] sdom[x];} else {idom[x] idom[ps];}sum[x] sum[idom[x]] x;for (int y : tree_adj[x]) {dep[y] dep[x] 1;dfs_tree(y);}};dfs_tree(n);for (int i 1; i n; i) {cout sum[i] \n[i n];}
}signed main() {ios::sync_with_stdio(0);cin.tie(0);
// int tt;
// cin tt;
// while (tt--)int n, m;while (cin n m)sol(n, m);
}
