問題リンク
問題概要
N頂点の木グラフと、各頂点に対して整数\(a_i\)が与えられている。
\(1 \leqq k \leqq N\)の全ての整数に対して、次の問題を解け。
問題k: 頂点1から頂点kまでの最短経路上にある頂点の整数をこの順に並べた数列の、最長増加部分列の長さを求めよ。
解法
まず一般の数列\({b_i}\)に対して普通の最長増加部分列問題を考えると、これは有名な問題で、次のDPで解けることが知られている:
\(dp[i][k]=(b_iまでで作れる長さkの増加部分列のうち、最後の要素の最小値\))
とし、
\(dp[0][0] = 0\)
\(dp[0][k] = \infty \) \( (1 \leqq k)\)
と初期化して
\(dp[i+1][k] = min(b_i, dp[i] [k]) \) (ただし\(dp[i] [k - 1] < b_k\)のとき)
\(dp[i+1][k] = dp[i][k] \) (ただし\(dp[i] [k - 1] \geqq b_k\)のとき)
という漸化式を立てることができ、\(A[N][k] < \infty \) となる最大のkが答えになる。
この式で更新されるのは実は\(b_k \geqq dp[i][k]\)となる最小のkの一箇所だけ(\(dp[i]\)は常に単調増加になる)なので、
その場所を二分探索で求めることにより一回の更新が\(O(logN)\)、
全体で\(O(NlogN)\)で答えを求めることができる。
元の問題に戻る。
dpを更新する代わりに、各要素にスタックを用いてスタックのtopをDPテーブルの要素と見て、頂点1からDFSしつつ、
- 頂点に到達したらそこまでの増加部分列の長さを求める
- 更新があればスタックにpushしてから子を探索し、探索し終わった後にpopする
ことで、各kに対して答えを得ることができる。
(追記:わざわざスタックを使わなくても、更新点の更新前を一箇所覚えるだけで十分だそうです。)
提出
https://atcoder.jp/contests/abc165/submissions/12625049
感想
ABC163-Fでオイラーツアーを使う問題が出たおかげで思いつけた。(あっちはまだ解けてないけど)