ABC165 F. LIS on Tree

問題

N頂点からなる木が与えられる。頂点iには整数a_iが書かれている。

すべての頂点について、頂点1から各頂点までの最短経路に出現する整数の列での最長増加部分列(LIS)の長さを求めよ。

制約

• 2 <= N <= 2 * 10^5
• 1 <= a_i <= 10^9

解法

数列における最長増加部分列(LIS)はdp+lower_boundで求めることができる。
(dp[i]に対して、無限大で初期化し、lower_boundでa_iを使って更新していく)

木についても同様の方法を考える。
頂点1からどこかの葉頂点までは数列として求められる。
木の場合は、その途中から頂点が分岐しているが、途中までdpテーブルが共通にしたいが保存しておくことは難しい。

テクニックとして、頂点を処理した後に前の状態に戻す(巻き戻し)、という方法が使える。
dfsで頂点1から頂点を辿る。頂点を処理するときはdpテーブルのどこかの値を1つ書き換える。しかし、書き換える前の位置と値を保存しておけば、戻るときにその値に戻せば各頂点でのdpテーブルの状態を揃えられる。