[1] \(f(P)\) の値域

\(f(P)\) の取り得る値の範囲を求めましょう．頂点 \(i\) の頂点 \(1\) からの距離を \(d_i\) とすると，\(g_i\) は \(1\) 以上 \(d_i + 1\) 以下の値を取ることが分かります．

このことから，\(f(P)\) の範囲は \(N\) 以上 \(N+\sum_{i=1}^N d_i\) 以下であることが分かります．\(K\) がこの範囲外のとき，答えは No です．実は，\(K\) がこの範囲のとき，必ず \(f(P)=K\) なる \(P\) が存在します．

[2] 部分和問題への帰着

最長増加部分列（以下 LIS）の長さについて，以下が成り立ちます．

• 列の末尾に要素を一つ追加したとき，LIS の長さは変化しないか，\(1\) 増加するかのいずれかである．

頂点 \(i\) を根とする部分木のサイズを \(w_i\) とします．末尾に\(P_{s_i}\) を追加することで LIS の長さが増加するような頂点集合を \(S=\lbrace s_1,\ldots,s_k\rbrace\) と決め打つと，\(f(P)\) の値は

\[ f(P)=N+\sum_{i=1}^k w_{s_i}\]

と求めることが出来ます．

以上より，\(N-1\) 個の要素 \(w_2,\ldots,w_N\) があり，その中から何個か選び要素の和を \(K-N\) に出来るかという問題に帰着されます．（決め打った \(S\) を達成するような \(P\) の構築方法については後述します．）

これはまさに部分和問題です．しかし，一般には部分和問題を高速に解くことは難しいです．

[3] \(w_i\) の性質を活かす

本問題では，\(w_i\) が部分木のサイズという特殊な制約がありました．実はこの性質を用いることで，部分和問題を貪欲法によって解くことが出来ます．

具体的には，\(w_i\) を値の降順に並び替え順に見ていき，見ている要素を選んでも和が \(K-N\) 以下ならば選ぶという貪欲法が正当です．この正当性は木のサイズに対する帰納法によって示せます．

[4] \(P\) の構築方法

[3] により \(S\) を求められたので，あとは末尾に\(P_{s_i}\) を追加することで LIS の長さが増加するような頂点集合が \(S\) となるような順列 \(P\) を求めればよいです．

これには様々な構築方法が考えられますが，ここでは Writer の方法を紹介します．

\(i=1,2,\ldots,N\) に対して，\(x_i\) を \(i\in S\) ならば \(x_i:=d_i\), \(i\notin S\) ならば \(x_i:=-d_i\) と定めます．\(x_i\) の昇順に \(P_i\) に \(1,2,\ldots,N\) を割り当てると，この \(P\) は確かに条件を満たすことが確認できます．

計算量はソートがボトルネックとなり \(\mathrm{O}(N\log N)\) となります．