题意

给定一棵 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)$。

分类: 文章

永无岛

有问题欢迎在评论区提问或者联系neverland1e8plus7@163.com

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code