考察
一edge操作は両端lampをtoggleするため、各connected component内のon個数parityは常に偶数である。size sのcomponentで到達可能な最大on数は最大の偶数2floor(s/2)で、全component合計をYとする。postorderで非root頂点vがoffならparent edgeをtoggleしてvをonに固定してからvを切り離す。この操作はvをoff→on、parentをtoggleするので全体on数は0または2増え、component終了時にはroot以外全てon、parityによりちょうど2floor(s/2)個onになる。
採用する候補: DFS forestの帰りがけに必要なparent edgeだけ使い、on数がKになった時点で止める
各edgeを高々一度使い、on数を0からYまで0または2ずつ単調に増やす構成が得られる。
棄却する候補: 任意edgeを選ぶ状態空間BFS
lamp状態は2^N通りで、N=2×10^5では探索できない。
全componentでDFS spanning treeとparent edgeを記録しY=Σ2floor(size/2)を計算する。Kが奇数またはK>YならNo。そうでなければ各treeをpostorder走査し、v≠rootがoffならparent edge IDを答えへ追加して両端stateをtoggleする。on countがKになった瞬間に停止してedge列を出す。
典型の発動条件
parity invariant
発動条件: 一操作が各component内のbitを二つ反転する。
on個数の偶奇が0から変わらないことを必要条件として使う。
spanning tree上のleaf elimination
発動条件: 任意graphでedge操作構成が必要だがcycleは不要である。
DFS treeを葉から処理し、各非root頂点の最終stateをparent edge一回で確定する。
問題固有の要素
leaf elimination中のon数が減らないため、最終最大値だけでなく途中の全偶数値を必ず通り、希望Kでprefixを切れば構成になる。
別の問題へ持ち帰る視点: 単調な構成processが到達値を刻み幅ごとに通過するなら、途中停止で全中間目標を実現できる。
正当性
一辺toggleはon数parityを変えず成分ごと最大偶数2floor(size/2)が上界。postorderでoff子を親辺でonにすると親がoffならon数+2、onなら±0で減らない。最終各非根がonで上界Yへ達し、0..Yを2刻みで通るため任意偶数Kで停止可能。
実装上の注意
- K=0なら操作0回で即終了する。edge IDは入力番号を保存し、component rootにはparent edge操作を行わない。
復習の核
- 孤立頂点、奇数/偶数size componentの混在、K=0・Y、parentがonのため増分0となるstepをsimulationして最終個数を確認する。
計算量と制約
時間
N頂点M辺。spanning forestとpostorder O(N+M)、出力O(N)。
空間
木親辺、色、走査順 O(N+M)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^5; 0 \leq M \leq \min\left( 2 \times 10^5, \frac{N(N-1)}{2} \right); 0 \leq K \leq N; 1 \leq u_i < v_i \leq N; The given graph is simple.; All input values are integers.
出典