1. 必要な知識
・セグ木
・LCA
2. やりたいこと
以下のような問題を解きたいです。
頂点に重みがついた $N$ 頂点の木が与えられます。以下のクエリを $Q$ 回処理してください。
・$2$ 頂点 $x,y$ が与えられる。$x-y$ 間のパス上にある頂点の重みの最大値を求めよ。
制約
$1≤N,Q≤2×10^5$
難しいですね。
3. 解き方
まず、入力で与えられる木を根付き木にします。根は適当に決めてください。
また、頂点 $x,y$ のLCAを $z$ とします。
すると、$x-y$ 間のパスは$x-z$ 間のパスと $y-z$ 間のパスの $2$ つに分解できます。
よって各クエリで答えるべき値は、$max(($ パス $x-z$ 上の頂点の重みの最大値 $),($ パス $y-z$ 上の頂点の重みの最大値 $))$ となります。
ではそれぞれをどう求めればよいのでしょう？
→そう、セグ木を使うのです！！！
発想としてはこうです。
「根からある頂点までのパスは見ようによっては列なのでは？→ということはセグ木が使える！」
根から頂点 $x$ までのパス上の頂点の重みをセグ木に載せることを考えます。セグ木上のindexは各頂点の深さに対応します。
すると、パス $x-z$ 上の頂点の重みの最大値を求めるクエリはセグ木上での $[($ 頂点 $z$ の深さ $),($ 頂点 $x$ の深さ $)]$ に対するRMQと同義になります。
$x$ を $y$ に置き換えても同じことが言えます。
これをそのまま実装することで、この問題を $O(NQlogN)$ で解くことができました。
...はい、冗談です。しっかり高速化して、$O(NlogN+QlogN)$ まで落とします。
では具体的にどうすればいいのでしょうか？
ここで登場するのがクエリ先読みです。
つまり、DFS をしながらクエリに答えてあげればよいのです。
以下に具体的なやり方を図付きで示します。
図中の木は頂点 $1$ を根とし、$x=4, y=5$ なるクエリに答えようとしています。
また簡略化のため、頂点の番号と頂点の重みは等しいものとします。
見ての通り、頂点 $4$ と頂点 $5$ の LCA は頂点 $3$ です。
セグ木上にある頂点には色が塗られていて、DFS で今訪れている頂点は赤で塗って区別しています。
根からDFSを行い、今見ているのは頂点 $4$ です。
セグ木には頂点 $1-$ 頂点 $4$ 間のパスに含まれる頂点の重みが載っています。
ここで、セグ木を用いて $[1,2]$ における最大値を求めます。(セグ木は 0-index とし、左端と右端はそれぞれ頂点 $3,4$ の深さに一致します)
その後見る頂点を変え、頂点 $5$ に移動します。
セグ木を更新し、$2$ 番目の要素を頂点 $5$ の重みに変えます。
こちらも先程と同様に、セグ木を用いて $[1,2]$ における最大値を求めればよいです。
それぞれの最大値は $4, 5$ なので、それらの $max$ である $5$ がこのクエリに対する答えです。
この流れはクエリが増えても同じで、計算量は $O(NlogN+QlogN)$ になります。
必要な情報は隣接行列などを用いて頂点ごとにメモしておきましょう。
4.このテクのメリット/デメリット
メリット
・HLD などの難しい知識が要らない
・重みが辺についていても対応でき、守備範囲が広い
・愚直な HLD よりオーダーが良い
デメリット
・HLD とは違い貼るだけにはならない
・更新クエリが飛んできた瞬間破滅する
5.解ける問題
ネタバレを含むので要注意です！
PAST2-O
https://atcoder.jp/contests/past202004-open/tasks/past202004_o
まんまですね。重みが辺についているだけです。
以下、自分の提出です。
可読性が低いのはご容赦を...
https://atcoder.jp/contests/past202004-open/submissions/16401479
技術室奥#5 Day2-H Second Path
https://yukicoder.me/problems/no/1212
このような問題にも応用が効くのがメリットです。
また、このテクはこの問題のために生み出されました。
以下、自分の提出です。Writerコードなので、PAST-O のものよりは読みやすいと思います。
https://yukicoder.me/submissions/542864
6.おわりに
これは僕の初記事です。ミスなどがあれば修正するので、連絡をいただけると幸いです。
元々このテクは前述の Second Path のWriter解として編み出されたのですが、本番でこのテクを使っている人がほとんどおらず、もったいないなと感じたのでこうして記事にしました。
参考にしていただけたら幸いです。