No.763

頂点 \(a\) について, \(a\) を根とする部分木における連結成分数の最大値を考える. このとき, \(a\) を残した場合の最大値を \(A(a)\), \(a\) を削除した場合の最大値を \(B(a)\) とする.

このとき,

\[\begin{align} A(a) &= \sum_{b \in C_a} \max(A(b)-1, B(b)) + 1 \\ B(a) &= \sum_{b \in C_a} \max(A(b), B(b)) \end{align}\]

となる. ただし, \(C_a\) は \(a\) の子の集合である.

これを葉から順に計算する.