同じ色の辺を $2$ つ以上子に持つ頂点が含まれる場合、それは美しい部分木ではありません。この判定は容易なので、以降すべての頂点について子の辺の色がすべて相異なるとします。

各頂点について、rank を以下のように定義します。

• 頂点 $i$ について、長さ $M$ の数列 $t_i$ を以下のように定義する。
  • 頂点 $i$ が色 $j$ の辺を子に持たない場合、$t_i$ の $j$ 番目の要素は $0$ 。
  • そうでない場合、$t_i$ の $j$ 番目の要素は、頂点 $i$ から色 $j$ の辺を辿った頂点の rank 。
• $t$ を重複を除いて最大値の昇順（タイブレークは辞書順）に並べて $t_i$ が $x$ 番目（1-indexed）に来るとき、頂点 $i$ の rank は $x$。

葉の rank が $1$ であることは直ちに従います。葉以外の rank は $2$ 以上なので、rankが $2$ になりうるのはすべての子が葉である頂点だけです。このような決め方を繰り返すことで、すべての頂点の rank を求めることができます。

$t_i$ と $t_j$ について、関係を定義しておきます。

• $t_i\leq t_j$ であるとは、$t_i$ のどの要素も $t_j$ の同じ位置の要素以下であることを指します。
• $t_i$ と $t_j$ が 比較可能 であるとは、$t_i\leq t_j$ または $t_j\leq t_i$ が成り立つことを、比較不可能 であるとは比較可能でないことを指します。

このとき、ある部分木が美しい部分木であることの必要十分条件は、どの $2$ 頂点を選んでも $t$ が比較可能であることです。

この事実を認めると小課題8 $(M=2)$ は容易で、マージテクの要領で子から順に確かめていくことで解けます（ $t$ を std::set のようなデータ構造に入れて、マージするときは隣の要素と比較可能かのみを判定すればよいです）。

$M$ が一般の場合、$t$ の非零の要素だけ持っておいて、比較する際は必要なところだけ確認すればよいです。