填数游戏（game）

当 $|T_i|=1$ 时 Alice 的最优决策一定是唯一的，可以预先处理。如果 $S_i\cap T_i=\varnothing$，则 Alice 的选择对 Bob 无影响；如果 $|S_i\cap T_i|=1$，则 Alice 一定选与 Bob 相同的最优；其余情况一定是 $S_i=T_i$，Alice 要从中二选一，使得 Bob 最小化的 $X$ 最大。

由二元关系联想到建图，$S_i=T_i=(u_i,v_i)$ 就在 $u_i,v_i$ 间连编号为 $i$ 的无向边。考虑每个联通块 $(V’,E’)$ 分别处理，如果 $|E’|>|V’|$ 则 Bob 不存在合法的选择方案，所以只可能是 $|E’|=$ $|V’|$ 或 $|V’|-1$。对于$|E’|=|V’|$ (也即基环树) 的情况，Bob 只有两种策略，对于 Alice 树的部分一定能完整取到，环上可以取到至少一半。

考虑 $|E’|=|V’|-1$ 的情况(也就是一棵树)，对于 Bob 来说一定会存在一个点 $r$ (是不选择的)，其余唯一确定。对于每条边 $(u_i,v_i)$，Alice 可以选择 $u_i$ 或者 $v_i$ 表示 $r$ 在 $u_i$ 或者 $v_i$ 的某一侧子树时，会产生一的贡献（如果令 $r$ 在 $u_i$ 这侧有贡献，我们就定向 $v_i\to u_i$ 否则 $v_i\to u_i$）。对于边 $(a,b)$ 和 $(c,d)$ 满足 $b$ 到 $c$ 不经过 $a,d$，定向方案一定不能是 $b\to a$ 且 $c\to d$ (否则两者均调换方向后更优)。可以推得，Alice 最优方案对应的定向后的树，至多只存在一个出度为零的节点 $o$。点 $o$ 对应的方案 $X$ 为 $n$ 减去 $o$ 到树上最远点的距离。Alice 需要最大化 $X$，取 $o$ 为树直径的中点一定是最优的。答案就是 $n$ 减去直径除以二。

时间复杂度 $O(n)$。