DOJ Beginner Contest 13 D - Vassals
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 13
- 問題
- D - Vassals
頂点 を根とする 頂点の根付き木があり、頂点 の親は です。各頂点 には容量 があります。辺をいくつか選び、各頂点 に接する選んだ辺が 本以下になるようにするとき、選べる辺の最大本数を求める問題です(、)。
葉の側から貪欲に決めます。頂点 を見るときには、 の子の部分木の中の辺はすでに決まっているとして、次のようにします。
- の各子 について、 の容量が残っていて、 の容量も残っていれば、辺 を選びます。
- そのあと の容量が残っていれば、 と親を結ぶ辺の候補になります。実際に選ぶかは親を見るときに決めます。
この貪欲が最適であることは、次の 2 つの入れ替えで示せます。
- 子の部分木の中の辺を、親への辺より優先してよい。 子 が親への辺 を選ぶために、部分木の中の辺 をあきらめたとします。 を外して を選び直しても本数は変わらず、 の容量が 空くだけです。
- 子への辺を、親への辺より優先してよい。 子への辺 を選べるのに、 の容量を親への辺に使い切った最適解があるとします。親への辺を外して を選んでも本数は変わりません。 の容量はほかに使い道がなく、親の容量は 空きます。
子どうしの間では、どの子との辺を選んでも の容量を 使うだけで、子の残りの容量はほかで使えないので、どれから選んでも同じです。
各頂点を帰りがけ順に 1 回ずつ見るだけなので、計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/graph/tree.hpp"#include "shogo-library/utility/container_func.hpp"
void solve() { LL(N); VL(P, N - 1); VL(B, N); Tree<> tree(N); rep(i, N - 1) { tree.add_edge(i + 1, P[i] - 1); } RootedTree<> rooted(tree, 0); vl dp(N); for (ll u : rooted.postorder) { for (ll v : rooted.child[u]) { if (dp[v] && B[u]) { B[u]--; } else { dp[v] = 0; } } if (B[u] && u != rooted.root) { dp[u] = 1; } else { dp[u] = 0; } } print(sum(dp));}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}rooted.postorder は帰りがけ順に並べた頂点の列、rooted.child[u] は の子です。B[u] は子との辺を選ぶたびに減らすので、 の残りの容量になります。
dp[u] は、 を見終わった時点では「 の容量が残っていて、親への辺の候補になるか」を表します。親を見たときに、その辺を選ばなかった子の dp[v] を に戻すので、最後には dp[v] が「 と親を結ぶ辺を選んだか」になり、その総和が答えです。
使用ライブラリ:cpp_include@4b58304