0012: 对特殊性质下树上DP时间复杂度为O(n^2)的证明

· · 算法·理论

0012: 对特殊性质下树上DP时间复杂度为\varTheta(n^2)的证明

本篇为动态规划系列第 1 篇, 关于本系列详见0000: 博客目录.

引理12.1

在树上DP中, 设以点 i 为根的子树为 sub_i. 若点 u 有 k 个儿子, 分别为 v_1,v_2,..,v_k. 如果要将第 i 个儿子 v_i 转移到 u 需要的枚举次数为\displaystyle|sub_{v_i}|\cdot[(\sum_{j=1}^{i-1}|sub_{v_j}|)+1], 且单次转移复杂度为\varTheta(1), 则树上DP总时间复杂度为 \varTheta(\frac{n^2}2).

证明

$$\displaystyle \begin{aligned}&\sum_{i=1}^k |sub_{v_i}|\cdot[(\sum_{j=1}^{i-1}|sub_{v_j}|)+1]\\=&\sum_{i=1}^k\sum_{j=1}^{i-1}|sub_{v_i}||sub_{v_j}|+\sum_{i=1}^k|sub_{v_i}|\end{aligned}$$ 我们将 $\displaystyle\sum_{i=1}^k\sum_{j=1}^{i-1}|sub_{v_i}||sub_{v_j}|$ 项 $\times 2$, 使得任意 2 个儿子的子树的大小相乘 2 次, 从而将上式化为: $$\begin{aligned}\text{上式}&=\frac{\sum_{i=1}^k|sub_{v_i}|\cdot(\sum_{j=1,j\neq i}^k|sub_{v_j}|)+2\sum_{i=1}^k|sub_{v_i}|}{2}\\&=\frac{\sum_{i=1}^k|sub_{v_i}|\cdot(|sub_u|-|sub_{v_i}|+1)}{2}\\&=\frac{(|sub_u|-1)(|sub_u|)-\sum_{i=1}^k|sub_{v_i}|^2+\sum_{i=1}^k|sub_{v_i}|}{2}\\&=\frac{|sub_u|^2-|sub_u|-\sum_{i=1}^k|sub_{v_i}|^2+(|sub_u|-1)}{2}\\&=\frac{|sub_u|^2-\sum_{i=1}^k|sub_{v_i}|^2-1}{2}\end{aligned}$$ 所以对于所有点的总枚举次数为(无需向叶子节点转移): $$\begin{aligned}\sum_{u=1,|sub_u|\neq1}^n\frac{|sub_u|^2-\sum_{i=1}^k|sub_{v_i}|^2-1}{2}\end{aligned}$$ 对于非叶非根点, 它的子树大小的平方会被抵消, 所以若$n\neq1$, 则上式可变为: $$\begin{aligned}\text{上式}&=\sum_{|sub_u|=n}^n\frac{|sub_u|^2}{2}-\sum_{|sub_u|=1}^{n}|sub_u|^2-\sum_{|sub_u|\neq 1}^n\frac{1}{2}\\&=\frac{n^2}{2}-\sum_{|sub_u|=1}^{n}1-\sum_{|sub_u|\neq n}^n\frac{1}{2}\\&<\frac{n^2}{2}\end{aligned}$$ 从而证毕.