自动搬运

查看原文

来自洛谷，原作者为

	喵仔牛奶 黄昏再美终要黑夜。

搬运于2025-08-24 22:54:05，当前版本为作者最后更新于2023-12-12 21:24:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

复杂度较劣，需要卡常才能通过的 NTT 题解。

Solution

由于树的节点数没有什么用，下文将题面中的 $n,t$ 对调。

Part I

记前缀和 $s_i=\sum_{j=1}^{i}v_i$。

观察发现可以选定一些点，将所有热量供给给它们，不管其他点。

需要养活这些点，就要在第一个 $s_p<0$ 的时刻点 $p$ 给它们 $-\min_{j=1}^{n}\{s_j\}$ 的热量（每个时刻可以传递无限热量，最优情况就是一次传递所有需要的热量）。

那么定义根节点深度为 $0$，$siz_i$ 为深度 $\leq i$ 的点数，一种方案的答案即为 $\min\{-k/\min_{j=1}^{n}\{s_j\},siz_p\}$（其中 $p$ 为第一个 $s_p<0$ 的时刻）。

暴力枚举 $\{v_n\}$ 即可。时间复杂度 $\mathcal{O}((2m+1)^n)$，期望得分 $20$。

Part II

考虑把它变成式子的形式。

先做一些预处理：

• $f_{i,j}$ 表示长度为 $i$ 的，所有数 $\in[-m,m]$，任意前缀和非负，所有数和为 $j$ 的序列数。
• $g_{i,j}$ 表示长度为 $i$ 的，所有数 $\in[-m,m]$，任意前缀和为正，所有数和为 $j$ 的序列数。
• $pre_{i,j}=\sum_{k=0}^{j}f_{i,k}$。
• $s_{a,v}=\sum_{b=a+1}^{n}g_{b-a,v}\times pre_{n-b,nm}$。

记前缀和 $s_i=\sum_{j=1}^{i}v_i$。

枚举 $a$ 为前缀和中第一个负数的位置，$b$ 为前缀和中全局最小的位置，$c$ 为 $s_a$，$d$ 为 $s_b$。

• 为了避免算重，多个最小值在第一个最小值处算贡献。
• 对于 $a=b$ 和前缀和不存在负数的情况要特判算贡献。

则答案为：

$$\begin{aligned} &t\times\left(\sum_{i=0}^{nm}f_{n,i}\right)+\sum_{a=1}^{n}\sum_{c=-m}^{-1}\left(\sum_{i=0}^{c+m}f_{a-1,i}\right)\times\left(\min\{-k/c,siz_a\}\times \left(\sum_{i=0}^{nm}f_{n-a,i}\right)+\sum_{b=a+1}^{n}\sum_{d=-nm}^{c-1}\min\{-k/d,siz_a\}\times g_{b-a,c-d}\times\left(\sum_{i=0}^{nm}f_{n-b,i}\right)\right)\\ =&t\times pre_{n,nm}+\sum_{a=1}^{n}\sum_{c=-m}^{-1}pre_{a-1,c+m}\times\left(\min\{-k/c,siz_a\}\times pre_{n-a,nm}+\sum_{d=-nm}^{c-1}\min\{-k/d,siz_a\}\times s_{a,c-d}\right) \end{aligned} $$

直接暴力算就能做到 $\mathcal{O}(n^2m^2)$，获得 $50$ 分。

Part III

然后是优化这个式子。

• 考虑贡献中的 $\min\{-k/d,siz_a\}$，可以除法分块，预处理 $\{s_{a}\}$ 的前缀和即可做到 $\mathcal{O}(nm\sqrt{k})$。
• 然后是预处理 $s_{a,v}=\sum_{b=a+1}^{n}g_{b-a,v}\times pre_{n-b,nm}=\sum_{b=1}^{n-a}g_{b,v}\times pre_{n-a-b,nm}$，这是多项式乘法的形式，可以 NTT 做到 $\mathcal{O}(n^2m\log n)$。
• 预处理 $f,g$ 的话，可以前缀和优化做到 $\mathcal{O}(n^2m)$。

时间复杂度 $\mathcal{O}(nm(n\log n+\sqrt{k}))$，使用极限卡常手段之后开上 O2 可过。