CF395

Eの賢い解法を見つけたのでメモのついでに

A:
色が異なるu-vを見つけたらuかvを選ばねばいけない

B:
x1%2,y1%2で類別すると同じのは接さない

C:
N=1,Mを除いておくと、総和の式からxとdの一次式が出てくる.同様に二乗和の式による制限によって高々二通りにまで制限できるので、これを満たすか判定してから、OKならまともに判定すればよい.(最後の判定いらないかも(解2つは+-の方に対応している気がする))

D:
hash
解いてないけど、
rng-58.blogspot.jp
がかなりためになる

E:
Bellをキーにしてdpの遷移をsegtreeに載せるんだけど、別に遷移先が一意に定まるのでdoublingっぽくするだけで合成とか考えなくて良い.クエリはlogN.

賢い解法を見つけた.
Submission #24402210 - Codeforces
とりあえず単に左から順にdfsで全連結成分を求める.
区間が与えられたら、とりあえずdfsの根の数を数える.本来の根が入って　ない連結成分をあとは数えれば良くて、これは、(区切られた後の)連結成分の内「dfsの値が一番小さいもの」の数を数えればよく、これを満たす頂点は絶対に区間の端っこK個に入っている.
理由:根は左にある、区間の外にある場合は左K個に入ってるはずで、内側にある場合は区間の右にはみだしてその後戻ってくるという形になっているが、このときは右K個に入っている.
判定するのは簡単(区切った後につながってるものとdfsidの大小を見るだけ)なので、解けた.
前処理O(NK),クエリO(K^2).

これ天才的だと思うんだけど