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\) の子の集合である.
これを葉から順に計算する.