ABC 318G Typical Path Problem

## 趣旨

AtCoder Beginner Contest 318 G Typical Path Problem を，(公式解説の方法でなく) block cut tree を使って解くこともできると思うのですが，根拠 (下の「命題」) が自分にとってあまり自明でなかったので，証明を書きます．

block cut tree や，関連する概念 (二重連結グラフなど) については，[別の記事](https://yamate11.github.io/blog/posts/2023/09-05-bridge/) を参照してください．

## 問題と解答方針

[問題へのリンク](https://atcoder.jp/contests/abc318/tasks/abc318_g)

概略としては，連結単純無向グラフ $G$ と，その異なる3頂点 $A$, $B$, $C$ が与えられるので，
$B$ を経由して $A$ と $C$ を結ぶ単純パスが存在するかどうか判定せよ，というものです．
頂点数と辺の数は $2\times 10^5$ 以下．

block cut tree で解けそう，という感じはします．block cut tree 上で $A$ と $C$ を結ぶパスを考えておいて，$B$ がそこから大きく外れたら (間に関節点を入れなければならないような位置にあったら) ダメ．という感じです．ただ，base case (?) として，次の命題が成り立たないといけないわけですが，それがすぐに分かりませんでした (簡単なのでしょうか?)．

#### 命題1

> 二重連結グラフ上に異なる3点 $A$, $B$, $C$ があるとき，$A$, $C$ を両端とする単純パスで $B$ を通るものが存在する．

これを認めれば，問題は，次のように解けます:

もとのグラフ上の頂点 $X$ に対し，block cut tree 上の頂点 $p(X)$ を，$X$ が関節点の時には，その関節点に対応する頂点として，そうでないときには $X$ が属するブロックに対応する頂点として定義する．
* $A$ と $C$ が同一ブロックに属するとき
  * $B$ もそのブロックに属するときには，命題 1 より Yes と判定する．
  * そうでない時には，$A$ から $B$ までのパスと $C$ から $B$ までのパスは同一関節点を通るので，No と判定する．
* $A$ と $C$ が同一ブロックに属さないとき
  * link cut tree 上で，$p(A)$ と $p(C)$ を結ぶ単純パス $\tilde\pi$ 上に，$B$ が属するブロックが存在するときには，Yes と判定する．理由は次の通り．$A$ と $C$ を結ぶ任意の単純パス $\sigma$ をとる．
    * $p(B)$ が $\tilde\pi$ 上にあるときには，$\sigma$ 上に $B$ が存在する．
    * そうでないときには，$\tilde\pi$ 上の，$B$ が属するブロックの直前と直後の 関節点を $D$, $E$ とする．$D$, $E$ は $\sigma$ 上にある．$D$, $B$, $E$ に対して命題1を適用して得られるパスで，$\sigma$ の，$D$ から $E$ までの部分を差し替えれば，題意を満たすパスが得られる．
  * そうでない時には，$A$ から $B$ までのパスと $C$ から $B$ までのパスは同一関節点を通るので，No と判定する．

ということで，以下，命題1を証明します．

## 命題1の証明

補題を準備します．

#### 補題2

> (3点以上からなる単純) 二重連結グラフ $G = (V, R)$ は，サイクルから出発して，すでに構成された2点を結ぶ単純パスを追加することで構成される．正確には次の通り:
> 以下を満たす $V$ の部分集合 $V_0, V_1, \ldots, V_k$ ($k \geq 0$) が存在する．$V_i$ が導出するグラフを $G_i$ とするとき
> * $V = \bigcup \\{V_i \mid i = 0, 1, \ldots, k\\}$
> * $V_i \cap V_{i + 1}$ は，2点 $p_i$, $q_i$ からなる集合
> * $|i - j| \geq 2$ のときは，$V_i \cap V_j = \varnothing$
> * $G_0$ はサイクル
> * $G_{i + 1}$ は，$p_i$ と $q_i$ を端点とする単純パス
> * 各辺$pq$ について，$p, q \in V_i$ となる $i$ が存在する．

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/504530/db350cee-2b6a-5a1b-8772-82d193d2ce40.jpeg" width="250px">

#### 補題2の証明

まず，$V_0$ を作る．このために異なる3点，$x, y, z \in V$ をとる．$G$ は連結なので，一般性を失うことなく，$y$ と $x$ を結ぶ単純バスと $y$ と $z$ を結ぶ単純パスが取れる．これらのパスに共通に現れる点がある場合には，それを $y$ に取り直してパスを短くしていくことにより，$x$ と $z$ を結ぶ単純パスで，その上に $x$, $z$ のいずれとも等しくない点 $y$ があるものが取れる．$G$ は二重連結なので，$y$ を取り除いても $x$ と $z$ を結ぶパスがある．これらを用いて$x$, $y$, $z$ をその上に持つサイクル $C$ がとれる．$C$ 上の隣接しない2点 $p$, $q$ で，辺で結ばれているものがある場合には，それをショートカットしてサイクルを短くしていくことにより，そのような2点のないサイクルを作成することができる．これを $V_0$ とすれば，$G_0$ はサイクルになる．$V_0$ の大きさは3以上であることに注意する．

$V_m$ まで構成できたとして，$U_m := \bigcup \\{V_i \mid i = 0, 1, \ldots, m\\}$ とする．$V \setminus U_m \neq \varnothing$ であれば，$x \in V \setminus U_m $ をとる．$y \in U_m $ をとって，$y$ から $x$ に至る単純パスを取る．このパス上にあって$U_m$ に属する最後の点を改めて $y$ とし，$U_m$ 上にあって $y$ に隣接する点を $z$ とする．$G$ は二重連結なので，$z$ から $x$ に至る単純パスで，$y$ を通らないものがある．このパス上にあって $U_m$ に属する最後の点を $w$ とする．パス $y - x - w $ を，上でサイクルを作成したときと同じような方法で短くすることで，$V_{m + 1}$ を構成することができる．(終)

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/504530/e079e846-7885-85da-54cc-3199b53d7123.jpeg" width="250px">

#### 命題1の証明

補題2にいう構成に関する帰納法で，次の2つを証明する．$U_i := \bigcup \\{V_i \mid i = 0, 1, \ldots, i\\}$ とする．

* (あ) $U_i$ 上に異なる3点 $A$, $B$, $C$ をとると，$A$, $C$ を端点とする単純パスで，$B$ を通るものが存在する．
* (い) $U_i$ 上に異なる4点 $A$, $B$, $C$, $D$ をとると，$A$ と $C$，$B$ と $D$ を結ぶパスで共通部分を持たないものが存在するか，もしくは，$A$ と $D$，$B$ と $C$ を結ぶパスで，共通部分を持たないものが存在する．

$i = 0$ のときは，サイクルだから明らかである．$i + 1$ の場合は，丁寧に場合分けしてできる．文章で書くのは手間がかかるので，図で済ますことにする．

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/504530/8de9f372-22a7-dfc4-b1a1-911099db3300.jpeg" width="400px">

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/504530/1e60ed1a-09f1-a779-36ef-e2b189004f38.jpeg" width="400px">