hitoare日記

たまに書きます

F - LIS on Tree (AtCoder Beginner Contest 165)

問題リンク

atcoder.jp


問題概要

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でオイラーツアーを使う問題が出たおかげで思いつけた。(あっちはまだ解けてないけど)