ABC126 DEF メモ - tinumu's reminder

D - Even Relation

頂点 $r$ を根としてみた根付き木と考える。
このとき、頂点 $u$ と頂点 $v$ の距離 $\mathrm{dist}_{u, v}$ は、
$\mathrm{dist}_{u, v} = \mathrm{dist}_{r, u} + \mathrm{dist}_{r, v} - 2 \times \mathrm{dist}_{r, \mathrm{lca}(u, v)}$ である。
最後の項は必ず偶数であるため、偶奇に関係しない。
そうすると、

$\mathrm{dist}_{u, v}$ が偶数 $\Leftrightarrow$ $\mathrm{dist}_{r, u}$ と $\mathrm{dist}_{r, v}$ の偶奇が一致する
となるので、これは、頂点 $r$ からの距離の偶奇で色分けすれば条件を満たすことがわかるので、dfs などを書いてやると、OK

E - 1 or 2

$Z_i$ の条件でつなげた頂点の偶奇が反転するか同じになるかがきまる。
つなげた時点で、片方に依存して一意に定まることがわかっているので、
実はこれは連結成分ごとに一つ数字を決めれば全ての数字がきまる。

よって、連結成分の個数を数えておわり
実は $Z_i$ 使わない

気づけば、Dよりも考察簡単では

F - XOR Matching

気づくのが難しいが、 $0, 1, 2, \cdots , K-1, K+1, \cdots 2^M -1 , K, 2^M - 1, \cdots , K+1, K-1, \cdots, 2, 1, 0, K$ とすればいい。
まず、考察として、 $A_1, A_2, \cdots, A_N, K, A_N, \cdots, A_2, A_1$ みたいなのは、全ての $A$ の要素について、内部のXORが $K$ になる。なぜなら $K$ 以外は同じものを $2$ つ含んでいるため、打ち消し合って $0$ になるからである。

これをすると、 $K$ 以外はすべて構築できたことになる。

また、 $0 \oplus 1 \oplus \cdots \oplus 2^M-1$ は $0$ になる。
これにおいて $K$ を抜くと当然総XOR は $K$ になる。
つまり、一番右もしくは一番左に $K$ を置けば、これもまた内部の XOR は $K$ になっている。よって、一番右に $K$ を置けば完成になる。

構築、一気に発想を飛ばさないといけないから難しいな

次に続きます
tinumukiti631.hatenablog.com
これです