联合省选 2023 填数游戏

这是 22 年的我：https://www.luogu.com.cn/record/81067862
这是 23 年的我：看我一个流过冲过 A 性质

首先考虑判定。一个经典模型是：如果在 \(T_{i,0}\) 与 \(T_{i,1}\) 之间连一条无向边（若 \(|T_i|=1\) 则认为 \(T_{i,1}=T_{i,0}\)），那么题目转化为给每条边定向，使得每个点的入度不超过 \(1\)。结论是有解当且仅当每个连通块是树或者基环树。这是很容易证明的：由于每条边都会产生 \(1\) 的贡献，从而有 \(|E|\le |V|\)；而一个连通块内有 \(|E|\ge |V|-1\)，从而我们只需给出树和基环树时的构造即可。当连通块形成一棵树时，取任意一点为根，将其定向为一颗外向树即可；当连通块形成一颗基环树时，则将环上的边定为同一方向，挂在环上的树均定为以环上的的点为根的外向树。

现在我们考虑加入了 Alice 操作后的问题。对树和基环树进行讨论：

基环树

不难发现我们上述给出的构造是唯一可行的构造方案，并且其只会给出两种构造，即只有环上的边的方向会发生改变，而挂在环上的树上的边的方向一定。于是，我们只需解决环上的问题即可。

不妨先给环定序为 \(\operatorname{cyc}_1\to \operatorname{cyc}_2\to \cdots \to \operatorname{cyc}_k\to \operatorname{cyc}_1\)（这里默认 \(k\le 2\)，否则下面做法会有问题），那么对于一条在 \(\operatorname{cyc}_i\) 和 \(\operatorname{cyc}_{i \bmod k + 1}\) 之间的边，对应的 Alice 的 \(S\) 集合有三种可能：

• \(S\cap \{\operatorname{cyc}_i,\operatorname{cyc}_{i \bmod k + 1}\} = \{\operatorname{cyc}_i\}\)
• \(S\cap \{\operatorname{cyc}_i,\operatorname{cyc}_{i \bmod k + 1}\} = \{\operatorname{cyc}_{i\bmod k + 1}\}\)
• \(S= \{\operatorname{cyc}_i,\operatorname{cyc}_{i \bmod k + 1}\}\)

记这三种情况的个数为 \(c_1,c_2,c\)，则分类讨论可知答案为 \(\min\left(\min(c_1,c_2)+c,\left\lfloor\frac{c_1+c_2+c}{2}\right\rfloor\right)\)。于是我们解决了基环树时的问题。

树

这一部分比较困难。

注意到上述构造中，Bob 会选一个点当根并将边定向为一颗外向树。于是，我们将 Bob 给边定向这件事看作是 Bob 选一个点。

现在来看看转化问题后 Alice 的选择会对 Bob 选点时的答案产生怎样的影响。记 \(f_i\) 为 Bob 选 \(i\) 作根时的答案，如果 Alice 在 \((u,v)\) 这条边对应的 \(S\) 集合中选择了 \(u\)，则不难发现 \(v\) 一侧的所有点（包括 \(v\)）的 \(f\) 值都会 \(+1\)，反之亦然。而又注意到 \(S_i\neq T_i\) 时 Alice 总是存在唯一的不劣选法，则问题进一步变为给定 \(f\)，需要 Alice 在一些边中选择给两侧点集中的某一个 \(f\) 值全部 \(+1\)，最大化 \(\min f\)。

一个关键性质是：记 \(V_i\) 为第 \(i\) 条边中 Alice 选的点，则有 \(\forall i,j,V_i\cap V_j\neq \varnothing\)。这并不难证明：考虑反证，若 \(V_i\cap V_j=\varnothing\)，则将这两条边中 Alice 选的点反过来使 \(V_i\gets \complement_V V_i\) 总是不劣的。由于这是在树上，那进一步则有 \(\cap_i V_i\neq \varnothing\)。

于是我们枚举 \(u\in \cap_i V_i\)，这样容易发现 Alice 需要选择的每一条边，都会选择以 \(u\) 为根时深度较大的点。注意到对每次对 \(f\) 的贡献在 dfs 序上形如一段区间或两端区间，因此在换根枚举 \(u\) 的同时维护一个线段树即可做到 \(O(n\log n)\)。