Tree Cutting (Easy Version)
適当に根を決めて根付き木として考える
辺全体n-1本からniceでない辺の本数を引いて答えを求める
これは各頂点iについて
num_blue[i]:頂点iを根とする部分木にある青の頂点の個数
num_red[i]:赤の頂点の個数
が分かればいい(そして、これらは木DPというかdfsというかで簡単に計算できる)
実際、親iから子jへの辺がniceでない条件は
頂点iを含む連結成分に青頂点・赤頂点がそれぞれ1個以上ある
or 頂点jを含む...(同上)
であるが、各連結成分内の赤頂点・青頂点の個数は次のように求まる
頂点iを含む連結成分について
青頂点の個数:num_blue[根] - num_blue[j]
赤頂点の個数:同様
頂点jを含む連結成分について
青頂点の個数:num_blue[j]
赤頂点の個数:同様
これは図を見ると分かる(ほんと?)i, jに親子関係があるのが大事そう
https://gyazo.com/4cde3ae563b8b17e75f4a78955b22d2b