题解：AT_arc214_b [ARC214B] Missing Number in Graph

ran_qwq · 2026-02-10 16:23:47 · 题解

因为图联通且保证有解，所以自由元只有一个，即确定 a_1 可以确定整张图。先 dfs 一遍，求出 d_i=a_i\oplus a_1 的值。

题目给的限制相当于 \forall i,a_1\oplus d_i<n+1。枚举 a_1\oplus d_i 与 n+1 不同的位 j，比 j 高的位要相同，第 j 位前者是 0，后者是 1。这对 a_1 的限制形如“a_1 要在一个区间 [l,r] 内”。所以一个 i 的限制形如“a_1 要在 O(\log n) 个区间 [l_j,r_j] 中的任意一个内”。

求出 l_j,r_j 后，用差分前缀和找出所有满足所有条件的位置 \{a_1\}。知道了 a_1 后，可推出 \bigoplus\limits_{i=1}^na_i，再异或上 \bigoplus\limits_{i=0}^ni 可求出未出现的数。

这是代码。