$N$ 頂点 $ M $ 辺の連結な無向グラフ $G$ が与えられる。
更に、 $1 \le A,B \le N$ かつ $A \neq B$ を満たす整数 $A,B$ も与えられる。
以下の条件を満たす頂点組 $(U,V)$ を数えよ。
- $U \neq A$ かつ $U \neq B$
- $V \neq A$ かつ $V \neq B$
- $U < V$
- $G$ 上の $U$ と $V$ とを結ぶあらゆるパスは、必ず頂点 $A,B$ の両方を通る(通る順序は問わない。)
$4 \le N \le 2 \times 10^5$
$N-1 \le M \le 5 \times 10^5$
嘘方針 : (これで1h以上溶かしました)
「$A,B$ どちらも通る」 = 「$A$ を通る」 + 「$B$ を通る」 - 「$A,B$ どちらかを通る」
反例 : $A=3,B=4$
「$A,B$ どちらかを通るが、どちらでもよい」みたいな場合が上手く数えられない。
真方針 :
- とりあえず $G$ から $A$ を接続された辺ごと取り除く。このとき、 $B$ を含む連結成分にある頂点同士の組は答えにならない (数えるべき組の少なくとも一方は必ず $B$ から孤立する)
- とりあえず $G$ から $B$ を接続された辺ごと取り除く。このとき、 $A$ を含む連結成分にある頂点同士の組は答えにならない (数えるべき組の少なくとも一方は必ず $A$ から孤立する)
- 「 $A$ を消すと $B$ から孤立する」「 $B$ を消すと $A$ から孤立する」に重複はない。
- 証明 : $G$ は連結なのでどの頂点 $u$ についても $u - A - B$ or $u - B - A$ なるパスがある。このことから題意は示される。
- この時点で、「 $A$ を消すと $B$ から孤立する頂点」「 $B$ を消すと $A$ から孤立する頂点」のペア以外は答えになりえないことが分かる。
- 逆に、「 $A$ を消すと $B$ から孤立する頂点数」「 $B$ を消すと $A$ から孤立する頂点数」を掛ければ答えになる。
- 証明 : 左側のある頂点を $l$ 、右側のある頂点を $r$ とする。
- $l$ から $A$ を通らずに行ける頂点は $A$ を消した時に同一連結成分にある頂点だけだが、これらは全て「 $A$ を消すと $B$ から孤立する頂点」である。これに含まれない頂点に移動するには $A$ を通る羽目になる。
- 同様に、 $r$ 側からも「 $B$ を消すと $A$ から孤立する頂点」に含まれない頂点に移動するには $B$ を通る羽目になる。
- この2つの事柄から、「 $A$ を消すと $B$ から孤立する頂点」「 $B$ を消すと $A$ から孤立する頂点」を結ぼうとすると、 $A,B$ 双方を通る羽目になることが言える。よって2つの数を掛けて答えとして良いことが示せる。
Submission #229779750 - Codeforces
本当に信じられないほど沼った。殺してたも～～～
