树形DP
树形DP，顾名思义就是在一棵树上进行DP。
这是一道模板题，要求子节点和父节点中最多选一个的情况下求出最大欢乐值。
树形DP的原理是 DFS 子节点并记录，然后父节点再通过数据进行操作。
设 dp_{i,0} 为不选 i 得到的最大值， dp_{i,1} 为选 i 得到的最大值，易得转移方程：
dp_{i,0}=\sum_{j=1}^{e_i.size()}\max(dp_{j,0},dp_{j,1})
dp_{i,1}=\sum_{j=1}^{e_i.size()}dp_{j,0} + a_i
也很容易得出 DFS 代码（链式前向星，防卡vector）：
void dfs(int x){
for(int i=head[x];i;i=s[i].nxt){
dfs(s[i].to);
dp[x][1]+=dp[s[i].to][0];
dp[x][0]+=max(dp[s[i].to][1],dp[s[i].to][0]);
}
dp[x][1]+=a[i];
}
最终结果就是 \max(dp_{root,1},dp_{root,0}) 。
时间复杂度 O(n) 。
树形背包
有时，背包DP的题目可能会加上一些限制，比如需要先选某件物品，这时就需要用到树形背包。
树形背包让前提条件成为这个物品的父节点，从上往下 DFS ，一定先遍历到父节点。
这是一道经典的树形01背包，先修课即为这个课程的父节点，这样就形成了一篇森林。
我们以 0 为根节点，连接所有的其他小树，形成一棵大树，从 0 开始遍历。
设 dp_{i,j} 为在以 i 为根节点的子树选择 j 个节点的最大贡献，则易得状态转移方程：
dp_{u,j}=\max(dp_{u,j},dp_{v,j}+dp_{u,j-k})
其中， v 为 u 的子节点，枚举 k 且 0 \le k < j 。
由此，易得 DFS 部分代码：
void dfs(int x){
for(int i=head[x];i;i=s[i].nxt){
int y=s[i].to;
dfs(y);
for(int j=m+1;j>=1;j--){//m+1是因为根节点从0开始
for(int k=0;k<j;k++){
dp[x][j]=max(dp[x][j],dp[y][k]+dp[x][j-k]);
}
}
}
}
时间复杂度 O(nm^2) 。（似乎有大佬写出了 O(nm) 写法）
换根DP
有时，树形DP也会变形，换根DP主要解决将一棵树中的节点作为根节点考虑的问题。
换根DP入门题，对于本题，很容易想到暴力每个节点都遍历一遍的 O(n^2) 做法，但是时间明显不允许。
设 dp_i 为节点 i 的价值， size_i 为以 i 为根的子树的总节点数：
可以观察父节点价值与子节点价值的关系，从父亲与儿子来观察，我们可以发现，如果 u 为 v 的父亲，那么 dp_v=dp_u+size_1-size_v \times 2 ，以下为具体解释：
======================================================
从以 v 为根的这棵子树提供的价值看，从 u 变为 v ，相当于 dp_u 中的子孙部分贡献全部 -1 ，也就是 -size_v 。
再看其他节点的贡献，很明显， dp_u 的另一部分都会 +1 ，也就是 +size_1-size_v 。
总的来看， dp_v=dp_i+size_1-size_v \times 2 。
======================================================
当然，这些前提是我们需要至少 1 个节点的总贡献，所以我们需要先暴力计算一个节点，也就是说我们要进行两次 DFS 。
即得代码：
void dfs1(int u){
sz[u]=1;
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(vis[v]) continue;
dfs1(v);
sz[u]+=sz[v];
}
}
void dfs2(int u){
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(vis[v]) continue;
f[v]=f[u]+sz[1]-sz[v]*2;
dfs2(v);
}
}
两次 DFS 的时间复杂度皆为 O(n) ，所以总复杂度也为 O(n) 。
求赞qwq