まず、各頂点において「親との辺を消すときの自分の色を \(c\) として操作できるか」という問題を bottom up に解きます。

頂点 \(u\) で解かなければならない問題は 「頂点 \(u\) のとりうる色の多重集合 \(\setminus \{ c \}\) 」と 「\(u\) の子」の二部グラフに完全マッチングが存在するかどうかです。これは hall の結婚定理 を用いることで、 \(O(1)\) で可能です。

（一般的に色の数を \(σ\) とすれば、考えるべき色の集合は \(O(2^σ)\) 通りです。 今回は条件が特殊なので、高々 \(3\) 通りの頂点集合について hall 条件を確認すればよいです）

よって、Yes / No の判定は \(O(N)\) で可能です。

次に解の復元を top down にします。

頂点 \(u\) において、ある子 \(v\) について「\((c, v)\) のペアを取り除いたときに hall 条件が崩れないかどうか」をすべての \(c\) について判定し、崩れないペアを貪欲に取り除いていけばよいです。これは愚直に行っても \(O(\mathrm{deg} (u) )\) です。

よって線形時間で解くことができました。

実装例(codon)