https://codeforces.com/contest/1153/problem/D
頂点1が根、N頂点の根付き木がある。
各頂点にはmin, maxが付いている。
木の葉の数をKとすると、木の葉には1～Kを1つずつ割り当てられる。
葉でない頂点の数は子のminかmaxになる（頂点についているmin,maxに従う）。
葉に適切に1～Kを割り当てて、頂点1の数を最大化せよ。
N≦3*10^5
前提知識
解説
https://codeforces.com/contest/1153/submission/52727503
木DPで解く（貪欲法に近いかもしれないけど）。
dp[cu] := 頂点cuの部分木で{葉の数, 最適に葉に数を割り当てたときに小さい方から何番目の数が頂点cuに来ているか}
これを使って計算していく。
まず、葉はそのまま使うしか無いので、{1,0}を返す。
各頂点では葉の数は固定なので、二番目の要素をなるべく大きくするような貪欲をしていく。
minのとき
以下の例で説明する
子供が{3,0}, {2,1}であるとする。
これを以下の様に表記しておく
Abc, dE
これらに1～5を割り当てて、かつ、マージしたときのminが大きくなるようにする。
数の大小関係としてA＜b＜c, d＜Eは変えられないので、
dAEbcとすると、A=2, E=3となり、マージしたときのminは2となり最大化できる。
多分わからないので、もう一例出しておく。
子供が{4,2}, {3,1}であるとする。
これを以下の様に表記しておく
abCd, eFg
これらに1～7を割り当てて、かつ、マージしたときのminが大きくなるようにする。
数の大小関係としてa＜b＜C＜d, e＜F＜gは変えられないので、
abeCFdgとすると、C=4,F=5となり、マージしたときのminは4となり最大化できる。こういう感じなのだが、minのときは、各子に対して、最適に割り当てたときに使われている数より小さい数を集めてくるのが最適となる。
よって、{葉の数の総和, 最適に割り当てたときに使われている数より小さい数の個数の総和}を返す。
maxのとき
minのときがわかっていれば、同様に最適な方針を考えるだけでいい。
こちらでは、maxなので、ある子をmaxとして使うことが決まれば、他の子は全て小さい数にすればいいので、
{葉の数の総和, ある子の最適に割り当てたときに使われている数より小さい数+他の子の葉の数の総和}の最大値を返せばいい。
int N, F[301010]; vector<int> C[301010]; //--------------------------------------------------------------------------------------------------- pair<int, int> dfs(int cu) { if (C[cu].size() == 0) return { 1, 0 }; if (F[cu] == 0) { // mi int top = 0, sz = 0; fore(to, C[cu]) { auto p = dfs(to); top += p.second; sz += p.first; } return { sz, top }; } else { // ma vector<pair<int, int>> ps; fore(to, C[cu]) ps.push_back(dfs(to)); int tot = 0; fore(p, ps) tot += p.first; int top = -1; fore(p, ps) chmax(top, tot - p.first + p.second); return { tot, top }; } } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> F[i]; rep(i, 1, N) { int p; cin >> p; p--; C[p].push_back(i); } auto p = dfs(0); cout << p.second + 1 << endl; }
