[USACO20OPEN]Circus P

· · 题解

不妨假设这些点正好在 1\sim k 上，若 x,y 能够在不影响其他点位的情况下交换，则 x,y 之间连边，不难发现有传递性，则会连成若干个团，则答案为 \dfrac{k!}{\prod [\text{团大小}]!}。

考虑点 x,y 何时能够互通，它必然需要一个地方腾挪。而一个二度点显然是不能腾挪的。

考虑一条路径，两端不为二度点，中间全为二度点。设其左端点的子树大小为 A 右边为 B 链上有 C 个点，显然有 A-1+B-1+C=n。

当 k>A-1+B-1 时，恒有 k-(A-1)-(B-1) 个点在链上，则左边 A-1 个点和中间 k-(A-1)-(B-1) 和右边 B-1 个点互不相通。k=A-1+B-1 时亦然，只是中间不存在点而已。否则我们一定可以交换链两端的点。

若 x\to y 路径上所有的链都满足 k<A-1+B-1 则可以互通。

我们把树上的路径缩起来形成一棵新树，把所有 k\geqslant A-1+B-1=n-C 的边断掉，则剩下的每个连通块就代表一个团。我们计算这个团的大小。

这个团的大小是由与其相连的断边刻画的，每条断边会规定一些一定不能与其交换，即

k-\sum (k-(B-1))=k-\sum (k-n+(A-1)+C)

于是从大到小枚举 k，然后每次加路径维护每个连通块的大小和断边个数即可。

注意到每个时刻连通块个数为断边个数加一，长为 l 的断边恰好断 l 个 k，于是任意时刻连通块个数的和是 \mathcal O(n)，于是整体时间复杂度就是 \mathcal O(n\log n) 的。