AGC014-B - 早稲田大学チームvivid_turtle 知見共有@ ウィキ

面白い問題だったので。

問題のリンク→https://atcoder.jp/contests/agc014/tasks/agc014_b

内容は明快だが、取っ掛かりが難しいな〜という感じで考えていた。だが本質が見えれば単純な問題に帰着する。

今回は辺を何度カウントしたかをmod2で考えるだけで良いのでグラフの形は実は重要でない。#image(http://s2.upup.be/9ItEfUi1U1)

図のように木を根付き木で考える。図より与えられたクエリは分割して考えて良い。そのクエリが偶数個ある時、そのクエリと根までの辺は全て偶数回足されるので問題ない。（例えば(2,7)(3,7)と与えられたら7-根の辺は全て偶数回足されている）
続いて考えるのは奇数個与えられたクエリが存在する時。それらのクエリの内、一番深いノードの上の辺を考えるとこれは奇数回しか足され得ないですね？？
つまり与えられたクエリが全て偶数回登場するか否かだけを調べれば良いという結論に帰着します。

これで計算量O（N+M)で解くことが出来ます！
要らないと思いますが一応ソースコードです→https://atcoder.jp/contests/agc014/submissions/5704264

(writer かっつ）