AtCoder Beginner Contest 244 G問題 Construct Good Path

$N$ 頂点 $M$ 辺の単純無向連結グラフ $G=(V=[\![N]\!], E=\{u_j v_j \mid j=1,2, \dots, M\})$ と $0,1$ からなる長さ $N$ の列 $S$ が与えられる.

以下を満たすような $P=(P_1, \dots, P_K)$ を1つ例示せよ.

ただし, 上の条件を満たす $P$ は必ず存在する.

適当な頂点 $r \in V$ を根とする $G$ の全域部分木 $T$ をとる. また, $T$ の Euler Tour $W$ を

$r=W_0, W_1, W_2, \dots, W_{2N-2}=r$

とする.

このとき, 以下のようにして, 条件を満たす $P$ を構成できる.

$P \gets \emptyset$
$P$ の末尾に $r$ を加える.
の順に以下を行う.
- $P$ の末尾に $W_i$ を加える.
- $i \neq 2N-2$ で, $W_i$ が $W_{i-1}$ の親であり, この時点で $P$ に登場する $W_{i-1}$ の個数の偶奇が要求と一致していなかったら, $P$ の末尾に $W_{i-1}, W_i$ の2つを加える.
ここまでで以外の全ての頂点についての偶奇は要求に沿うことができている. そこで, の偶奇の状況において場合分けする.
- $W_{2N-3}, W_{2N-2}$ における偶奇がともに一致しているならば, 何もしない.
- $W_{2N-3}$ における偶奇は一致していないが, $W_{2N-2}$ における偶奇は一致しているならば, $P$ の末尾に $W_{2N-3}$ を加える.
- $W_{2N-3}$ における偶奇は一致しているが, $W_{2N-2}$ における偶奇は一致していないとき, $P$ の末尾に $W_{2N-3}, W_{2N-2}, W_{2N-3}$ を加える.
- $W_{2N-3}, W_{2N-2}$ における偶奇がともに一致していないならば, $P$ の末尾に $W_{2N-3}, W_{2N-2}$ を加える.