問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

無向グラフ $G=(V,E)$ が与えられる. なお,

$V:=\{1,2, \dots, N\}$
$E:=\{A_j B_j \mid j=1,2, \dots, M\}$

である.

ここで, 辺を使って頂点を移動すると, 次のようにポイントが変動する.

$j$ 番目の辺を用いて頂点 $A_j$ から頂点 $B_j$ へ移動すると, ポイントが $C_j$ 増加する.
$j$ 番目の辺を用いて頂点 $B_j$ から頂点 $A_j$ へ移動すると, ポイントが $C_j$ 減少する.

次の $Q$ 個の質問に答えよ.

最初のポイントがの状態で頂点から移動を始め, 頂点にいる状態でのポイントの最大値を求めよ.
- ただし, 頂点 $X_q$ から頂点 $Y_q$ に移動が不可能な場合は移動不可能である旨を報告せよ.
- また, 頂点 $Y_q$ にいる状態でポイントが上に非有界であるときは上に非有界である旨を報告せよ.

制約

$2 \leq N \leq 10^5$
$0 \leq M \leq 10^5$
$0 \leq Q \leq 10^5$
$1 \leq A_j, B_j, X_q, Y_q \leq N$
$0 \leq C_j \leq 10^9$

解法

まず, 2頂点 $X_q, Y_q$ が $G$ において同じ連結成分にない場合は明らかに移動が不可能である.

よって, 以降では2頂点 $X_q, Y_q$ が $G$ において同じ連結成分にある場合のみを考慮すれば良い. また, 頂点間の移動を考えていることから, $G$ は連結であると仮定してもよい.

$G$ は連結であるから, $G$ の全域部分木 $T$ が存在する. また, $T$ をある頂点 $r$ を根とする根付き木とみなす. このとき, 任意の頂点 $v$ に対して, 根 $r$ から移動を始め, 頂点 $v$ まで移動した場合におけるポイントの増減 ${\rm pot}_v$ が定まる. 実際, $rv$ walk はいくつも考えられるが, ポイントの増減の定め方から, 同じ辺の往復によってポイントの増減は相殺される. よって, $rv$ path におけるポイントの増減のみを考えればよい. これは $T$ における BFS や DFS で求めることができる.

$G$ の辺のうち, 全域部分木 $T$ から外れる辺 $e=A_j B_j$ について, $T+e$ における $e$ を含むサイクルを $C$ とする.

${\rm pot}_{A_j}+C_j \neq {\rm pot}_{B_j}$ だった場合, このとき, ${\rm pot}_{A_j}+C_j \neq {\rm pot}_{B_j}$ であるから, $C$ を一方の向きで一周すると, ポイントが増えてしまう. よって, 任意の2頂点 $x,y$ に対して, $x$ から $C$ に向かい, $C$ 上をポイントが増える向きに何周かした後に $y$ に向かうことによって, $y$ に到達した時点でのポイントをいくらでも大きくできる.
${\rm pot}_{A_j}+C_j={\rm pot}_{B_j}$ の場合, このとき, $C$ 上を1周してもポイントは変わらない. よって, $A_j$ から $B_j$ へ移動する方法として $e$ を使うものと $T$ を経由するものがあるが, これらはポイントの増減は一致する. $e$ は全域部分木から外れた辺であったことから, $e$ は無いものとして考えても良い.

以上から, 全域部分木 $T$ から外れる辺 $e=A_j B_j$ のうち, ${\rm pot}_{A_j}+C_j \neq {\rm pot}_{B_j}$ となるようなものが存在すれば, 答えは上に非有界である.

逆に, 全ての全域部分木 $T$ から外れる辺 $e=A_j B_j$ で, ${\rm pot}_{A_j}+C_j = {\rm pot}_{B_j}$ だったならば, 各問における答えは $T$ におけるものを考えれば良く, 特に, $X_q \to r \to Y_q$ と辿る walk を考えればよいので, 答えは ${\rm pot}_{Y_q}-{\rm pot}_{X_q}$ である.