华为题库已更新至:华为实习&秋招真题题库，请移步。

思路

这道题是洛谷P1352-没有上司的舞会一题的改版.具体做法是树形$DP$.

动态规划题目重点有两个:状态定义,状态转移.

状态定义

我们记$dp[u][0/1]$为当前以$u$为根节点的子树的最高维护成本,其中第二维度为0表示$u$根节点也被撤销,为1表示$u$根节点未被撤销.