树形DP

树形DP题单：0x2 树形dp - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

最大点权独立集

模板题：P1352 没有上司的舞会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 蓝桥舞会 - 蓝桥云课 (lanqiao.cn)

给一棵n个节点的树，每个节点都有一个权值，要找到一个结点集，使得 树的每条边的两端，不能同时都一个在集合里，同时集合权值和最大。

说明：这种适用于一张图（选了一个节点，就不能选它相连的邻居）

解法：创建一个dp[n][2]数组，dp{j，0} 就表示以 j 为根的子树不选 j 的最大价值；dp{j，1}表示选 j 的最大价值。

若选择一个节点的权值，其子节点就无法被选取；若不选择，其子节点可以选，也可以不选。

由此，我们可以得到如下的转移方程： \[ dp[j, 0] = \sum_{i}^{son} \max(dp[i, 0], dp[i,1]) \newline dp[j, 1] = \sum_{i}^{son} dp[i, 0] \] DFS遍历

void dfs(int x, int f){
	for(auto it : e[x]){
		if(it == f) continue;
		dfs(it, x);
        // 此时，子节点已经处理好
		dp[x][0] += max(dp[it][1], dp[it][0]);
		dp[x][1] += dp[it][0];
	}
}

主函数

cin>>n;
for(int i = 1 ; i <= n ; i ++){
    // 输入权值，初始化DP
    cin>>dp[i][1];
}
for(int i = 1 ; i <= n-1 ; i ++){
    int x,y;cin>>x>>y;
    e[y].push_back(x);
    e[x].push_back(y);
}
dfs(1, -1);
cout<<max(dp[1][0],dp[1][1]);

最小点权覆盖集

模板题：P2016 战略游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

给一棵n个节点的树，每个节点的都有权值，要找到一个结点集，使得树的每条边的两端，至少有一个在集合里，同时使得集合权值和最小。（这题的节点权值为1）

和最大点权独立集类似：一个节点若选择，其邻居可以选，也可以不选；一个节点若不选，其邻居一定选。

状态转移方程如下： \[ dp[j,1] = \sum_{i}^{son} min(dp[i,0],dp[i,1]) \newline dp[j,0] = \sum_{i}^{son} dp[i,1] \] DFS

void dfs(int x, int f){
	for(auto it : e[x]){
		if(it == f) continue;
		dfs(it, x);
		dp[x][1] += min(dp[it][1], dp[it][0]);
		dp[x][0] += dp[it][1];
	}
}

主函数

cin>>n;
for(int i = 0 ; i < n ; i ++){
    int x,m;cin>>x>>m;
    for(int j = 0 ; j < m ; j ++){
        int y;cin>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
}
// DP初始化
for(int i = 0 ; i < n ; i ++){
    dp[i][1] = 1;
}
//DP
dfs(0, -1);
cout<<min(dp[0][1],dp[0][0]);

树上背包

模板题：CTSC1997 选课 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

树上背包，也叫 有依赖关系的背包问题。

题意：给一个n节点的森林，标号从1-n，每个节点存在一个权值。对这个森林内的每棵有向树，都要求出一条从根出发的路径，所有路径的节点数量和不超过m，同时节点权值和最大。

首先，设置一个超点0，连接0和每一棵树的根。这样就把n条路径的问题，转化为求0出发的一条路径。

然后，我们设置一个状态DP数组，dp{u, k} 表示 以u节点为根，容量为k的最大权值和。有如下的状态转移方程： \[ dp[x, j] = max(dp[x,j], dp[x, j-k] + dp[it][k]) \] 此处，x表示父节点，it表示子节点，j 和 k 分别表示 到两个节点剩下的容量。

最后，dfs更新dp数组，我们可以得到ans == dp[0][m]。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 305;

int n,m;
int dp[maxn][maxn];
vector<int > e[maxn];

void dfs(int x){
	for(auto it : e[x]){
		dfs(it);
	}
	for(auto it : e[x]){
		for(int j = m ; j >= 0 ; j --){
			// j不可以 == k
			// 因为至少要学习父节点，才能学子节点
			for(int k = 0 ; k < j ; k ++){
				dp[x][j] = max(dp[x][j], dp[x][j-k] + dp[it][k]);
			}
		}
	}
}

int main(void){
	cin>>n>>m;
	m++;
	for(int i = 1 ; i <= n ; i ++){
		int x,v;cin>>x>>v;
		e[x].push_back(i);
        dp[i][1] = v;
        // 如果不是必须要刚好修m门课，应该这么写：
		// for(int j = 1 ; j <= m ; j ++){
		//	dp[i][j] = v;
		// }
	}
	dfs(0);
	cout<<dp[0][m];
	return 0;
}

换根DP

模板题： POI2008 STA-Station - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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

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

分析：

对于一个父节点x，和它的子节点y，

扭转了x和y的位置以后，y以下（含y）的全部节点（siz[y]）深度都要 - 1，其他节点（n-siz[y]）的深度都要 + 1

假设我们已经知道了以x为根的深度和dp[x]，和 分别以x，y为根的子树节点数siz[x], siz[y]。

那么，我们可以通过如下的状态转移方程，得到dp[y]： \[ dp[y] = dp[x] + (n - siz[y]) - siz[y] \] dfs函数

// 首先，我们dfs求出：以节点1为根时，每棵子树总节点数
void dfs(ll x, ll f){
	for(auto it : e[x]){
		if(it == f) continue;
		depth[it] = depth[x] + 1;
		dfs(it, x);
		siz[x] += siz[it];
	}
}

reDfs函数

// 然后，再次dfs求出 以每个节点为根的深度和
void reDfs(ll x, ll f){
	for(auto it : e[x]){
		if(it == f) continue;
        //dp[it] = dp[x] + (n - siz[it]) - siz[it]
		dp[it] = dp[x] + n - 2*siz[it];
		reDfs(it, x);
	}
}

主函数

// 建图
cin>>n;
for(int i = 1 ; i <= n-1 ; i ++){
    ll u,v;cin>>u>>v;
    e[u].push_back(v);
    e[v].push_back(u);
}
// dp求最值
for(int i = 1 ; i <= n ; i ++) siz[i] = 1;
dfs(1, 0);
for(int i = 1 ; i <= n ; i ++) dp[1] += depth[i];
reDfs(1, 0);
for(int i = 1 ; i <= n ; i ++){
    if(dp[i] > max_){
        max_ = dp[i];
        ans = i;
    }
}
cout<<ans;