树形DP学习笔记
树形DP概念
顾名思义，树形DP就是在树上进行DP
树形DP实现
一般来说，树形DP通过深度优先搜索实现。将它的子树的信息整合起来，就是树形DP。不过树形DP的题目比较灵活，没有什么固定的做法。状态的主要表现形式式 \(dp[i][0/1]\) ，其中 \(0\) 表示不选这个节点， \(1\) 表示选择这个节点。
P1352 没有上司的舞会
我们设 \(dp_{i,0}\)? 表示第 \(i\)? 个人没来，他的下属们的最大快乐值， \(dp_{i,1}\)? 表示第 \(i\)?? 个人来，他的下属们的最大快乐值
很显然，我们有如下转移方程(设当前节点为 \(u\) ,它的子节点为 \(v\))
\[\begin{cases}dp_{u,0} = \sum \max(dp_{v,0},dp_{v,1}) \\ dp_{u,1} = \sum dp_{v,0} \end{cases} \]先找到根节点（职位最高的领导），一步步向下遍历，最后的答案为(设根节点为 \(s\) ) \(\max(dp_{s,0},dp_{s,1})\)?
代码：
#include
#include
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=6e3+7;
vector edge[N];
int dp[N][2];
int r[N],fa[N];
int n;
inline void dfs(int u) {
dp[u][1]=r[u];
for(int i=0,v;i P1122 最大子树和
我们设 \(dp_u\) 表示选择 \(u\) 点时子树的最大和，显然有转移方程
\[dp_u = \sum \max(dp_v,0) \]直接计算即可
代码：
#include
#include
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int inf=0x7fffffff;
const int N=1.6e4+7;
vector edge[N];
int dp[N];
int a[N];
int n,ans=-inf;
inline void AddEdge(int u,int v) {
edge[u].push_back(v);
edge[v].push_back(u);
}
inline void dfs(int u,int fa) {
dp[u]=a[u];
for(int i=0,v;i P2014 [CTSC1997] 选课
树形背包模板题，套用模板即可。
#include
#include
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=1e3+7;
vector edge[N];
int dp[N][N];
int s[N];
int n,m;
inline void AddEdge(int u,int v) {
edge[u].push_back(v);
}
inline void dfs(int u,int t) {
if(!t)
return ;
for(int i=0,v;i P2016 战略游戏
求一棵树的最小点覆盖。
设 \(dp[i][1/0]\)? 表示第 \(i\)?? 个点选或不选时子树所需的最小士兵数，显然有转移方程
\[\begin{cases}dp_{u,0} = \sum dp_{v,1} \\ dp_{i,1} = \min (dp_{v,0},dp_{v,1}) \end{cases} \]代码：
#include
#include
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=1.5e3+7;
vector edge[N];
int dp[N][2];
int n;
inline void AddEdge(int u,int v) {
edge[u].push_back(v);
}
inline void DFS(int u) {
dp[u][1]=1;
for(int i=0,v;i 双倍经验：UVA1292 Strategic game
P2015 二叉苹果树
注意到当某条边被保留下来时，从根节点到这条边的路径上的所有边也都必须保留下来
我们可以设 \(dp_{i,j}\) 表示 \(i\) 的子树上保留 \(j\)? 条边，至多保留的苹果数目。
显然由转移方程：
\[dp_{u,i}=\max(dp_{u,i},dp_{u,i-j-1}+dp_{v,j}+edge[i].w) \ \ (1 \leq i \leq \min(q,siz_u),0 \leq j \leq min(siz_v,i-1)) \]代码：
#include
#include
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=1e2+7;
vector > edge[N];
int dp[N][N];
int siz[N];
int n,m;
inline void AddEdge(int u,int v,int w) {
edge[u].push_back({v,w});
}
inline void dfs(int u,int fa) {
for(int i=0,v,w;i P3478 [POI2008] STA-Station
我们先用一次深搜处理出以 \(1\) 为根时每个节点的深度，再用一次深搜处理出以任意节点为根时所有结点的深度之和。
那么第二次深搜怎么写呢？
设 \(dp_u\) 表示以 \(u\) 为根时所有结点的深度之和， \(siz_u\) 表示 \(u\) 为根时子树的大小，我们可以得到这么一个转移方程（设 \(v\) 为 \(u\) 的其中一个儿子）：
\[dp_v=dp_u-siz_v+n-siz_v \]直接DP即可，代码（记得开long long）：
#include
#include
typedef long long ll;
using namespace std;
const int N=1e6+7;
vector edge[N];
ll dp[N];
int deep[N],siz[N];
int n,ans;
inline void AddEdge(int u,int v) {
edge[u].push_back(v);
edge[v].push_back(u);
}
inline void dfs1(int u,int fa,int w) {
siz[u]=1,deep[u]=w;
for(int i=0,v;idp[ans])
ans=i;
printf("%d",ans);
return 0;
}
CF219D Choosing Capital for Treeland
与上题做法类似，也是两遍深搜。这一次我们设 \(dp_u\) 为以 \(u\) 为根时要翻转的道路条数，显然有：
\[\begin{cases}dp_v=dp_{n}+1(u \to v)\\ dp_v=dp_{n}-1 (v \to u)\end{cases} \]完整代码：
#include
#include
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int inf=0x3f3f3f3f;
const int N=2e5+7;
vector > edge[N];
int dp[N];
int n,ans=inf;
inline void AddEdge(int u,int v) {
edge[u].push_back({v,true});
edge[v].push_back({u,false});
}
inline int dfs1(int u,int fa) {
int res=0;
for(int i=0,v;i