2026-11-12(#19)：绝不涉足的肮脏之所

Imy feat. 棗いつき —— Not Falling

懒得找歌了，用一首比较喜欢的。

51 [qoj9774] Same Sum

相对最小最大值去做集合哈希，两边的集合要一样。代码。

下午出去玩。

晚上打 CF1134(Div. 4)，发现自己秒不掉后面的题，而且打着打着就困了，上了大学之后作息还是太健康了熬不动夜了。

一开始想去外面住酒店打，但这样一天就要 -300，我很久没讲过课了所以不太赚的到钱，再说吧。

确实能说明水平不足。记录后面两个做得奇异搞笑的题。

一开始得出了错误的观察：一定是根节点连向某个节点，这个观察基于根节点只有一个儿子。

那么发现它一定会连向树的叶子节点。

然后顺着这个做下去了！设 $f_i$ 考虑子树内要丢失的最小是多少（即断掉子树一条边），只有一个儿子是 $f$ ，剩下的是 $siz$ ，然后取最大值。

也就是说，将边连进去则可以“保住”，此时断这里的边的损失最大是 $f$ ，否则是 $siz$ 。

如果根节点真的只有一个儿子那么答案就是 $n-f_1$ 。然后样例 4 就错了。

否则我们对于两个儿子则可以通过连接这两个子树的某两个叶子来保住这两个儿子，那么挑 $siz$ 最大的两个保住就可以了。代码。

肯定是二分，当然，不要像我第一眼把 $\max$ 看成求和。

梦碎 ICPC 2026 武汉，三个人没人会二分的，唉。

由于只能变高，因此高度至少需要是 $y_i=\max_j\left(h_j-D\cdot \operatorname{dist}(i,j)\right)$ 。直接枚举 G1 就做完了。

把距离的绝对值拆了，分成左边右边去维护。让左右都直接取 $n$ 个，这样比较方便，而且多取的一定不会使得答案变劣。两边都直接用滑动窗口做掉即可。

然后好久之后的第一次打 CF，在此期间代码习惯把 long long 都写成了 long，Linux 下 long 确实是 64 位，但是 CF 是 Windows，然后吃了一发。代码。