AtCoder Grand Contest 014 B. Unplanned Queries

とても面白かった。典型的な"よく考えると自明"な問題な気がする。

今見てみたらあっさり解けたんだけど、この前問題を見た時は20分ぐらい考えて、「は？？本当に500点か？？？」とキレながら諦めた覚えがある。別に今でもこの問題が簡単だとは思ってないし苦手だなあ。

ただ、点数自体は、解けた今となっては、500点が適正だと思う。

木上の、u,v間のパスに対するクエリをQ(u, v)で表すこととする(ここではパスu, v上の辺に重みを1足すクエリ(をベクトルを返す写像的に捉えて欲しい))。

この時、w = lca(u, v)として、

Q(u, v) = Q(w, u) + Q(w, v) = Q(root, u) + Q(root, v) - 2*Q(root, w)

というのはまあそれはそうだし結構よく使う分解なわけですが、

今mod 2を気にしていることを考えると、Q(u, v)をQ(root, u) + Q(root, v)に変換して良い。

これに気づくと一瞬。

というのも、今、考えている木を、適当な頂点を根として根付き木にする。

明らかに、「ある頂点vからその親p(v)への辺(v, p(v))の重みが偶数である」ことと、「『vを根とした部分木に含まれる頂点全て』の、クエリに登場する回数の総和が偶数である」ことは同値。

この事から考えると、「全ての辺の重みが偶数である」ためには、「任意の頂点vについて、vがクエリに登場する回数は偶数である」ことが必要十分となる。

これはとても強いことを言っていて、実は、どんな木を作ろうが(ある頂点の子孫にどれだけどんな頂点を持ってこようが)、「全ての辺の重みが偶数かどうか」を変える事はできない事が分かる(なので適当に実験してもこの結果は予想できたかも？ゲームの時とかもそうだけど、手を動かすのもやっぱり大事かもね)。

以上から、この問題は与えられた入力に、各頂点が偶数回出てきているかどうかを見るだけであり、20行程度で解ける。