この問題は以下の動的計画法 (木DP) を用いて \(O(N)\) 時間で解くことができます。

\(dp[v][i]\) \(=\) \(v\) を根とした部分木について選んだ葉の数の偶奇が \(i\) であるときの黒で塗られた頂点の数の最大値

頂点 \(v\) を根とした部分木に対して、頂点 \(v\) が何色になるかは部分木に属する選んだ葉の数によって決まります。また、頂点 \(v\) の色が反転するときは選んだ葉の数が奇数のときであるので、選んだ葉の数の偶奇を持てばよいです。

この木DPは次のようにして解くことができます。

• 葉である頂点 \(v\) については、その頂点の色に応じて \(dp[v][i]\) に値を入れます。
• 葉でない頂点 \(v\) については \(v\) の各子 \(u\) について以下のように更新し、すべての子に対して更新をした後に \(dp[v][(1 + A_v) \mod 2]\) に \(1\) を足します。

\[dp[v][0] = \max(dp[v][0] + dp[u][0], dp[v][1] + dp[u][1])\]

\[dp[v][1] = \max(dp[v][0] + dp[u][1], dp[v][1] + dp[u][0])\]

実装例 (C++)