フローを使わないものを説明します．簡単のため色を \(0, 1, 2\) とします．

また，辺を消す操作をイベントとして定義します．イベントの情報としては，辺の端点と，消す際の端点の色を持ちます．

根付き木として捉え，根以外の頂点について，「自分の親とを結ぶ辺を消す操作について，自分の色を \(c\) として行えるか」を管理する DP を行います．\(c\) として考えるのは \(0, 1, 2\) の全てです．また，可能な場合はそれを実現する部分木についてのイベントの列も管理します．

部分木 DP を考えます．自分の子について，自分とマッチングするとき相手の色は何にできるか，という情報がわかっています．

自分の色をうまくマッチングさせたいです．まず，自分の子 \(x\) について，マッチングするときの \(x\) の色が一意でないならば無視して構いません．

すると，以下のような問題になります．

• 整数集合 $S$ には $0, 1, 2$ がそれぞれ $X, Y, Z$ 個ある．
• 整数集合 $T$ には $0, 1, 2$ がそれぞれ $A, B, C$ 個ある．
• $T$ の各要素について，$S$ の要素を $1$ つずつ選びマッチングしたい．ただし，同じ値同士はマッチングできない．

これは，\(T\) の \(0\) とマッチングする \(S\) の \(1\) の個数を全探索することで解くことができます．

これを用いることで，部分木 DP の更新が \(O(N)\) ででき，全体で \(O(N^2)\) となります．

おそらくですが，この方針を高速化することで準線形時間などで解けるとは思っています．