計算量オーダー \(O(N)\) で解きますが、競プロの範囲では高速化にもならないのであまり役に立ちません。

答えは次のような木 DP で計算できます。

深さが大きい順に計算する。各頂点では、その子それぞれについて元問題を解いて数列を求め、数列を辞書順でソートする。これで、子を訪れる順序が求まる。

なお、これが正しい理由は 公式解説 を参照してください。

これを AHU algorithm で高速化します。 AHU algorithm : cf. https://logic.pdmi.ras.ru/~smal/files/smal_jass08.pdf

頂点 \(v\) の部分木に対して問題を解いて得る数列を、 \(v\) の答え と呼びます。

深さ \(d\) の頂点の個数を \(C_d\) とおきます。

答えを座標圧縮しながら、深さごとに一度に計算します。つまり、深さが \(d+1\) の頂点 \(v\) すべての \(v\) の答えを辞書順で座標圧縮したものがわかっているとき、深さ \(d\) の頂点 \(v\) すべての \(v\) の答えを辞書順で座標圧縮したものを計算量 \(O(C _ d + C _ {d+1} )\) で求めます。

まず、深さ \(d\) の各頂点の子のリストを、答えの辞書順でソートします。まとめてバケットソートをすると線形時間です。

次に、深さ \(d\) の頂点の答えをソートします。 atcoder::suffix_array の引数 upper を用いることでこれも線形時間です。

同じものは座標圧縮後にも同じ番号をつける必要がありますが、隣り合う要素の比較なので線形時間です。

これを用いると、元の問題の全体の計算量は \(O(N)\) になります。

解答例