忘得差不多了，来善后一下。
0x1 树形dp
树形dp，说简单了就是在树上按照树从根结点向叶子结点走的递归顺序+dp的状态转移的维护。
所以从根结点开始，维护一个点时，先维护它所有子结点的值，再来维护自己，相当于一个“先递归，再转移”的递归函数。
这是最基本的类型。
0x10 基础的树形dp
就是像开头说的那样的维护，有几种经典类型。
最大权独立集
随便选了一个， UVA1220
关乎到独立集大小，我们需要记录是否选择当前结点。
而唯一性的问题只需要看更新了自己的子树的选择是否唯一。
记得为了让所有结果好统计，我们用一个超根 \(0\) 结点连向真正的根结点，从 \(0\) 开始跑dfs。
多组数据记得清空。
void dfs(int u)
{
dp[u][0] = 0;//表示没有选u
dp[u][1] = 1;//选了u，那么至少有u这个结点
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
dfs(v);//先递归
//再维护
//先维护不选u的，此时选不选v都可以
if (dp[v][0] == dp[v][1])//两边子树结果相同，那肯定不唯一了
{
dp[u][0] += dp[v][0];
f[u][0] = 1;//1表示不唯一
}
else if (dp[v][0] > dp[v][1])//不选的更优
{
dp[u][0] += dp[v][0];
if (f[v][0] == 1)
{
f[u][0] = 1;//选哪种唯一性跟哪种，这么写而不是f[u][0] = f[v][0]是为了保留之前的结果，保险
}
}
else
{
dp[u][0] += dp[v][1];
if (f[v][1] == 1)
{
f[u][0] = 1;
}
}
//再维护选了u，此时只能不选v
dp[u][1] += dp[v][0];
if (f[v][0] == 1)
{
f[u][1] = 1;
}
}
return;
}
最小权覆盖集
注意，这个题是“某个士兵在一个结点上时，与该结点相连的所有边都可以被瞭望到”，并且要求所有边都要被瞭望到。
所以我们这么考虑：\(dp[i][0]\) 表示没选 \(i\) 时，此子树的最小权覆盖集大小。
那么它的每个儿子结点都要有士兵，这样才能让它连出去的每一条边都被瞭望到。
\(dp[i][1]\) 则选了 \(i\)， 所有连出去的边都被瞭望到了，所以它的儿子结点可选可不选。
注意， 要将 \(dp[i][1]\) 初始化为 \(1\), 因为至少选了一个点；这个题是有根树，要建双向边，dfs时记录上一个结点防止重复走一条边导致死循环，从任意一个点作为根开始dfs。
void dfs(int x, int fa){
dp[x][1] = 1;//初始值
for (int i = 0; i < T[x].size(); ++i){
int y = T[x][i];
if(y == fa){
continue;
}//不要走了重复的点
dfs(y, x);
dp[x][0] += dp[y][1];
dp[x][1] += min(dp[y][0], dp[y][1]);
}
return ;
}
那再做一个，P2899
额，这次对于一个节点 \(i\)，需要考虑它是被父亲节点连接，还是自己搭天线，或者被儿子结点连接。
和P2016不同的是，它要求所有点被看到，P2016要求的是边。
\(dp[i][0/1/2]\) 分别表示由父亲连接，由自己搭线，由儿子连接。
用代码解释把。
void dfs(int u, int fa)
{
dp[u][1] = 1;//自己搭了线，肯定至少有自己这个发电台。
int sum = 0, cnt = inf;
for (int i = 0; i < G[u].size(); ++i)
{
int w = G[u][i];
if (w == fa)
{
continue;
}
dfs(w, u);
dp[u][0] += Min(dp[w][1], dp[w][2]);//如果由父亲连接，则自己不是发电台，那么儿子结点就不能通过父亲连接
dp[u][1] += Min(dp[w][0], Min(dp[w][1], dp[w][2]));//自己是发电台，儿子肯定能连接，所以都可以
//而对于u让儿子维护时，需要有一个儿子w是发电台，即dp[w][1]，其他儿子可以是发电台也可以用儿子维护，即Min(dp[w][1], dp[w][2])
//于是先假想所有的儿子都选Min(dp[w][1], dp[w][2])，然后如果所有的儿子都选择了dp[w][2]，那么cnt绝对>0，此时加上cnt就会使一个儿子取dp[w][1]并且为所有儿子中代价最小的
sum += Min(dp[w][1], dp[w][2]);
cnt = Min(cnt, dp[w][1] - dp[w][2]);
}
if (cnt > 0)
{
sum += cnt;
}
dp[u][2] = sum;
if (G[u].size() == 1 && u != 1)
{
dp[u][2] = inf;//特判，如果是叶子节点，不可能用儿子维护
}
return;
}
这种覆盖所有点的，类似的还有P2458，P2279。
P2279需要维护儿子和孙子，父亲和爷爷，还有自己，五类，会吐。
所以解决这一类，引入一种贪心：尽量被自己的爷爷维护。
确实，根本不需要解释。
所以对于P2279，这么做：跑dfs给节点标上深度 \(dep\)，用 \(diz\)，\(dio\)，\(dit\) 分别表示被距离为 \(0\) 的点覆盖（自己），被距离为 \(1\) 的（儿子或父亲），被距离为 \(2\) 的（孙子或爷爷）。
然后优先爷爷。
void bfs()
{
dep[1].d = 0;
q.push(1);
while (q.empty() == 0)
{
cur = q.front();
q.pop();
for (int i = 0; i < G[cur].size(); ++i)
{
nxt = G[cur][i];
dep[nxt].d = dep[cur].d + 1;
q.push(nxt);
}
}
return;
}
int main()
{
scanf("%d", &n);
dep[1].id = 1;
for (int i = 2; i <= n; ++i)
{
dep[i].id = i;
scanf("%d", &a);
fa[i] = a;
G[a].emplace_back(i);
}
bfs();
sort(dep + 1, dep + n + 1, cmp);
for (int i = 1; i <= n; ++i)
{
//cout << fa[dep[i].id] << ' ';
int u = dep[i].id;
int v = fa[u];
int w = fa[v];
if ((diz[u] == 1 || diz[v] == 1 || diz[w] == 1) || (dio[u] == 1 || dio[v] == 1) || dit[u] == 1)
{
continue;
}//如果已经被覆盖过
diz[w] = dio[fa[w]] = dit[fa[fa[w]]] = 1;//否则在爷爷上放，把上面的全部赋值
++ans;
}
printf("%d", ans);
return 0;
}
当然，这种简洁的贪心还可以运用到别的上面，比如直接生猛地上P3942，k层覆盖，这个要是写树形dp就是想不开，找死。
0x11 树上背包
原文地址：http://www.cnblogs.com/Ziqqurat/p/16783294.html
