計算量がなぜ間に合うのか自信がない。
ある頂点P(色c)に注目したとき、パスをつくれる頂点は図のようになる。
DFSで戻るときにパスの数を計算しながら、部分木の色のヒストグラムをマージしていく。
(色c以外は合計して、色cは1にする。)
深さが最悪ケースではマージテクをつかうことで計算量を抑えることができる。
逆にマージする色のヒストグラムが大きいときは、二分木が最悪ケースで、深さがlogNに抑えられる。
以上から実行時間が間に合う、のだと思う。
実装時はサイズが大きいヒストグラムをコピーしないよこうに注意する。
作れるパスの数の計算の仕方は図にかいた通り。