無向辺を2つの有向辺と見て、スコアが下がる向きに重み$-1$、上がる向きに$+1$、変わらないなら$0$を付与すると、ある有向パスが上りになっている$\Leftrightarrow \min$クエリが$1$である、下りになっている$\Leftrightarrow \max$クエリが$-1$である、と判定できる。
ダブリングLCAの構築をする時に、同時にmin/maxについてもダブリングのテーブルを作っておけばパス$u - v$がbeautifulかどうかは適当に判定できる:
- $u$から根に向けてスコアが上がる限りダブリングで上る。$\operatorname{LCA}(u, v)$の深さより上(inclusive)に行けたら3に行く。
- さらに根に向けてスコアが下がる限り上る。$\operatorname{LCA}(u, v)$の深さより上に行けなかったらfalseを返す。$\operatorname{LCA}(u, v)$の深さより上に行けたら頂上が$u- \operatorname{LCA}$の側にあると記録しておく。
- $v$から根に向けてスコアが上がる限り上る。$\operatorname{LCA}(u, v)$の深さより上に行けたらtrueを返す。頂上が$u-\operatorname{LCA}$の側にあるのに$\operatorname{LCA}(u, v)$の深さより上に行けなかったらfalse。
- さらに根に向けてスコアが下がる限り上る。$\operatorname{LCA}(u, v)$の深さより上に行けたらtrueを返す。
- falseを返す。
山のイメージに従って書くだけなので特に難しいとは感じなかった。でも、振り返ってみると、$u$と$v$を完全に対称に扱ったほうがいい気がする。
