Skip to main content

树形 DP

Summary

树形 DP 在树上做动态规划，通常设状态表示以某点为根的子树的某种最优值，自底向上由各子节点的状态合并而来，一遍 DFS 即可完成。以「没有上司的舞会」为例，对每个节点分选与不选两态：选它则其子节点都不能选，不选它则子节点取选或不选的较大者，父节点由各子节点逐个转移累加。文末给出换根 DP 的入口，指向树的重心一节，用于在把根从一个点换到相邻点时快速统计以各点为根时的信息，避免逐点重算。

参考资料​

简介​

树形 DP 在树上做动态规划，通常设 fuf_u 表示以 uu 为根的子树的某种最优值，自底向上由各子节点的状态合并而来，用一遍 DFS 实现。

实现​

以「没有上司的舞会」为例：fu,0f_{u,0}、fu,1f_{u,1} 分别表示不选、选节点 uu 时子树的最大权值。选 uu 则子节点都不能选，不选 uu 则子节点选或不选取较大者。

106 Bcpp
void dfs(int u)
{
	for(auto v:G[u])
	{
		dfs(v);
		f[u][0]+=max(f[v][0],f[v][1]);
		f[u][1]+=f[v][0];
	}
}

换根 DP​

详见 树的重心。

例题​

洛谷 P1352 没有上司的舞会

某大学有 nn 个职员，编号为 1…n1\dots n。

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

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

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

洛谷 P3478 [POI 2008] STA-Station

给定一个 nn 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。

一个结点的深度之定义为该节点到根的简单路径上边的数量。