树上型
树上型
可以理解成后缀型（即当前结点即整个子树的某种性质）
常见处理方法，通过设计一层状态，来把多层问题（如需下下层）转化成只需要下一层（典型如打家劫舍III、树的最大独立集）
注：可能有同学觉得树形 DP 没有重复访问同一个状态（重叠子问题），并不能算作 DP，而是算作普通的递归。这么说也有一定道理，不过考虑到思维方式和 DP 是一样的自底向上，所以仍然叫做树形 DP。此外，如果是自顶向下的递归做法，是存在重叠子问题的，一般要结合记忆化搜索实现。
例题
树的最大独立集
k
无根树，转有根树：任选一个根r，无根树就变成有根树了
状态：f[i]表示以i为根的子树的最大独立集的大小。
转移：f[i]=max{1+sum{f[j]|j in gs(i)}, sum{f[j]|j in s(i)}}
拓展，
- 树上的打家劫舍其实就是这个题的二叉有根树版本。
- 打家劫舍其实就是这个题的单链树版本。
- 打家劫舍II其实就是这个题的简单环版本。
实现层面：
- 可以用刷表法，因为转移方程需要枚举所有的儿子和孙子，颇为不便，当计算出一个
f[i]后，用它去更新i的父亲和祖父结点的累加值。 - 下面的写法，实践中更为常用，只需要从儿子更新，不需要记录更多
K Edit Distance
给定N个字符串，以及目标字符串Target
• 问哪些字符串和Target的编辑距离不大于K
• 一次编辑包括插入一个字符或删除一个字符或修改一个字符N次Edit Distance有重复计算，所以构建字典树，在树上DP
状态：f[s][j]表示前缀结点s和target前j个字符的最小编辑距离
转移：f[s][j]=min{f[s][j-1]+1,f[q][j-1]+1,f[q][j]+1,f[q][j-1]|q==target[j-1]}
刷表法
Hali-Bula的晚会
树的最大独立集，最大独立集是否唯一
状态：
f[i][0/1]表示以i为根的子树，不选/选i的最大独立集的大小。g[i][0/1]表示以i为根的子树，不选/选i的最大独立集的是否唯一。
转移：
f[i][1]=sum{f[j][0]|j in s(i)}g[i][1]=and{g[j][0]}f[i][0]=sum{max{f[j][0],f[j][1]}|j in s(i)}g[i][1]=or{f[j][0]==f[j][1]}||max的f的g=false
树的重心
状态：f[i]表示以i为根的子树结点个数
转移：f[i]=sum{f[j]|j in s(i)}+1
树的最长路径（最远点对）
完美的服务
n台机器形成树状结构，要求每个不是服务器的计算机恰好和一台服务器计算机相邻，求服务器最少的数量
状态：
f[i][0]表示i是服务器，则每个结点也可以不是。f[i][1]表示i不是服务器，其父亲是服务器。意味着i的所有子节点都不是服务器f[i][2]表示i和其父亲都不是服务器。这意味着i恰好有一个儿子是服务器。
转移：子节点v
f[u][0]=sum{min{f[v][0],f[v][1]}}+1f[u][1]=sum{f[v][2]}f[u][2]=min{f[u][1]-f[v][2]+f[v][0]}
行