この問題はDFSにより解くことが出来ます。

「頂点1からいまいる頂点までの経路上に存在する各色の頂点の個数」の配列を用意しておき、頂点への進入/退出時にこれを更新すればよいです。

この配列の更新は \(O(1)\) であり、この配列を使えばよい頂点かどうかの判定は \(O(1)\) で行えるので、全体で \(O(N)\) で解けました。