## 树型DP
**树型DP**,即在树上做动态规划。树是无环图，顺序可以是从叶子到根节点，也可以从根到叶子节点。一般树型DP的特征很明显，即状态可以表示为树中的节点，每个节点的状态可以由其子节点状态转移而来（从叶子到根的顺序），或是由其父亲节点转移而来（从根到叶节点的顺序），也可是两者结合。找出状态和状态转移方程仍然是树型DP的关键。
### 例1：没有上司的晚会
#### 题目描述
Ural大学有$N$个职员，编号为$1 \sim N$。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数，第$i$个职员的快乐指数为$h_i$。 现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起参加宴会。
#### 数据范围
$1 \leq N \leq 60000, -128 \leq h_i \leq 127$
#### 分析
设$f_{i,0/1}$表示节点$i$不参加(或参加)晚会时子树$i$的最大快乐指数。
若$i$不参加，则$i$的直接下属$j$可以参加，也可以不参加。
$f_{i,0} =\sum_{j \in son_i} max(f_{j,0}, f_{j,1}$
若$i$参加，则$i$的直接下属$j$不能参加宴会。
$f_{i,1} = \sum_{j \in son_i} f_{j,0} + h_i$
叶子节点的初始状态$f_{leaf,0}=0, f_{leaf, 1}=h_{leaf}$.
因为自下而上转移，所以可以采用记忆化搜索的方法。
```cpp
#include <bits/stdc++.h> using namespace std; #define maxn 60006 int n, ecnt, h[maxn], fir[maxn]; int f[maxn][2]; bool vis[maxn]; struct node{ intv,nxt; }eds[maxn << 1];void adde(int u, int v){ eds[++ecnt].v=u, eds[ecnt].nxt=fir[v], fir[v] =ecnt; //只保存父亲到儿子的边 }
int dfs(int r, bool flg){ if(f[r][flg] !=0xd0d0d0d0) returnf[r][flg]; if(flg==0) f[r][flg] =0; elsef[r][flg] =h[r]; for(inti=fir[r]; i; i=eds[i].nxt){ intt=eds[i].v; if(flg==0){ f[r][flg] +=max(dfs(t, 0), dfs(t, 1)); } elsef[r][flg] +=dfs(t, 0); } returnf[r][flg]; } int main(){ inta, b, root; scanf("%d", &n); for(inti=1; i<=n; i++)scanf("%d", &h[i]); for(inti=1; i<n; i++){ scanf("%d%d", &a, &b); adde(a, b); vis[a] =1; }
for(inti=1; i<=n; i++){ if(vis[i] ==0) {root=i; break;} //找出根节点 } memset(f, 0xd0, sizeof f); dfs(root, 0); dfs(root, 1); printf("%d\n", max(f[root][0], f[root][1])); return0; } ``` ### 例2. 二叉苹果树 #### 题目描述 有一棵苹果树，如果树枝有分叉，一定是分$2$叉（就是说没有只有$1$个儿子的结点） 这棵树共有$N$个结点（叶子点或者树枝分叉点），编号为$1 \sim N$,树根编号一定是$1$。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树: 2 5 \ / 3 4 \ / 1 现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。 给定需要保留的树枝数量，求出最多能留住多少苹果。 #### 输入格式 第1行: 2个空格分开的整数，$N$ 和 $Q(1 \leq Q \leq N,1 \lt N \leq 100)$，$N$表示树的结点数，$Q$表示要保留的树枝数量。 接下来$N-1$ 行描述树枝的信息。 每行$3$个整数, 前两个是它连接的结点的编号。第3 个数是这根树枝上苹果的数量。 每根树枝上的苹果不超过30000 个。 #### 输出格式 第1行：一个整数，表示最多能留住的苹果的数量。 #### 分析 如果设状态$f_{i,j}$为子树$i$中包含$j$边，转移时不太自然。因为还要考虑节点$i$到儿子的边是否保留的情况。 于是，将父子边的边权下放到儿子处，设状态$f_{i,j}$表示$子树$i$包含$j$个点的最大的苹果数量。 于是得到状态转移方程为 $$f_{i,j}=\max_{k=0}^{j-1}(f_{l,k}+f_{r,j-1-k}) $$ 答案为$f_{Q+1}$。因为包含$Q+1$个点时，刚好包含$Q$条边。 标签：int,树枝,####,leq,DP,树型,节点,flg From： https://www.cnblogs.com/hefenghhhh/p/18675815