树形DP总结

· · 算法·理论

一、树形DP基础概念

1.1 什么是树形DP

树形动态规划是在树结构上进行的动态规划，利用树的递归特性，通过后序遍历自底向上地传递信息。

1.2 基本框架

void dfs(int x,int fa)
{
    //初始化工作
    for(int i=0;i<l[x].size();i++)
    {
        int y=l[x][i];
        if(y==fa)
            continue;
        dfs(y,x); //递归处理子树
        //状态转移
    }
    //更新最终结果
}

二、经典模型与例题

2.1 没有上司的舞会（P1352）

问题：树中选取不相邻节点，使权值和最大。

状态设计：

状态转移：

void dfs(int x,int fa)
{
    dp[x][0]=0;
    dp[x][1]=a[x];
    for(int i=0;i<l[x].size();i++)
    {
        int y=l[x][i];
        if(y==fa)
            continue;
        dfs(y,x);
        dp[x][0]+=max(dp[y][0],dp[y][1]);
        dp[x][1]+=dp[y][0];
    }
}

2.2 树的最长路径（直径问题）

解法：树形DP求直径

void dfs(int x,int fa,int ans)
{
    for(int i=0;i<l[x].size();i++)
    {
        int y=l[x][i];
        if(y==fa)
            continue;
        dfs(y,x,ans);
        ans=max(ans,dp[x]+dp[y]+1);
        dp[x]=max(dp[x],dp[y]+1);
    }
}

三、树上背包问题

3.1 树上分组背包

典型例题：选课问题（P2014）

状态：dp[u][j]表示以u为根的子树选择j门课的最大价值

转移：

void dfs(int x,int fa)
{
    for(int i=0;i<l[x].size();i++)
    {
        int y=l[x][i];
        if(y==fa)
            continue;
        dfs(v,u);
        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]);
            }
        }
    }
}

3.2 二叉苹果树（P2015）

状态：dp[u][j]表示以u为根的子树保留j条边的最大苹果数

int dfs(int x,int fa)
{
    int sum=1;
    for(int i=0;i<l[x].size();i++)
    {
        int y=l[x][i].y,w=l[x][i].w;
        if(y==fa)
            continue;
        int tmp=dfs(y,x);
        sum+=tmp;
        for(int j=min(sum,q);j>=0;j--)
        {
            for(int k=0;k<=min(sum,j-1);k++)
            {
                dp[x][j]=max(dp[x][j],dp[y][k]+dp[x][j-k-1]+w);
            }
        }
    }
    return sum;
}

3.3 注意事项

  1. 枚举顺序：倒序枚举避免重复选择
  2. 体积范围：注意体积的合理范围
  3. 初始化：根节点需要特殊初始化

四、复杂树形DP

4.1 战略游戏（P2016）

问题：在树上放置士兵，监视所有边。

状态：

转移：

void dfs(int x,int fa)
{
    dp[x][0]=0;
    dp[x][1]=1;
    for(int i=0;i<l[x].size();i++)
    {
        int y=l[x][i];
        if(y==fa)
            continue;
        dfs(y,x);
        dp[x][0]+=dp[y][1];
        dp[x][1]+=min(dp[y][1],dp[y][0]);
    }
}

五、优化技巧

5.1 时间复杂度优化

5.2 空间优化

六、实战建议

6.1 解题步骤

  1. 确定树结构，建立邻接表
  2. 分析问题，设计状态
  3. 写出状态转移方程
  4. 确定遍历顺序和初始化
  5. 考虑边界情况

6.2 常见错误

  1. 忘记跳过父节点导致死循环
  2. 状态转移顺序错误
  3. 数组开小或越界
  4. 初始化不正确
  5. 背包枚举顺序错误

七、推荐练习题单

入门级

进阶级

挑战级

总结

树形DP的核心在于利用树的递归结构，通过子问题的解来构建原问题的解。掌握树形DP需要：

  1. 理解树的基本遍历（DFS）
  2. 熟练设计状态表示
  3. 正确写出转移方程
  4. 注意实现细节和优化

关键思维：