ABC165 F - LIS on Tree
問題はこちら
問題概要
頂点の木と, 各頂点に
の値が与えられる. 全ての頂点
に対して, 頂点1から頂点
までのパスを頂点1から見た数列ととらえて狭義最長増加部分列の長さを求めよ.
思考の流れ
ある数列Sが与えられたとき最長増加部分列(LIS)の求め方は, 典型問題である. すべての要素がに初期化された配列Tを用意し, 数列の前の要素から順に見ていき,
の要素の中で
以上で最も右にある要素を二分探索で見つけ, その値を
に書き換える. そのようにしていくと最後には
がLISになっている(
を除く).
今回は木であるがその本質は変わらない. 頂点1からDFSを行い, 頂点1からその頂点までのLISを含んだ配列を求めていくと答えを求めていくことができる. DFSで戻る際に, 書き換えたところを戻すような操作を行うことですべての頂点に対して高速に求めることができる. このようにDFSで戻るときに適切な操作を行い高速化する問題は
とかで出てる.
提出プログラム
https://atcoder.jp/contests/abc165/submissions/12649528
感想
すぐわかった. 本番でもみんな結構解けてたみたい.
