树形DP总结

一、树形DP基础概念

1.1 什么是树形DP

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

1.2 基本框架

CPP

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）

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

状态设计：

dp[u][0]：以u为根的子树不选u时子树最大权值
dp[u][1]：以u为根的子树选u时子树最大权值

状态转移：

CPP

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求直径

CPP

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门课的最大价值

转移：

CPP

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条边的最大苹果数

CPP

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 注意事项

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

四、复杂树形DP

4.1 战略游戏（P2016）

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

状态：

dp[u][0]：以u为根的子树且u节点不放士兵
dp[u][1]：以u为根的子树且u节点放士兵

转移：

CPP

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 空间优化

滚动数组
DFS序优化

六、实战建议

6.1 解题步骤

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

6.2 常见错误

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

七、推荐练习题单

入门级

P1352 没有上司的舞会（最大独立集）
P2015 二叉苹果树（树上背包）
P2014 选课（树上分组背包）

进阶级

P2016 战略游戏（最小点覆盖）
P2458 保安站岗（树上状态机）
P1270 访问美术馆（二叉树DP）

挑战级

P2607 骑士（基环树DP）
P2685 电视网络
P3177 树上染色（复杂树上背包）

总结

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

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

关键思维：

把问题分解到每棵子树
通过DFS收集子树信息
在回溯时进行状态转移
合理处理父子节点关系

文章操作