对于 $i = 1 \ldots n$，Alice 需要从 $S_i$ 中选择一个数作为 $a_i$；在这之后，Bob 需要从 $T_i$ 中选择 $b_i$。其中 $1 \le |S_i|, |T_i| \le 2$。
设 $X = \sum\limits_{i=1}^n [a_i = b_i]$。Alice 的目标是最大化 $X$，Bob 的目标是在保证 $b_i$ 互不相同的前提下最小化 $X$。判断 Bob 能否保证 $b_i$ 互不相同，并在他能时求最终 $X$ 的值。
将每个 $T_i = \{u_i, v_i\}$ 转化为一条边 $(u_i, v_i)$ (特别的，$|T_i| = 1$ 时转化为一条自环)，则显然 Bob 能保证 $b_i$ 互不相同的充要条件是图为一个由基环树或树构成的森林 (即每个连通块 $C$ 含有的边数小于等于 $|C|$)。
接下来考虑 $X$。对于基环树，树边只有一种选法，所有环边作为一个整体共有两种选法。对于 Alice 的每个 $S_i$，记录 $S_i$ 中选项对 Bob 选法的贡献，最大化其对 Bob 两种选法产生的总贡献的最小值，贪心即可。
对于树，显然其中恰好有一个节点未被任何边占用，每个节点未被占用都对应 Bob 的一种选法，故 Bob 共有 $|C|$ 种选法，记其中不占用节点 $x$ 的选法为 $D_x$。对于 Alice 的一条边 $(u_i, v_i)$，若其选择了 $u_i$，则对于所有 $u_i$ 子树外的节点 $x$，当 Bob 使用 $D_x$ 时，Alice 的这种选法都会对 $X$ 产生 $1$ 的贡献。形式化地，记 Bob 选用 $D_x$ 时 $X$ 的值为 $F_x$，则 Alice 选用 $u_i$ 的效果为：$\forall x \notin \mathrm{subtree}(u_i): F_x \gets F_x + 1$。Alice 的目标是最大化 $\min\limits_{x} F_x$。
显然这个问题可以利用树形 DP 在 $O(n^3)$ 的时间复杂度内解决。然而我们需要更快的解法。
通过观察不难发现存在一个 Alice 的最优选法，其中存在一个点 $x$，将树以 $x$ 为根，Alice 所有边都选用深度较大的节点。因为对于两个 Alice 的边 $(p, q)$ 和 $(q, r)$，不应两条边都选取 $q$，这样劣于两条边分别选取 $p$、$r$；根据这样的决策原则，可以确定存在一个最优选法为所有边都选深度较大的节点。于是我们可以在 $O(n\log n)$ 的时间内通过 DFS 和线段树得到以所有点为根时 $\min\limits_{x} F_x$ 的值。
代码：https://github.com/fei0319/competitive-programming/blob/main/code/luogu/P10547.cpp