これが解けないのは悔しいんだけど、まあ難しいね...。

問題

考察と解法

　まず、どの3つのスイッチを取っても、その3つに関わるランプは存在しないという条件に注目する。これは、各ランプについて、押すと影響のあるスイッチは高々2つしかないことを言っている。そうなると、ランプを辺、スイッチを頂点としたグラフを考えたくなる。とりあえず、すべての辺が2つの頂点を結んでいる場合を考えよう。
　このグラフの頂点(スイッチ)に黒か白の色を塗ることを考えよう。最初はすべての頂点は白色で、これはスイッチがoffであることを表す。黒色に塗ると、これはスイッチがonであることを表す。このように考えると、辺(ランプ) $i$ について、そのランプが点灯しているときは、以下の制約を満たす必要がある。

$S_i = 0$ のとき、辺の両端の色は異なる
$S_i = 1$ のとき、辺の両端の色は同じ

この制約を満たすように色を塗るとき、黒色の頂点を最小で何個塗ればよいかということを答えよというのがこの問題の要求となる。
　さて、すべての頂点が白い状態から、番号が $i$ 以下の辺が制約を満たすように黒く頂点を塗っていくことを考えよう。ある頂点 $v$ を黒色に塗ることにすると、そのスイッチを繋ぐ辺のうち番号が $i$ 以下の辺があれば、上の制約より、辺が繋ぐのもう一方の頂点の色が決定することになる。この決定は連鎖するので、 $i$ 以下の辺でつながれた連結成分ごとに状態が決まっていくことになる。頂点 $v$ を塗らないことにしても、連鎖は同様にしておこる。つまり、取り得る状態は連結成分について高々2つしかなく、このうち黒い頂点の数が少ない方がわかればよいことになる。この計算が高速に行えればよい。
　制約の要となるグラフの辺をどんどん増やしていきながらクエリに答える問題なので、Union-Findを使った解法を考えるのは不自然ではないだろう。ここでは、頂点を倍加するテクニックを用いる。つまり、グラフの頂点として、( $v$ ,白)と( $v$ ,黒)という $2K$ 個の頂点を用意し、最初は辺が1本もない状態からスタートする。また、頂点を黒く塗ることにはコストがかかるので、( $v$ ,黒)に重み1を載せておく。辺 $i$ を追加するとき(頂点 $u,v$ を結んでいるとする)は、次のような併合操作を行う。

$S_i = 0$ のとき、( $u$ ,白),( $v$ ,黒)を併合して、( $u$ ,黒),( $v$ ,白)を併合する
$S_i = 1$ のとき、( $u$ ,白),( $v$ ,白)を併合して、( $u$ ,黒),( $v$ ,黒)を併合する

併合のときに、連結成分内の重みの総和も更新する。すると、辺 $(u,v)$ の属する連結成分の答えは、( $u$ ,白)が属する連結成分の重みと、( $u$ ,黒)が属する連結成分の重みであることがわかる。両者は同じ連結成分に属することはない。今回は問題の入力として必ず条件を満たすスイッチの押し方が存在することが保証されているので、矛盾が生じる(前述したように、あるスイッチの状態を決定した後に、状態の決定が連鎖していく中で黒かつ白である必要のある頂点が現れること)ことがないからである。この処理を辺1から順に行い、答えを適宜更新してくことでこの問題が解ける(実装の項参照)。
　ある辺が1つの頂点としか結ばれていないときの扱いは、あらたにスイッチ $X$ を用意し、( $X$ ,白)と( $X$ ,黒)という頂点を用意して同様の処理を行うことにする。ここで、( $X$ ,黒)のコストを5000兆などの十分大きい数にしておけば、 $X$ が黒く塗られるようなスイッチの押し方が最適解となることがなくなるのでうまくいく(結局、 $2K+2$ 個の頂点を用意することになる)。