树形DP入门：实战技巧与经典例题 ^_^

本文介绍了树形动态规划的基本概念和应用。树形DP利用树的递归特性，通过分解子树问题来求解父节点最优解。文章通过多个例题详细讲解，包括《没有上司的舞会》、《战略游戏》等经典问题，展示了如何通过状态转移方程解决树上的最大独立集、最小覆盖等问题。还介绍了树上背包问题的解法，如《选课》和《二叉苹果树》等题目。最后指出，虽然题目看似复杂，但只要掌握技巧并多加练习，50行左右的代码就能解决这类问题。树形DP的

kzh1026

1058人浏览 · 2025-08-02 19:17:36

kzh1026 · 2025-08-02 19:17:36 发布

树形DP是什么？

顾名思义，便是树形的DP （废话少说）

树形动态规划是动态规划在树结构上的扩展，利用树的递归特性实现自底向上或自顶向下的状态转移。其核心思想是将问题分解为子树上的子问题，通过合并子树的最优解得到父节点的解。

首先，我们要了解：

有根树：题目给定根
无根树：题目没给定根

树：无环连通
n个点，n-1条边

树形DP：最大独立集
选择不相邻结点，使得点权和最大

实践出真知，不练怎么行

所以我将结合具体题目进行讲解，希望大家可以在题目中领悟这种新DP思想

那么，我们进入第一道题【P1352 没有上司的舞会】

题目描述

某大学有 n 个职员，编号为 1…n。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 ri，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

不难发现，这是关于点与点之间的，那么可推出：

dp[u][0] += max(dp[v][0],dp[v][1]);
dp[u][1] += dp[v][0];

代码：

#include <bits/stdc++.h>
#define maxn 6050
using namespace std;
vector<int> to[maxn];
int fa[maxn],dp[maxn][2],w[maxn];
void dfs(int u)
{
	dp[u][0]=0,dp[u][1]=w[u];
	for(int v : to[u]) //基于范围的for循环   迭代器
	{ //只建了父亲到儿子的有向边
		//if(v==fa[u]) continue;
		//fa[v]=u;
		 dfs(v);
		 dp[u][0] += max(dp[v][0],dp[v][1]);
		 dp[u][1] += dp[v][0];
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<=n-1;i++)
	{
		int u,v;
		cin>>u>>v; //v父亲 u儿子
		fa[u]=v;
		to[v].push_back(u); 
	}
	int s;
	for(int i=1;i<=n;i++) if(!fa[i]) {s=i; break;}
	dfs(s);
	cout<<max(dp[s][0],dp[s][1]);
	return 0;
}

第二题，【P2016 战略游戏】

题目背景

Bob 喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。

题目描述

他要建立一个古城堡，城堡中的路形成一棵无根树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能瞭望到所有的路。

注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被瞭望到。

请你编一程序，给定一树，帮 Bob 计算出他需要放置最少的士兵。

这道题就是变为了无向边，需要这一步

f(v==fa[u]) continue; fa[v]=u;

那么这道题变为了：

选最少点，使得所有边被覆盖问题
对于u-->v
选u，那么v选不选都行
不选u，那么v必选

所以，状态转移方程：

dp[u][0]+=dp[v][1];
dp[u][1]+=min(dp[v][0],dp[v][1]);

#include <bits/stdc++.h>
using namespace std;
const int maxn=1505;
vector<int> to[maxn];
int dp[maxn][2],fa[maxn];
void dfs(int u)
{
	dp[u][0]=0x,dp[u][1];
	for(int v : to[u])
	{
		if(v==fa[u]) continue;
		fa[v]=u; dfs(v);
		dp[u][0]+=dp[v][1];
		dp[u][1]+=min(dp[v][0],dp[v][1]);
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int u,k;
		cin>>u>>k;
		while(k--)
		{
			int v; cin>>v;
			to[u].push_back(v);
			to[v].push_back(u);
		}
	}
	dfs(0);
	cout<<min(dp[0][0],dp[0][1]);
	return 0;
}

第三题那么，下面，不上模板题了，【B4311 [蓝桥杯青少年组国赛 2024] 第六题】

题目描述

某城市的道路构成了一个巨大的树形结构，每一条道路可视为该结构的一条边，而道路的交叉点或端点视为其中的一个节点。该城市共有 n 个节点，编号分别为 1,2,3,…,n。

为了实时记录道路情况，需要在某些节点部署监控设备。当部署好后，与该节点直接相连的所有道路均能被监控到。为了优化资源分配，在保证整座城市的所有道路都被监控到的前提下，部署监控设备的费用要尽可能少。给定每个节点部署监控设备的费用，请计算要使所有道路都能被监控到的最少花费是多少？

看到树形二字，我们会想到树形 dp。

看到这道题，我们会发现与前面的模板题有些不同，一个点有三种被监控的可能，那么~~我突发奇想~~便可以设置三种状态：

dp[u][0]代表u被自己覆盖（u处建塔）

dp[u][1]代表u被父亲覆盖，此时v未被父亲u覆盖

dp[u][2]代表u被儿子覆盖

上代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
vector<int> to[maxn];
int dp[maxn][3],fa[maxn];
void dfs(int u)
{
	dp[u][0]=1,dp[u][1]=dp[u][2]=0;
	bool flag=false; 
	int minn=1e9;
	for(int v : to[u])
	{
		if(v==fa[u]) continue;
		fa[v]=u; dfs(v);
		dp[u][0] += min(dp[v][0],min(dp[v][1],dp[v][2]));
		dp[u][1] += min(dp[v][0],dp[v][2]); // v的父亲“靠不住”，两种选择 
		if(dp[v][0]<dp[v][2]) //v如果靠自己更好 
		{
			dp[u][2]+=dp[v][0]; //让v自己建信号塔,并给u“养老” 
			flag=true;
		}
		else
		{
			dp[u][2]+=dp[v][2];
			minn=min(minn,dp[v][0]-dp[v][2]); // 求出最小的dp[v][0]-dp[v][2] 
		}
	}
	if(!flag) dp[u][2]+=minn; //多花费minn的代价，确保u能被覆盖 
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n-1;i++)
	{
		int u,v;
		cin>>u>>v;
		to[u].push_back(v);
		to[v].push_back(u);
	}
	dfs(1);
	cout<<min(dp[1][0],dp[1][2]);
}

第四题，【P1351 联合权值】

题目背景

NOIP2014 提高组 D1T2

题目描述

无向连通图 G 有 n 个点，n−1 条边。点从 1 到 n 依次编号,编号为 i 的点的权值为 Wi，每条边的长度均为 1。图上两点 (u,v) 的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对 (u,v)，若它们的距离为 2，则它们之间会产生 Wv×Wu 的联合权值。

请问图 G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

~~不难看出，~~ 想了半小时想出：

dp[u]是u为根子树的答案，son[u]是u的儿子权值和，son_max[u]是儿子最大权值
那么，本题就是求【距离为2】的点的最大权值乘积、权值乘积的和

分两种情况：u和u孙子（u和v儿子）；兄弟（v）之间

遍历所有边 u-->v：dfs(v); dp[u] += dp[v] + w[v]*son[u] + w[u]*son[v];
用 w[v]*son_max[u], w[u]*son_max[v] 更新最大值
son[u]+=w[v]; son_max[u]=max(son_max[u], w[v]);

dp[u]是【u子树】所有联合权值的和

初值：dp[u]=0;
设边u-->v
（1）情况1：u 和它的孙子
w[u]*w[vv1]+w[u]*w[vv2]+...
=w[u]*(w[vv1]+w[vv2]+...)
=w[u]*v的儿子权值和
=w[u]*son[v]
（2）情况2：u儿子和 u另一个儿子
w[v]*(w[v1]+w[v2])
=w[v]*son[u]
（3）情况3：v子树本身也有联合权值
dp[v]
（注：目前的son[u]是v之前兄弟的点权和）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5 , mod = 10007;
vector<int> to[maxn];
int w[maxn],dp[maxn],son[maxn],son_max[maxn],fa[maxn];
int maxx=-1e9,ans=0;
void dfs(int u)
{ // dp[u]代表【以u为根的子树】联合权值之和，son[u]是u的儿子的点权和
	dp[u]=son[u]=0;
	for(int v:to[u])
	{ // 边u-->v
		if(v==fa[u]) continue;
		fa[v]=u; dfs(v); // 自上而下搜索，回溯时状态转移
		dp[u] += w[u]*son[v]+w[v]*son[u]+dp[v];
		son[u]+=w[v];
		dp[u]%=mod; son[u]%=mod;
		
		maxx=max(maxx,max(w[u]*son_max[v],w[v]*son_max[u]));
		son_max[u]=max(son_max[u],w[v]); // 儿子权值中的
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n-1;i++)
	{
		int u,v;
		cin>>u>>v;
		to[u].push_back(v); to[v].push_back(u);
	}
	for(int i=1;i<=n;i++) cin>>w[i];
	dfs(1);
	cout<<maxx<<" "<dp[1]*2%mod; //点对(a,c)和点对(c,a)不能看做相同点对
	return 0;
}

第五题，【P10723 黑白翻转】（GESP七级真题）

题目描述

小杨有一棵包含 n 个节点的树，这棵树上的任意一个节点要么是白色，要么是黑色。小杨认为一棵树是美丽树当且仅当在删除所有白色节点之后，剩余节点仍然组成一棵树。

小杨每次操作可以选择一个白色节点将它的颜色变为黑色，他想知道自己最少要执行多少次操作可以使得这棵树变为美丽树。

学到这里相信大家已经逐渐熟练，

dp[u] 是【以u为根的子树】是否有黑色
0无黑色；1有黑色
初值：dp[u]=w[u]
状态转移：设u-->v，先dfs(v);
dp[u] |= dp[v];
// dp[v]是1，那么dp[u]也变成1
答案：if(u是白色并且 dp[u]==1) ans++;

直接上代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100050;
vector<int> to[maxn];
bool dp[maxn];
int w[maxn],fa[maxn],ans;
void dfs(int u)
{
	dp[u]=w[u];
	for(int v:to[u])
	{
		if(v==fa[u]) continue;
		fa[v]=u; dfs(v);
		if(dp[v]) dp[u]=1;
	}
	if(!w[u] && dp[u]) ans++;
}
int main()
{
	int n; cin>>n;
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<=n-1;i++)
	{
		int u,v;
		cin>>u>>v;
		to[u].push_back(v);
		to[v].push_back(u);
	}
	int s=-1;
	for(int i=1;i<=n;i++)
	{
		if(w[i]==1)
		{
			s=i; break;
		}
	}
	dfs(s);
	cout<<ans;
	return 0;
}

接下来，我们看看树上背包（树形DP+背包DP）

第一题，【P2014 [CTSC1997] 选课】

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 N 门功课，每门课有若干学分，分别记作 s1,s2,⋯,sN，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 M 门课程学习，问他能获得的最大学分是多少？

思路：

1<=k<=min(j-1,cnt[v])
1<=j<=min(m,cnt[u])

已经枚举好 u v j k
边u-->v，其中u子树共选了j门，v子树选了k门
dp[u][j]+=max(dp[u][j],dp[u][j-k]+dp[v][k])

背包问题：(一维滚动数组)
(1) 正序枚举，完全背包，物品用无限次
(2) 倒序枚举，01背包，物品最多用一次

本题 j k应当倒序枚举 (01背包)

上代码：

#include <bits/stdc++.h>
#define maxn 305
using namespace std;
vector<int> to[maxn];
int w[maxn],fa[maxn],cnt[maxn],dp[maxn][maxn];
// dp[u][j]代表【以u为根子树】（u必选）选j门课的最大学分和
// cnt[u]是【以u为根的子树】的节点数 
int n,m;
void dfs(int u)
{
	dp[u][1]=w[u]; cnt[u]=1;
	for(int v:to[u])
	{
		dfs(v); cnt[u]+=cnt[v];
		for(int j=min(m,cnt[u]);j>=1;j--) // 倒序枚举 
		{
			for(int k=min(j-1,cnt[v]);k>=1;k--)
			{
				dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k]);
			}
		}
	}
}
int main()
{
	cin>>n>>m; m++; // 虚拟课程0必选
	for(int i=1;i<=n;i++)
	{
		cin>>fa[i]>>w[i];
		to[fa[i]].push_back(i);
	}
	dfs(0);
	cout<<dp[0][m];
	return 0;
}

第二题，【P2015 二叉苹果树】

题目描述

有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）

这棵树共有 N 个结点（叶子点或者树枝分叉点），编号为 1∼N，树根编号一定是 1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 4 个树枝的树：
2   5
 \ / 
  3   4
   \ /
    1
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。

我们不难发现，苹果在边上，所以要使用带权边 -->
vector<Edge> to[maxn]; // 其中：Edge成员变量有 u v w
0<=j<=min(q,cnt[u]-1)
0<=k<=min(j-1,cnt[v]-1)

状态转移方程：dp[u][j]=max(dp[u][j],dp[v][k]+w+dp[u][j-k-1]);

#include <bits/stdc++.h>
#define int long long
#define maxn 105
using namespace std;
struct Edge {
    int u,v,w;
};
vector<Edge> to[maxn];
int dp[maxn][maxn],fa[maxn],cnt[maxn];
int n,q;
void dfs(int u)
{
    dp[u][0]=0; cnt[u]=1;
    for(auto tmp:to[u])
    {
        int v=tmp.v,w=tmp.w;
        if(fa[u]==v) continue;
        fa[v]=u; dfs(v);
        cnt[u]+=cnt[v];
        for(int j=min(q,cnt[u]-1);j>=0;j--)
        {
            for(int k=min(j-1,cnt[v]-1);k>=0;k--)
            {
                dp[u][j]=max(dp[u][j],dp[v][k]+w+dp[u][j-k-1]);
            }
        }
    }
}
signed main()
{
    cin>>n>>q;
    for(int i=1;i<=n-1;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        to[u].push_back(Edge{u,v,w});
        to[v].push_back(Edge{v,u,w});
    }
    dfs(1);
    cout<<dp[1][q];
    return 0;
}

做完这所有题，我们也不难发现，这些题难得不行还是比较简单的,代码也就50行左右，只要掌握技巧，多练题，相信你便能熟练掌握！ >_<

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

GEO推广服务深度解读：AI搜索时代的企业流量新范式

GEO推广服务并非短期的流量手段，而是企业适应AI搜索时代的系统性能力升级。它要求企业从“建设网站”转向“构建知识体系”，从“购买流量”转向“被AI引用”。面对技术变革，企业唯有以系统化思维、专业化运营和持续迭代，才能在智能搜索时代掌握增长主动权。这不仅是营销领域的变革，更是企业数字能力的全面重塑。你，准备好了吗？

2048 AI社区

GPT刚更新Claude和Gemini也在卷开发者到底该选哪个

2048 AI社区

AI 为什么不绕过编程语言直接写机器码？

AI为何不直接生成机器码？文章探讨了一个看似技术性的问题背后的人文内涵。AI之所以继续使用编程语言而非直接输出机器码，本质上是为了继承人类积累的文明成果。编程语言作为人类思维的载体，构成了AI学习的"母语"，而机器码对AI而言则是难以理解的无序符号。编译器技术凝聚了人类半个多世纪的智慧结晶，AI直接生成机器码将失去这些优化。更重要的是，编程语言确保了代码的可读性和可维护性，使