题解：P6277 [USACO20OPEN] Circus P

· · 题解

显然不论这些牛的初始位置在哪里，我们都可以将它们移动到某特定的 k个位置上，然后计数分配标号的方案数。不妨认为将这些牛移动到编号为 1,2,\cdots,k 的点上。

牛在树上的移动会受到其他牛的限制，有时会被堵死，有时可以互换位置。所以我们只关心某两个位置上的两头牛是否能交换位置。

如果位置 (x,y) 上的牛可以交换位置且不改变其它牛的位置或者可以将其它牛恢复到原位，则称这两个位置有交换关系。显然这种关系具有传递性。

我们将这种关系视作一张图上连接 (x,y) 的一条边，那么由于传递性，最终会形成若干个团。不妨对将牛排列在 1,2,\cdots,k 位置的标号排列计数。设第 i 个团的大小为 s_i，那么答案就是 \dfrac{k!}{\prod\limits_i (s_i!)}。这些 s_i 都是在 k 头牛限制下得到的，可以说明 i\le k。

现在来刻画这种交换关系在树上表现出的形态。感性上，两个位置想要交换，必然需要一个空位置，来让其中一头牛在上面等待另一头牛移动。

这告诉我们，一条不分叉的路径上，两个位置不能交换。以下定义链为两端的点度数不为 2，中间的每个点度数都为 2 的一条路径。

不妨将一条链拎起来，称左端点及其下方部分为左子树，设其大小为 A，右端点同理，设其大小为 B，设链长（含两个端点的点数）为 C。显然有等式 (A-1)+(B-1)+C=n。

考虑在 k 的限制下，何时可以交换左右子树中的一个点。

可以断言：当且仅当 k<(A-1)+(B-1)=n-C 时，左右子树中的点可以任意交换。

必要性是显然的，若 k>n-C，那么链上至少会有 k-n+C 头牛无法交换位置，故左右子树中的点无法交换。若 k=n-C，容易验证与前一种情况类似。

充分性可以构造得证。感性理解就是 k<n-C 时，将 k 头牛扔进左右子树后仍有空位，可以利用这些空位完成交换。

以下称一条链是非法的，如果 C\ge n-k。

考虑对于固定的 k 算一次答案。我们将 C\ge n-k 的非法链从原图中删去，那么剩下的若干个连通块一一对应着若干个团。

此处应注意区分：连通块的大小指树上的点的数量，而团的大小指奶牛的数量。

考虑计算一个连通块对应的团的大小。直接算是不好算的，这个团是由与这个连通块相连的非法链刻画的，每条非法链会从这个团中扣掉一部分。不妨用牛的总数 k 减去每条非法链从这个团中划分出去的数量。设一条非法链已知其 A,B,C，那么它可以从这个团中划分出 k-(A-1)=k-(n-(B-1)-C) 个点。

那么对于一个连通块，枚举其每一条非法链出边，计算其团的大小。设连通块大小为 siz，非法链出边数量为 cnt。

\begin{aligned} k-\sum(k-(n-(B-1)-C))&=k-k\cdot cnt+n\cdot cnt+cnt-(\sum B-1+C-1)-2\cdot cnt\\ &=k-(k-n+1)\cdot cnt-(n-siz)\\ &=(n-k-1)\cdot (cnt-1)+siz-1 \end{aligned}

对每个连通块维护 cnt 和 siz，就可以算出对应的团的大小。

从大到小枚举 k，就可以改删边为加边，使用并查集维护。上述过程在 k=n 时会越界，要特殊处理 k=n 时的答案，显然这是 n!。

注意到这里枚举的复杂度是 O(\sum\limits_k \text{连通块个数})=O(\sum\limits_k\text{非法链个数})。考虑每条非法链的贡献，可以得到 O(\sum\limits_k\text{非法链个数})=O(\sum\limits_k\text{链长})=O(n)。过程中如果用 set 维护，时间复杂度 O(n\log n)。