题意
给定一棵 n 个节点的树，每个点有点权，让你找一个最大的联通块满足块内权值和不大于 m。
n,m, 点权不大于 1e5，点权互不相同。
解
点权互不相同，且点权和不大于 m，所以显然联通块的大小不会超过 $\sqrt{m}$。
令 $dp_{i,j}$表示以 i 节点为根的大小为 j 的联通块最小权值和 (这里还用到了交换下标的技巧)，那么第二维受两个条件制约：$\sqrt{m}$和子树大小。
这个 dp 的复杂度是多少的呢？$O(n^2)?O(n\sqrt{m})?$
对于一个点和 ta 的父亲，有三种情况：
1. 两个点的子树大小均不超过 $\sqrt{m}$。
可以把整颗树上满足” 自己的子树大小不大于 m 但是父亲的子树大小大于 m 的点” 提出来，这些点和它们的子树形成一个森林，森林中每棵树的大小不超过 $\sqrt{m}$，这部分 dp 的复杂度不会超过 $O((\sqrt{m})^2 \times \frac{n}{\sqrt{m}})$。(这里相当于是有不超过 n 个变量，每个变量的值不大于 $\sqrt{m}$, 求这 n 个变量的平方和的最大值)
2. 自己的子树大小不大于 $\sqrt{m}$但是父亲的子树大小大于 $\sqrt{m}$的点
这样的节点在树上是不会出现” 一个是另一个的祖先” 的情况的，那么这一块的复杂度等于
$$O(\sqrt{m}\times\Sigma_{i 是满足条件的节点}i 的子树的大小) \leq O(n\sqrt{m})$$
3. 自己的子树大小大于 $\sqrt{m}$
这时我们可以只看这些点形成的树 (显然这些点形成一个包含根的联通块)。考虑对于每一个节点合并它儿子的 dp 数组的时候，都在 x-1(x 为儿子的数量) 次合并后使整颗树的叶子数量减少 x-1，最开始叶子的数量不大于 $\frac{n}{\sqrt{m}}$, 故合并次数不超过 $\frac{n}{\sqrt{m}}$。一次合并复杂度 $O((\sqrt{m})^2)$, 故这部分复杂度是 $O(n\sqrt{m})$的。
每一个点继承的复杂度都是不超过 $O(\sqrt{m})$的，故继承部分总复杂度也不超过 $O(n\sqrt{m})$。
总复杂度 $O(n\sqrt{m})$。
更一般地，可以认为有如下结论:
一个一维树上背包，如果其第二维同时受子树大小和某个数 k(可以是常数或者变量) 约束，那么这个背包的复杂度有一个上界是 $O(nk)$。
0 条评论