从一道美团春招笔试题目出发，揭开树 DP 的神秘面纱

我们先上题

给定一棵树，每一个节点有一个权重，选择其中某些节点，满足被选中的节点两两不相邻，求在所有的选择方案中，最大化被选择节点权值之和的情况下，被选择节点权值最小值尽可能大。(白话一点说就是，优先保证选择的节点权值和最大；如果有多个和最大的情况，要优先选择选中的节点中最小的值是最大的。比如和最大是 10，你可以选择 1 9，也可以选择 2 8，这种时候要优先选择 2 8，因为 2 要比 1 大)。

树是一种无向联通图，任意节点两两可达且无环。

输入

第一行两个整数 N 和 M，分别表示树的节点数和边数\

第二行为 N 个整数，分别表示每个节点的权重\

接下来 M 行，每行两个整数 a 和 b，存在一条从 a 到 b 的边。

输出

输出两个整数，表示能选择的最大权值之和是多少，以及权值最小值是多少，用空格分割。

输入样例

5 4

3 4 1 4 9

1 2

1 3

2 4

3 5

输出样例

16 3

解释

可以证明，当选择 1，4，5 号节点的时候，有最大权值之和 16，最小权值为 1 号节点的 3，此时为最优解。

分割线，如果看完题知道怎么解了，后面的内容可以跳过了，恭喜～

题外话

怎么评价这个题呢，我觉着所有的考生可以分为两种，第一种是会树 DP 的，一看这个题：呀呵，这不是树 DP 么；第二种是不会树 DP 的，冥思苦想苦苦不知道怎么求。但其实我感觉，树形 DP 在广大的 DP 家族里面是属于比较简单的一种。

其实从最近几年的面试/笔试经验来看，树 DP 出现的频率可不低了。当年面试字节的时候就有被面试官问到类似的题；前几天跟一个同学聊的时候发现他也被问了一个树 DP，他可是没有竞赛经历啊。。可怕。

树 DP 解释

树 DP，也就是在树上进行的 DP。因为树固有的递归属性，所以树 DP 一般都是递归进行的。

我们这里就不详细介绍关于动态规划和树的基础知识了。

简而言之，动态规划背后的基本思想非常简单，大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解；而树的一些特点和性质有：

• 有 n 个节点，n-1 条边无向图，任意两个顶点可以互相到达

• 任意两个顶点之间有且只有一条路

• 一个点至多有一个父亲节点，但是可以有多个儿子节点

• 没有环

拿到一个树 DP 问题，我们可以按照以下的三步去解决。

1. 判断是否是一个树 DP 问题。首先判断是否是一个树，然后是否符合动态规划要求，也就是去判断父亲节点和儿子节点是否存在阶段性的关联关系。

2. 建树。通过数据量和题目要求，选择合适的建树的方式。

3. 写状态转移方程。通过观察孩子和父亲之间的关系建立方程。通常树形 DP 的写法有两种：

- 根到叶子: 不过这种动态规划在实际的问题中运用的不多。我们也会给出一个例子。

- 叶子到根: 既根的子节点传递有用的信息给根，然后从根得出最优解的过程。这类的习题比较的多。

到这步的时候面鲸提示可以用一套框架来解决，其核心在于根据转移方程需更新

func dfs(root)：  对于root的每一个节点son，循环执行    dfs(son) // 递归处理son子树    根据转移方程动态更新

一个简单的例子

某大学有 N 个职员，编号为 1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $a_i$，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

按照刚才的判断，首先这是一个树(题目中明说了)，其次满足动态规划的要求，知道了某个子树的解之后，可以递归的向上得到父节点所在子树的解。

我们令 $f(i,1/0)$表示以 $i$为根的子树的最优解(最大的快乐指数)，第二维的 0 表示 $i$不参加误会，1 表示 $i$参加舞会。

我们可以很简单的推出两个状态转移方程(j 是 i 的儿子节点):

• $f(i,0)=\sum max(f(j,0),f(j,1))$（上司不参加舞会时，下属可以参加，也可以不参加）

• $f(i,1)=\sum f(j,0)+a_i$（上司参加舞会时，下属都不参加，快乐值+ $a_i$）

套用到我们上面提到的套框架里面去，可以很容易写出代码。

void dfs(int x) {
  for (auto& v: Edge[x]) {
    dfs(v);
    f[x][0] += max(f[v][0], f[v][1]);
    f[x][1] += f[v][0];
  }
  f[x][1] += a[xx];
}

如果到这里还没有问题的话，我们可以继续往下走～

回到这个题

再回到这个题，其实可以发现美团这个题只是在原来这个题的基础上加了一个限制：要求在选择权值最大的情况下，被选择节点权值的最小值尽可能大。

我们需要另外一个数组来记录下，当选择或者不选择这个节点的时候，这个子树中节点的最小值是多少。尤其要注意当某个时刻，有多种选择的时候，要尽量去选择最小值较大的那个。

```c++void dfs(int u) {    vis[u] = true;    for (auto& v : Edge[u]) {        if (vis[v]) continue;        // 递归处理儿子节点        dfs(v);                // 先考虑这个节点不放的情况        // 如果某个儿子节点“不放”要比“放”收益大        if (f[v][0] > f[v][1]) {            f[u][0] += f[v][0];            // 同时更新这个子树的最小值            d[u][0] = min(d[u][0], d[v][0]);        } else if (f[v][0] < f[v][1]) {            f[u][0] += f[v][1];            d[u][0] = min(d[u][0], d[v][1]);        } else {            // 如果儿子节点放或者不放收益相同，            // 那么我们要选择那个使得权值最小值较大的那个去更新父节点            f[u][0] += f[v][1];            d[u][0] = min(d[u][0], max(d[v][1], d[v][0]));        }        // 再考虑这个节点放的情况        f[u][1] += f[v][0];        d[u][1] = min(d[v][0], d[u][1]);    }    // 这个节点要放了，当然要加上这个节点的数量    f[u][1] += a[u];    // 同时更新这个节点放的情况下，子树的最小值    d[u][1] = min(d[u][1], a[u]);}

至此，美团这个题就结束了～关于树形 DP，不知道你是否有一些自己的理解了呢。完整代码可在面鲸公众号后台回复“树 DP”获得。

总结

至此，我们总结一下～

• 怎么判断是不是树 DP 题目：先看是不是一个树上的问题，然后去判断是否满足动态规划的性质，也就是去判断父亲节点和儿子节点是否存在阶段性的关联关系。

• 怎么解树 DP 题目：一般都是 dfs 去做，慢慢的从儿子节点的状态更新到父亲节点。可以尝试利用下面这个模版。

  func dfs(root)：    对于root的每一个节点son，循环执行      dfs(son) // 递归处理son子树      根据转移方程动态更新

放一道类似的题目，leetcode 337，赶紧去切吧。：）