\(N \le 2\) または \(M=1\) の場合は簡単に処理することが出来るため、以降 \(N \ge 3,M \ge 2\) を仮定します。　

以降、端点の色が同じである辺を嬉しい辺と呼ぶこととします。また、辺の深さを端点のうち根から遠い方の深さと定義し、深さ \(k(\ge 1)\) の頂点の集合を深さ \(k\) の円と呼ぶこととします。

ある木をつくることが出来るか判定するために、その木から逆操作を行い始めの状態に戻すことが出来るかを考えます。逆操作は、「隣り合う色の等しい頂点対を選び、片方の頂点の色を好きな色に変更する。」です。以降、操作と言ったらこの逆操作を指すこととします。結論から述べると、木を作ることの出来る条件は以下のようになります。

• 嬉しい辺が $0$ 本の場合
必ず作ることが出来ない。
• 嬉しい辺が $1,2$ 本ある場合
まず、嬉しい辺を操作を用いて深さ $1$ の辺にまで持っていく。そして、以下の条件を満たす木を作ることが出来る。
• 深さ $1$ の頂点の色が $N-2$ 種類以下
• 深さ $1$ の頂点の色が $N-1$ 種類であり、深さ $2$ の頂点と深さ $1$ の頂点の組であって同じ色であるものが存在する
• 嬉しい辺が $3$ 本以上ある場合

必ず作ることが出来る。

嬉しい本が \(0\) 本の場合は自明であり、嬉しい本が \(3\) 本あるときは操作を用いて嬉しい本が \(1,2\) 本かついずれかの条件を満たす場合に帰着出来ます。なので、嬉しい辺が \(1,2\) 本ある場合について証明します。

まず、嬉しい辺を操作を用いて深さ \(1\) の辺にまで持っていきます。条件を満たしていないときに作ることが出来ないことを証明します。

深さ \(1\) の円に色が \(N\) 種類ある場合はどのように操作をしても嬉しい辺の本数を増やすことが出来ないので元の木を作ることが出来ません。 深さ \(1\) の円に色が \(N-1\) 種類あり、深さ \(2\) の頂点の色が全て残り \(1\) 種類の場合もどのように操作をしても嬉しい辺の本数を増やせないことが分かります。

\(2\) 個の条件の片方を満たしている状態ならば深さ \(2\) 以上のある頂点の色を目標の色に変えて、\(2\) 個の条件の片方を満たしている状態に戻せることを示します。

まず、最終的に目指す形としてグラフを根と \(N\) 本のパスに分けたとき、「同じパスに属している \(\leftrightarrow\) 頂点の色が同じである」を目指すこととします。(このような状態にすることが出来ればパス同士の色を swap するのは容易です)

前者の条件を満たしているとき、簡単に後者の条件(またはその上位互換)を満たしている状況を作ることが出来るため今満たしているのは後者の条件とします。さて、このとき深さ \(2\) の頂点と深さ \(1\) の色が等しい頂点の組を利用して長さ \(4\) の全ての頂点の色が等しいパスを作ることが出来ます。そして、深さ \(2\) の円で色が被っている頂点対のどちらかの頂点 \(v\) を選びます。(全ての色が違う場合は適当に選びます)長さ \(4\) のパスが頂点 \(v\) を含むように色を変更します。そして、頂点 \(v\) の子(自分も含む)のうち目標の色と異なる最も深い頂点の色を変更して、更に残った長さ \(3\) のパスを根の部分まで戻します。すると、深さ \(1\) の円の色の種類が \(N-2\) 種類以下であるか深さ \(1,2\) の頂点の組であって色が同じものを取ることが出来ます。(最終的に残っている深さ \(2\) の頂点については、嬉しい辺を \(1\) 本使って色を目標の色に揃えます。)

そして、これを繰り返して深さ \(1\) の円以外は全て目標の色に揃えられたとします。ここで深さ \(1\) の円の色を全て異なる色にします。ここで、深さ \(2\) 以上の頂点の色を変えるタイミングで、その頂点が含まれるパスの今の深さ \(1\) の頂点と同じ色に変更することで目標としていた形にすることが出来ます。よって、上記のいずれかの条件を満たしている場合目標を達成することが可能です。

あとは条件を満たすものの個数を数え上げればよいです。条件を満たさないものの個数を数え上げることにします。嬉しい辺が \(0\) 本のケースは簡単で、\(1,2\) 本のケースは嬉しい辺を深さ \(1\) まで持っていった形を考えると数え上げられます。数え上げに出てくる形は累乗、階乗のみなのでこの問題を \(\mathrm{O}(N + \log M)\) で解くことが出来ます。

実装例