AT_cpsco2019_s2_e Mogu Mogu Gummi

[problemUrl]: https://atcoder.jp/contests/cpsco2019-s2/tasks/cpsco2019_s2_e $ N $ 頂点 $ N-1 $ 辺からなる根付き木の形をしたグミ $ G $ があります。 頂点には $ 0 $ から $ N-1 $ の番号が、辺には $ 1 $ から $ N-1 $ の番号がついています。 根は頂点 $ 0 $ です。辺 $ i $ は頂点 $ i $ と $ p_i $ を結ぶ無向辺であり、硬さは $ H_i $ です。 あなたは以下の操作を繰り返して、このグミ $ G $ をより多くの連結成分に分けようとしています。 - 根 $ 0 $ 以外の $ 1 $ つの頂点 $ X $ を選び、根 $ 0 $ と $ X $ を両手で引っ張る。 - 根 $ 0 $ と $ X $ を結ぶパス上にあるすべての辺の硬さが $ 1 $ 減少する。 - 硬さが $ 0 $ になったすべての辺はちぎれて消滅する。 - これによって根と連結でなくなった頂点は $ 2 $ 度と選ぶことができない。 操作を繰り返したあとの、$ G $ の連結成分の個数の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ p_1 $ $ H_1 $ $ p_2 $ $ H_2 $ $ : $ $ p_{N-1} $ $ H_{N-1} $

操作を繰り返したあとの、$ G $ の連結成分の個数の最大値を出力せよ。

### 制約 - $ 2\ \le\ N\ \le\ 5000 $ - $ 0\ \le\ p_i $ - $ 1\ \le\ H_i\ \le\ 10^9 $ - 入力はすべて整数である。 ### 部分点 この問題には部分点が設定されている。 - $ N\ \le\ 300 $ を満たす入力に正解すると、$ 500 $ 点が得られる。 ### Sample Explanation 1 頂点 $ 1 $ または $ 2 $ を合計 $ 10 $ 回選ぶと、$ 1 $ 番目の辺がちぎれ、これ以上操作ができなくなります。 このとき、$ G $ は $ \{0\},\{1,2\} $ という $ 2 $ 個の連結成分に分かれています。 ### Sample Explanation 2 (10:40 更新) 頂点 $ 4 $ を $ 2 $ 回選び、頂点 $ 3 $ を $ 3 $ 回選ぶと、$ \{0\},\{1,2\},\{3\},\{4\} $ という $ 4 $ 個の連結成分に分かれます。