主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
树上背包复杂度证明
最后更新于 2025-07-31 04:45:16
作者
qqqaaazzz_qwq
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
### 刷表法 用刷表法求书上背包复杂度是正确的，具体来说是这个式子： $$$ \sum_{i=1}^n \sum_{j=1}^{|son_i|} (\sum_{k=1}^{j-1} size_{son_{i,k}}) \times size_{son_{i,j}} $$$ 如何证明这个式子的答案是 $\Theta(n^2)$ 呢？ 可以这么想，令 $p_i = \sum_{j=1}^{|son_i|} (\sum_{k=1}^{j-1} size_{son_{i,k}}) \times size_{son_{i,j}}$，$q_i$ 表示有多少个点对的 $lca$ 是 $i$。则可以证明 $p_i \leq q_i,\sum p_i \leq \sum q_i \leq n^2$。 ⭐：关于 $p_i \leq q_i$，可以这么想：$j$ 枚举的是其中一个点在 $j$ 这个子树里，而另一个点在前面的子树里，乘法原理求积。所以说 $p_i \leq q_i$。 得证。 [here](https://www.luogu.com.cn/record/176809422) ### 填表法（错误的） 填表法是**错误的**，它的式子和上面的式子只有一点点不同： $$$ \sum_{i=1}^n \sum_{j=1}^{|son_i|} (\sum_{k=1}^{\color{red}j} size_{son_{i,k}}) \times size_{son_{i,j}} $$$ 这样可以被链卡成 $\Theta(n^3)$。 [here](https://www.luogu.com.cn/record/176811175) ### 谨以此文， ### 纪念我在模拟赛中挂掉的20分
正在渲染内容...
点赞
0
收藏
0
