P1352题解

题目大意

有 \(n\) 个人，每个人有一个上司，当他不和他的上司一起跳舞时，他会有一个快乐值，求当一些人一起跳舞时，所有人的快乐值总和最大值。

分析

且给出的关系一定是一棵树。

题面中的这个信息可以让我们知道这是一道树形dp的模板题，每个人的上司就是这个人的父节点。

树形dp

基本思路

我们用 dp[i][0] 表示不选该节点时的最大快乐值， 用 dp[i][1] 表示选该节点时的最大快乐值，用mc[i]表示该人的快乐值。

可以得到以下式子：

\[ dp[i][0]= \sum _{j是i的子节点} \max (dp[j][0],dp[j][1])~~~ \\ dp[i][1]= mc[i] + \sum _{j是i的子节点} dp[j][0]~~~ \]

这就是树形dp的基本实现。

选根

和一般的树形dp题目不一样，这道题不是从每一个节点开始遍历都可以得到答案，需要找没有父节点（没有上司）的节点开始遍历。

模板题，就不给出代码了。

这个思路可以过此题，如果本文有错误或不妥之处，请在下方留言。