競技プログラミングにハマるプログラマのスレ 168

219 ：仕様書無しさん：2024/03/28(木) 20:40:39.34 .net

>>198
∑LIS(1,v)=K になるように、条件を満たしながら頂点に値を振る方法

まずは上界、つまり子の値が必ず (自分の値)+1 になっている場合からスタート
頂点 1 に注目する
1 の子 q について、 qの値が 1 の値)+1 になっているなら、qの部分木が含む頂点すべての値をごっそり 1 減らしても（条件）を満たす
これで（qの部分木サイズ）だけ ∑LIS が減らせる

（qの部分木サイズ）-1 だけ減らしたいときはどうするか？
q 自体は減らさず、qの全部の部分木に対して値を減らせばいい

こんな感じに思うと、子の部分木サイズが（残り減らすべき∑LIS）以下だったら減らす、という貪欲でやっていったら0≦x≦(q の部分木サイズ）の任意のxだけ必ず減らせる