コンテンツにスキップ

DOJ Beginner Contest 13 D - Vassals

サイト
DOJ
コンテスト
DOJ Beginner Contest 13
問題
D - Vassals

頂点 11 を根とする NN 頂点の根付き木があり、頂点 ii (i≥2)(i \ge 2) の親は PiP_i です。各頂点 ii には容量 BiB_i があります。辺をいくつか選び、各頂点 ii に接する選んだ辺が BiB_i 本以下になるようにするとき、選べる辺の最大本数を求める問題です(2≤N≤2000002 \le N \le 200000、0≤Bi≤2000000 \le B_i \le 200000)。

葉の側から貪欲に決めます。頂点 uu を見るときには、uu の子の部分木の中の辺はすでに決まっているとして、次のようにします。

  1. uu の各子 vv について、vv の容量が残っていて、uu の容量も残っていれば、辺 (u,v)(u, v) を選びます。
  2. そのあと uu の容量が残っていれば、uu と親を結ぶ辺の候補になります。実際に選ぶかは親を見るときに決めます。

この貪欲が最適であることは、次の 2 つの入れ替えで示せます。

  • 子の部分木の中の辺を、親への辺より優先してよい。 子 vv が親への辺 (u,v)(u, v) を選ぶために、部分木の中の辺 (v,w)(v, w) をあきらめたとします。(u,v)(u, v) を外して (v,w)(v, w) を選び直しても本数は変わらず、uu の容量が 11 空くだけです。
  • 子への辺を、親への辺より優先してよい。 子への辺 (u,v)(u, v) を選べるのに、uu の容量を親への辺に使い切った最適解があるとします。親への辺を外して (u,v)(u, v) を選んでも本数は変わりません。vv の容量はほかに使い道がなく、親の容量は 11 空きます。

子どうしの間では、どの子との辺を選んでも uu の容量を 11 使うだけで、子の残りの容量はほかで使えないので、どれから選んでも同じです。

各頂点を帰りがけ順に 1 回ずつ見るだけなので、計算量は O(N)O(N) です。

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] は uu の子です。B[u] は子との辺を選ぶたびに減らすので、uu の残りの容量になります。

dp[u] は、uu を見終わった時点では「uu の容量が残っていて、親への辺の候補になるか」を表します。親を見たときに、その辺を選ばなかった子の dp[v] を 00 に戻すので、最後には dp[v] が「vv と親を結ぶ辺を選んだか」になり、その総和が答えです。

使用ライブラリ:cpp_include@4b58304