树形 DP 学习笔记（一）
xuchuhan
·
·
算法·理论
前言
本文讲解如何用树形 DP 解决兄弟节点间没有数量上的约束关系的树上问题。状态通常是 dp_i 表示以 i 为根节点的子树的信息。
一般是将各个子树的信息合并至根节点的信息，故一般先递归再转移。
这种树形 DP 较为简单，写几道例题看一看。
P1122 最大子树和
设 dp_x 表示以 x 为根的子树的最大子树和。对于边 x\rightarrow to，其决策是以 x 为根的子树选不选以 to 为根的子树中的最大子树和。故有转移 dp[x]=max(dp[x],dp[x]+dp[to]);。
P1352 没有上司的舞会
经典树形 DP 入门题。
发现每个点选或不选会影响其子孙节点的决策，故考虑升维。
```cpp
dp[x][0]+=max(dp[to][0],dp[to][1]);
dp[x][1]+=dp[to][0];
```
### [P2585 [ZJOI2006] 三色二叉树](https://www.luogu.com.cn/problem/P2585)
状态转移很套路，设二维就可以了，一维是根节点，二维是染的色，可以将颜色绿、红、蓝分别设为数字 $\texttt{0/1/2}$ 进行转移。
主要是谈谈怎么建树。可以直接递归建树，因为题目给出的输入顺序是按照 DFS 序给出的，所以我们可以顺其自然，一边递归一边建树。如下：
```cpp
int build(){
int cur=++tot;
if(s[cur]=='2'){
ls[cur]=build();
rs[cur]=build();
}
else if(s[cur]=='1')
ls[cur]=build();
return cur;
}
```
### [P1131 [ZJOI2007] 时态同步](https://www.luogu.com.cn/problem/P1131)
$dp_x$ 表示以 $x$ 为根的子树时态同步所需要的代价。我们需要先找到这棵子树中最长的距离，然后再调整其他的距离。但最长的距离也需要维护，故进行 $2$ 遍 DFS。一遍求最长距离，一遍转移。
部分代码：
```cpp
dis[x]=max(dis[x],dis[to]+w);//以x为根节点的子树中的最长链
dp[x]+=dis[x]-dis[to]-w;//将其它链调整至最长链的长度
```
怎么感觉写的有点少……溜了溜了。