「nowcoder 271D」风斩冰华-DP+贪心

发布于 11 天前  24 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「nowcoder 271D」风斩冰华-DP+贪心

Description

咕咕咕。

Solution

设$f_{i,0,1,2}$分别表示以$u$为根的子树中$u$没有删除,在其父亲之前删除,再其父亲之后删除的答案。

$f_{u,0}$很好求。

$$f_{u,0}=\sum max(f_{v,0},f_{v,2})$$

$f_{u,1}$与$f_{u,2}$有点麻烦。要把儿子节点分为再$u$之后删除/保留以及再$u$之前删考虑。

  • 在$u$之后删的贡献$max(f[v][0],f[v][1])$
  • 在$u$之前删的贡献$f[v][1]$

设$v'$为在$u$之后删除的儿子,所以答案为$\sum f_{v,1}+(\sum max(f_{v',0},f_{v',2})-f_{v',1})$

所以在满足度数要求的情况下贪心即可。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「nowcoder 271D」风斩冰华-DP+贪心


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前, 相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!