全方位木 DP
Rerooting DP
code
code:cpp
std::vector<std::map<int, value>> dp(n);
auto solve = &(auto&& solve, int v, int par, bool flag) -> value { if(dpv.count(par)) return dpvpar; value res = id;
if(par == -1 or flag) {
std::vector<value> ret;
for(int i = 0; i < gv.size(); i++) { if(to == par) continue;
ret.push_back(solve(solve, to, v, flag));
}
std::vector<value> R(ret.size() + 1, id);
for(int i = R.size() - 1; i > 0; i--) Ri - 1 = marge(Ri, reti - 1); if(par == -1) {
value L = id;
for(int i = 0; i < gv.size(); i++) { }
}
} else {
solve(solve, v, -1, flag);
res = solve(solve, v, par, flag);
}
};
solve(solve, 0, -1, true);
for(int i = 0; i < n; i++) cout << solve(solve, i, -1, false) << endl;
解説
dp[v][par] := 頂点 v を見ていて親が par のときの解
親が -1 のときは頂点 v を根としたときの値 = 頂点 v についての解となる
solve(solve, v, par, flag)
v: 現在見ている頂点
par: 現在見ている頂点の親
flag: 前処理かどうか
if(par == -1 or flag)
v を根と考えるときの処理
if(to == par) continue; を入れると前処理の時だけ働く(処理をまとめられる).
if(par == -1)
両側累積和を用いて子を親としたときの値をメモっている
else
親が存在するときの処理
一度自分を根したときの値を求めておく solve(solve, v, -1, flag)
すると求めたかった値が求まっている res = solve(solve, v, par, flag)
計算量はすべての辺を二回(向きの自由度分)見るのと map の $ \log がかかるので
$ O(N\log N)
辺の id についてメモって頑張ると $ O(N) に落とせる.
図
パターン 1 が if で処理しているケース,パターン 2 が else の方で処理しているケース
https://gyazo.com/fc9c2ba2820ef3d5725af919b43d98ce