我想出来的最后一道题

· · 题解

以下是考场思路。

首先，这是一道图论题。把 T 集合抽象成边，大小为 1 的集合就是自环。然后要是有个连通块边比点多那肯定就完蛋了。

然后每个连通块要么是树要么是基环树，基环树应该简单所以先想树。再来看 S 集合，我们只考虑 S_i 和 T_i 的交集，稍微转化一下可以将题意转化为：

有一个树，有的边上有方向规定，B 要给每条边定向使其成为一棵内向树使得违反的规则尽可能少，在这之前 A 可以决定部分边上的规定使得 B 违反尽可能多的规则。

先随便抽出一个点为根，那么 B 要是选择其他根，实质上就是反转了这两个点之间的链。那我们就可以 dp A 的选择了，设 dp_{i,j,k} 表示确定了以 i 为根的子树、B 选择把根放到这棵子树里最多可能少违反 j 个规则、你摆放的外向边数数量为 k 的状态是否存在。最终的答案就是所有存在的 dp_{1,j,k} 中 j-k 的最大值。实现的时候可以只记录 i,j 相同的状态里 k 最大的，这是一个 O(n^2) 的 dp。

这个 dp 据说形态良好，可以维护凸包直接得出答案，不过这有些复杂，我们还可以进一步发掘性质。考虑这个 dp 所有状态的三种转移：

合并两个子树：dp_{i_1,j_1,k_1},dp_{i_2,j_2,k_2} \to dp_{i,\max(j1,j2),k1+k2}

接上一个内向边：dp_{s,j,k}\to dp_{i,\max(j-1,0),k}

接上一个外向边：dp_{s,j,k}\to dp_{i,j+1,k+1}

我们发现，假如说我们同时选择在两个不同的子树里接上内向边，那么由于 j 的合并是 \max ，还是只会省下一份 j （令 j 比原先减少了 2），但是 k 也确确实实减少了 2，那么 k-j 就不变了，这样也就得不偿失，所以我们可以猜测最后每个节点都只会有一个子树里面有特意安放的内向边。

这样的话，特意安放的内向边只会在一个从根开始的链上，我们接着感性分析，猜测这样的边会尽可能靠近根，以防好不容易减下来的 j 被 \max 掉。

此时我们就有一个很强的结论了：A 的决策一定是选择一个点，然后以这个点为根为根将所有可以调的边全部设定成外向的！那这个点是什么呢？不重要。我们可以通过换根的方式统计出所有点的答案，然后取最优即可。

那这个题就做完了……吗？？还有基环树呢。

这也能难倒人吗？B 在基环树里只有环上有选择，要么顺时针要么逆时针直接看哪个违反的规则少就行，那 A 就让两种情况尽可能平均，你找到环不就做完了？

然后我确实在考场上没能写出来找环。这个玩意实在是太难写了，参见讨论区（

就这样，我遗憾离场了。

这道题其实不算很难，推法也有很多种。如果我能写完它，进队也就稳了，可惜没有如果。我写过的比这题还长的代码不超过 10 个，没法指望啊……

最后这个题的输出没有出锅，我还是拿到了 A 性质的分数。这是我学 OI 以来的线下考试里第一个得了分的 T2，纪念一下吧（