目录
引入
考虑这样一个问题（P1352 没有上司的舞会）：
一棵树，每个节点 \(i\) 都有价值 \(v_i\)，对于每个子节点，不能和父节点同时选择，求最大价值和。
令 dp[x][0] 为在x的子树中表示i不取时值最大是多少。
令 dp[x][1] 为在x的子树中表示i取时值最大是多少。 选与不选两个状态，升维来保证没有后效性啦~
我们可以用这样一个函数（实际上是dfs）：
void tdp(int x)
{
for(int i = 0;i < tree[x].size();i++) //遍历儿子
{
int y = tree[x][i];
tdp(y);
dp[x][0] += max(dp[y][0], dp[y][1]);
dp[x][1] += dp[y][0];
}
}
树形dp
树上递推
在树上递推实现遍历整棵树。 这已经是惯常操作了呢~
先序遍历（关键词：到根）
例如：
求到根最远的节点？
后序遍历（关键词：子树）
例如：
如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
求直径（树上最长路径）
对于树上任意一点X，求出离P最远的点A，在找到离A最远的点B，A到B的路径就是树的直径。
使用反证法：证明过程点这里，感谢这位神犇 是你太懒了吧
这是一个例子
void dfs(int x, int fa)
{
for(int i = 0;i < g[x].size();i++)
{
int y = g[x][i];
if(y == fa) continue;
dis[y] = dis[x] + w[x][i];
dfs(y,x);
}
}
int main()
{
...
dis[1] = 0;
dfs(1, 0);
int A = 0;
for(int i = 1;i <= n;i++)
{
if(dis[i] > dis[A]) A = i;
}
dis[A] = 0;
dfs(A,0);
int B = 0;
for(int i = 1;i <= n;i++)
{
if(dis[i] > dis[B]) B = i;
}
cout << dis[B];
return 0;
}
换根DP法
我们来看这样一道题：市政服务大厅
D市共设有 \(N\) 个街区，编号 \(1\) ~ \(N\)；建有 \(N−1\) 条双向道路，编号 \(1\) ~ \(N-1\)，其中第 \(i\) 条道路长度 \(l_i\) ，连接了街区 \(a_i\) 与 \(b_i\) 。任意两个街区之间有且仅有一条路径。每个街区都常住有一定数量的市民，其中常住于街区 \(i\) 的市民共有 \(p_i\) 人。这里，市政服务大厅可选址于任意一个街区，但要使选址尽可能地优，就意味着所有常住市民到市政务府大厅的距离之和应尽可能地小（假设只考虑各个街区之间的距离，忽略同一个街区内部的距离）。
到x的总距离：
x子树外的人：到达 fa 后，一起走到x。sz[1] - sz[x]
x子树内的人：到达 fa 后，一起走到x。sz[1] - sz[x]
树上背包
我们来看例题 P2014 选课。
假设 dp[x][j] 表示x为根的子树分配j个名额的最大学分。
dp[x][...] 设为无穷小，dp[x][1] = a[x] 。
标准代码
void dfs(int x)
{
for(int i = 0;i <= n;i++)
dp[x][i] = -1e9;
dp[x][1] = a[x];
for(int i = 0;i < g[x].size();i++)
{
int y = g[x][i];
dfs(y);
for(int j = m;j >= 1;j--)
{
for(int k = 0;k < j;k++)
{
dp[x][j] = max(dp[x][j], dp[x][j-k] + dp[y][k]);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
m++;
for(int i = 1;i <= n;i++)
{
int fa;
cin >> fa >> a[i];
g[fa].push_back(i);
}
dfs(0);
cout << dp[0][m];
return 0;
}
链式前向星
点：head[i] 表示第i个点的最后一条边。
边：next[i] 表示第i条边的上一个起点相同的边的序号。
\(\color{white}{\text{ . .: }}\)to[i] 第i条边的上一个起点相同的边的序号。
struct edge
{
int to, w, nxt; // w是边长
}e[N*2];
int cnt, head[N];
void add(int x, int y, int z)
{
e[++cnt] = (edge){y, z, head[x]};
head[x] = cnt;
}
void dfs(int x, int fa)
{
for(int i = head[x];i;i = e[i].nxt)
{
int y = e[i].to;
if(y == fa) continue;
dfs(y,x)
}
}