ID: 314

Difficulty: 8

No testdata at current.

思路

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

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

状态定义

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

In following contests:

秋招模拟赛第28场|华为春招实习|2023.05.24