問題の入力の木を \(T\) と呼ぶことにします．

頂点 \(u\) より頂点 \(v\) を後に操作しなければならない，という形の条件をまとめていきます．

まず，任意の \(2\) 頂点 \(u,v\) について，最終的に出来る列で \(u\) より \(v\) が後に登場するための必要十分条件を考えます． \(u\) と \(v\) の LCA を \(w\) とします． 一般に，頂点 \(x\) とその祖先 \(w\) に対し，\(x-w\) パス上の頂点のうち \(w\) を除くすべての頂点を操作し終える時刻を \(M(x,w)\) とします．操作の時刻を \(1,2,\ldots,N-1\) とし，\(x=w\) のときは \(M(x,w)=0\) と定めます． \(M(x,w)\) は，頂点 \(x\) と \(w\) が初めて同じ頂点にマージされる時刻です． よって，最終的な列で \(u\) が \(v\) より前に来るための必要十分条件は，\(M(u,w)<M(v,w)\) となります．

そしてこの条件は，根付き森の形でまとめて表現することが出来ます． つまり，頂点集合 \(\{2,3,\ldots,N\}\) からなる根付き森が存在し，最終的な列が \((1,2,\ldots,N)\) になることと，この森のすべての親子関係について子を親より先に操作することが同値になります． この事実を，森を構築するアルゴリズムとともに示します．

操作の順序の条件を表す森を \(F\) と呼ぶことにします．

頂点 \(2,3,\ldots,N\) をこの順に処理していきます． 今頂点 \(v\) まで処理が終わっているとします．

ここに頂点 \(v+1\) を追加することを考えます． \(v=P_{v+1}\) のケースは自明なので，\(v>P_{v+1}\) のケースを考えます． \(v\) と \(P_{v+1}\) の \(T\) 上での LCA を \(w\) とします． \(P_{v+1}<v\) より，ここまでの条件から \(M(P_{v+1},w)<M(v,w)\) が成立しています． さらに，\(v\) が \(v+1\) より前に来るためには，\(M(v,w)<M(v+1,w)\) が必要十分です． これは結局，\(v+1\) を操作するのは \(v-w\) パス上の \(w\) を除くすべての頂点より遅い，という制約になります．

そこで，\(v-w\) パス上の \(w\) を除く頂点のうち，\(F\) の根であるものから，\(v+1\) への辺を張ることが出来ます． そして逆にこの辺を張るだけで \(F\) の更新は十分です． これは，以下の \(2\) つの事実から従います．

• \(v\) までを処理した段階で \(F\) で根になっている (番号 \(v\) 以下の) 頂点はすべて，\(T\) の頂点 \(1\) から \(v\) までのパス上に存在している．
• \(1\) から \(v\) までのパス上にある頂点 \(x\) であって，\(F\) の根ではないものを考える．\(x\) の \(F\) 上の根を \(y\) とすると，\(y\) は \(v-x\) パス上にある．

これらの事実は帰納的に確認できます．

森を求めたあとの数え上げは簡単です．

森の計算は，\(F\) の根でない頂点 \(v\) と \(P_{v}\) を結ぶ union-find を用意すると高速に行えます．

計算量は \(O(N \alpha (N))\) です．

解答例(C++)