树形 DP

参考资料

树形 DP 在树上做动态规划，通常设 $f_u$ 表示以 $u$ 为根的子树的某种最优值，自底向上由各子节点的状态合并而来，用一遍 DFS 实现。

以「没有上司的舞会」为例： $f_{u,0}$ 、 $f_{u,1}$ 分别表示不选、选节点 $u$ 时子树的最大权值。选 $u$ 则子节点都不能选，不选 $u$ 则子节点选或不选取较大者。

106 Bcpp
void dfs(int u)
{
	for(auto v:G[u])
	{
		dfs(v);
		f[u][0]+=max(f[v][0],f[v][1]);
		f[u][1]+=f[v][0];
	}
}

某大学有 $n$ 个职员，编号为 $1\dots n$ 。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$ ，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

请计算邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

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

一个结点的深度之定义为该节点到根的简单路径上边的数量。