2024/04/03(#27)：弹指间湮灭我 但命运打不败活着

摘要：无。

让生命如剧烈的烟火 / 璀璨熄灭前也将点亮 / 孩童的双眸

感觉还是被负能量主导了啊。

我未曾想过自己会有这个问题，曾夸下海口说自己“比一般人的抗挫能力更强”，但现在看来，我也只是臭鱼烂虾罢了。

为什么会这样？我能想到的是自己的能力与现实的巨大差距，但这时候理应爆发出更加强大的执行力，而不是在原地等待。

不吃饭？还有对入眠的恐惧感？

没有选择“在当前局面下更优的解决办法”，用一个我非常不想用在我自己身上的形容词，自暴自弃。

将它们修复、抹除掉。没有什么是我做不到的。

神罚并没有停止，空前的绝望如期而至。但是很可惜，我的名字叫不死之人。

[USACO20OPEN] Circus P | AGC066E

Portal.

首先，奶牛之间没有区别，我们总可以移动这些奶牛使得它们到达前 $K$ 个点。

$K=i$ 时，答案的上界是 $i!$，但是无法达到，原因是存在一些位置对 $(x,y)$ 它们可以在不改变其它奶牛的位置的前提下进行交换，那么对它们连边，它们会构成一些团，设团的大小为 $s_i$，那么答案是 $k!/\prod s_i!$。

考虑一条路径，两端不为二度点，中间全为二度点。设其左端点的子树大小为 $A$ 右边为
$B$ 链上有 $C$ 个点，当 $x\rightarrow y$ 上的所有链都满足 $k<A-1+B-1=n-C$ 则可以连通。

将树上的二度点路径缩起来成为一棵新树。将所有 $k\ge n-C$ 的边断掉，剩下的每个连通块就都是团，我们需要计算每个连通块对应的团的大小（有多少个奶牛在这里面可以互换）。

设连通块内的子树为 $B$，那么我们让其填满，无法连接到连通块的点的数量为：

$$\begin{aligned} & k - \sum (k-(B-1))\\ =\ & k-\sum(k-(n-C-A+1))\\ =\ & k-\sum(k-(n-1-p))\\ \end{aligned}$$

其中 $p$ 连接到当前连通块外的那个的子树大小，$1$ 是连接点（在连通块内），不难发现 $\sum p=\sum n - x$。

最后用 $k$ 减去就是团的大小。由于链长总和是 $O(n)$ 的，因此时间复杂度 $O(n\log n)$。代码。

对于 AGC066E，没有本质区别。答案的下界是 $\binom n k$（哪些位置放石头），到最终局面下每个团内部可以任意排列的。