公式

D - LIS on Tree 2 解説 by nok0


[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)\) となります.

投稿日時:
最終更新: