考察
元 graph の余分な辺は使わなくてもよく、連結性から任意の spanning tree 上だけで path を構成できる。木なら子部分木を往復する DFS walk により、部分木内の parity を bottom-up に確定できる。
子 c の構成列が c で始まり c で終われば、親 v からその列へ入り v へ戻れる。c の parity が不足した場合に (v,c) を余分に挟むと c だけを1回、vを後の帰還と合わせて2回追加して補正できる。
採用する候補: spanning tree を根付け、各子の閉じた walk を連結しながら子根 parity を局所 gadget で直し、最後に根だけを補正する。
処理済み子孫の parity を壊さず親へ戻る不変条件を保ち、各 tree edge を定数回使う長さ上限付き構成になる。
棄却する候補: s_i=1 の頂点を個別に訪れる path を連結していく。
二つの目的地を結ぶ途中頂点の訪問 parity も変わり、独立な要求として処理すると既に合わせた頂点を壊す。
子 c の parity が不一致なら A_c の後に v,c を置き、その後の通常の v 帰還まで含めると、c は奇数回、v は偶数回だけ追加される。
根以外を全て確定した後、根だけ不一致なら neighbor u,r,u を末尾へ足すと u は2回、根は1回増えて根だけを反転できる。
全0 target なら空 path を出してよい。それ以外は spanning tree を作り、各 v で v を置いて子の列を再帰連結し、子 parity が target と違えば v,c を追加して v へ戻る。root 列完成後に必要なら u,root,u を追加し、長さと列を出力する。
典型の発動条件
spanning tree 上の構成
発動条件: 連結 graph で任意の辺を使えるが、構成の正当性を階層的に管理したいとき。
余分な辺を捨てて tree にし、部分木ごとの不変条件を帰納的に保つ。
局所 parity 補正 gadget
発動条件: walk の連結性を保ちながら特定頂点の訪問 parity だけを直したいとき。
tree edge の往復回数を組み合わせ、他頂点への追加を偶数回にする短い列を設計する。
問題固有の要素
子補正 v,c と次の v への帰還を一まとまりで見ると、親への影響が偶数に相殺され、子だけを確定できる。
別の問題へ持ち帰る視点: parity 構成では操作列を単発で見ず、局所 gadget 全体の各要素出現 vector mod 2 を計算する。
正当性
子の補正は、その子の訪問回数だけを奇数回増やし、親は偶数回増やす。すでに合わせた子孫には触れないので、部分木ごとに要求を確定できる。最後の根の補正も隣接点を二回訪れるだけであり、他頂点の偶奇を変えない。
実装上の注意
- 連結列の隣接頂点が必ず tree edge になる順序を守り、実際に append するたび parity 配列を XOR すると判定が安全になる。最後に長さ≤4Nと全 bit一致を検査する。
復習の核
- leaf c の target が0/1の二場合で出力列中の v,c の追加回数を mod 2 で数え、親 parityを途中で確定しない理由を理解する。
計算量と制約
時間
O(N+M)、spanning tree DFSと定数回parity補正。
空間
O(N+M)、出力walk長O(N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 10^5; N-1 \leq M \leq \min\lbrace 2 \times 10^5, \frac{N(N-1)}{2}\rbrace; 1 \leq u_i, v_i \leq N; The given graph is simple and connected.; N, M, u_i, and v_i are integers.; S is a string of length N consisting of 0 and 1.
出典