【记录】树形 DP 优化

xuyunao · 2025-02-13 15:30:21 · 算法·理论

树形DP常用优化

主要是通过利用 DFN 序的一些巧妙性质及利用，从而实现优化常数甚至是优化复杂度。

1.树形背包

例如 P2014 [CTSC1997] 选课

我们在正常进行树形背包时，需要进行 3 层循环，时间复杂度为 O(n^3) 。

code

for(int i = 0;i < G[u].size();i++)
    {
        int v = G[u][i];
        for(int j = m;j >= 1;j--)
        {
            for(int k = 0;k < j;k++)
            {
                dp[u][j] = max(dp[u][j],dp[u][j-k] + dp[v][k]);
            }
        }
    }

但我们可以考虑将以 u 为根的子树拍扁,这样我们就相当于是在子树内进行了一次 0/1 背包，由于最终答案都是由子树合并来，而子树之间的数量关系也不会相互影响，所以我们直接将其拍扁，这样进行树形背包的复杂度是 O(n^2) 的。

code

for(int i = 1;i <= n + 1;i++)
    {
        int u = d[i];
        for(int j = 0;j <= m;j++)
        {
            f[i][j] = f[i - size[u]][j];
            if(j) f[i][j] = max(f[i][j],f[i-1][j-1] + s[u]);
        }
    }

2.DFN 优化递归常数

同样的，我们这种利用 DFN 而避免使用递归合并 dp 数组的方法可以极大的优化递归常数。

例如P3523 [POI 2011] DYN-Dynamite

我们在由子树向根合并 dp 值的时候，通过 DFN 避免了使用 dfs 递归带来的大常数，在一些极端数据下可以使我们的代码跑的飞快。

详见分析

3.通过减少合并次数降低复杂度

常见的，我们可以通过树的链剖分以及树上 lca ，使得子树或一条链内的所有节点都合并到链头的位置，从而可以优化合并的复杂度。

4.上下界优化

通过子树大小限制枚举的上下界，可以证明时间复杂度为 O(n^2)。

未完待续。