树形DP（自用）

基本原理

在对树结构进行从树根到树枝或从树枝到树根的搜索中，可以记忆化储存我们需要的信息，并利用储存信息进一步推导其他节点的信息(相同子问题)，从而达到减少搜索时间的目的，实际上这是一种更聪明的暴力搜索。

流程

定义状态储存数组->分析状态转移方程->dfs->按照方程更新数组->保存答案->输出

void dfs(int u,int father) {
f[1][u] = w[u], f[2][u] = 1e9, f[3][u] = 0;
for (int v : g[u]) {
if (v == father)continue;
dfs(v,u);
f[1][u] += min(min(f[1][v], f[2][v]),f[3][v]);
f[3][u] += min(f[1][v], f[2][v]);
}
for (int i : g[u]) {
f[2][u] = min(f[2][u], f[1][i] + f[3][u] - min(f[1][i], f[2][i]));
}
}

注意细节

树根是谁是否影响答案？
遍历的顺序？
是否需要初始化状态数组？