本题即树的最大独立集问题。

有$N$名职员，编号为$1\dots N$，他们的关系就像一棵以老板为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数$r_i$，现在要召开一场舞会，使得没有职员和直接上司一起参会。主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

令$f(v)$表示以$v$为根的子树中，选择$v$的最优解，$g(v)$表示以$v$为根的子树中，不选$v$的最优解。

则对于每个状态，都存在两种决策（其中$u$代表$v$的儿子）：

• 选择$v$时，可选也可不选$u$，此时有 g ( v ) = ∑ max ⁡ { f ( u ) , g ( u ) } g(v)=\sum\max\{f(u),g(u)\} g(v)=∑max{f(u),g(u)}；
• 不选$v$时，一定不能选$u$，此时有$f(v)=r_i+\sum g(u)$。

时间复杂度为$\mathcal{O}(N)$。
注意本题需要寻找根节点，没有上司的结点即为根节点，读入时用数组标记即可。

#include <cstdio>
#include <vector>
#define maxn 6005
using namespace std;inline int max(int x, int y) { return x > y? x: y; }vector<int> G[maxn]; // 邻接表
bool bad[maxn]; // 根结点标记
int f[maxn], g[maxn]; // 数据存储void dfs(int v) // 遍历结点v
{// 读入时已初始化，这里可省略for(int u: G[v]) // 遍历子结点{dfs(u); // 先对子结点进行dfs// 更新当前dp状态f[v] += g[u]; // 选择v，不能选ug[v] += max(f[u], g[u]); // 不选v，u可选可不选}
}int main()
{int n;scanf("%d", &n); // 结点个数for(int i=0; i<n; i++)scanf("%d", f + i); // 相当于提前初始化好f[i]=r[i]for(int i=1; i<n; i++) // N-1条边{int u, v;scanf("%d%d", &u, &v); // 读入一条边G[--v].push_back(--u); // 0-index，存入邻接表bad[u] = true; // 标记不可能是根结点}int root = -1; // 根结点变量for(int i=0; i<n; i++)if(!bad[i]) // 找到根结点{root = i; // 记录根结点break;}dfs(root); // 开始进行树形DPprintf("%d\n", max(f[root], g[root])); // 根结点也有两种选择return 0;
}

有$N$门课，第$i$门课的学分是$s_i$。每门课有不超过一门先修课，需要上了先修课才能上这门课。现要选$M$门课，使得学分总和最大。

每门课最多只有一门先修课，这符合树结构的特点，与有根树中一个点最多只有一个父亲结点的特点类似。因此，我们根据数据构造一棵树，课程的先修课为这门课的父结点。又由于给定的输入是一个森林（多棵树组成的不一定连通的图），不是一棵完整的树，因此我们添加虚拟根结点$0$（$s_0=0$），将没有先修课的结点全部连到它下面，并从这里开始dfs。注意此时必须选中$0$号结点（它是所有课程的直接或间接先修课），所以操作前先将$M$加上$1$。

格式问题解决，下面考虑如何$\text{DP}$。
令$f[i][j]$表示当前在结点$i$、且已经选了$j$门课时的最大学分数量，则答案为$f[0][M+1]$。状态转移方程等详见代码。时间复杂度为$\mathcal{O}(NM)$，有兴趣的可以自己尝试证明。

#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 305
using namespace std;// dp算法中常用的模板，等效于x=max(x,y)
inline void setmax(int& x, int y)
{if(x < y) x = y;
}vector<int> G[maxn]; // 邻接表
int n, m, f[maxn][maxn];int dfs(int u) // 遍历结点u，返回值为其子树大小
{int tot = 1; // 记录子树大小，初始为1for(int v: G[u]) // 遍历u的所有子结点{int sz = dfs(v); // 对当前子结点进行搜索// 状态转移，注意i倒序，防止串连转移现象for(int i=min(tot, m); i>0; i--) // 子树大小优化可降低算法复杂度for(int j=1, lim=min(sz, m-i); j<=lim; j++)setmax(f[u][i + j], f[u][i] + f[v][j]); // 更新状态tot += sz; // 加到当前子树下}return tot; // 返回子树大小
}int main()
{scanf("%d%d", &n, &m);for(int i=1; i<=n; i++){int a;scanf("%d%d", &a, f[i] + 1); // 初始化f[i][1]=s[i]G[a].push_back(i);}m ++; // 别忘了这一句dfs(0);printf("%d\n", f[0][m]);return 0;
}

给定一个$n$个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。

先考虑最简单粗暴的方法，即为枚举所有结点，代码如下：

#include <cstdio>
#include <vector>
#define maxn 1000005
using namespace std;vector<int> G[maxn];int dfs(int v, int d, int par)
{int s = d;for(int u: G[v])if(u != par)s += dfs(u, d + 1, v);return s;
}int main()
{int n;scanf("%d", &n);for(int t=n; --t; ){int u, v;scanf("%d%d", &u, &v);G[--u].push_back(--v);G[v].push_back(u);}int ans = 0, maxDepth = dfs(0, 0, -1);for(int root=1; root<n; root++){int d = dfs(root, 0, -1);if(d > maxDepth) ans = root, maxDepth = d;}printf("%d\n", ++ans);return 0;
}

很明显，这种做法时间复杂度为$\mathcal{O}(n^2)$，又因为$n\le 10^6$，所以无法得全分，评测结果如下：

好家伙，居然还有50分，本以为最多30…

下面来考虑换根DP的方法。不妨令$u$为当前结点，$v$为其子结点。先预处理出每个结点的子树大小$s[u]=1+\sum s[v]$和以$1$为根结点时所有结点的深度（${\text{depth}}_i$），此时第一遍DFS即为预处理。

令$f_u$表示以$u$为根时，所有结点的总深度和，则$f_1=\sum {\text{depth}}_i$。
考虑$f_u\to f_v$的转移，即“根结点从$u$变成$v$时所有结点深度和的变化”，则有：

• 所有在$v$的子树上的结点深度全部$-1$，则总深度和减少$s_v$；
• 所有不在$v$的子树上的结点深度都$+1$，则总深度和增加$n-s_v$；

此时，可得$f_v=f_u-s_v+n-s_v=f_u+n-2s_v$。注意数据类型，使用long long。

#include <cstdio>
#include <vector>
#define maxn 1000005
using namespace std;using LL = long long;vector<int> G[maxn];
LL sz[maxn], f[maxn];
int n, ans;LL dfs1(int v, int d, int par)
{sz[v] = 1;LL s = d;for(int u: G[v])if(u != par)s += dfs1(u, d + 1, v), sz[v] += sz[u];return s;
}void dfs2(int v, int par)
{if(f[v] > f[ans]) ans = v;for(int u: G[v])if(u != par){f[u] = f[v] + n - (sz[u] << 1LL);dfs2(u, v);}
}int main()
{scanf("%d", &n);for(int t=n; --t; ){int u, v;scanf("%d%d", &u, &v);G[--u].push_back(--v);G[v].push_back(u);}f[0] = dfs1(0, 0, -1);dfs2(0, -1);printf("%d\n", ++ans);return 0;
}