CF1120D Power Tree（树形DP/构造+差分+最小生成树）_ads power tree

作者：花生_TL007 | 2024-02-06 21:37:12

踩

ads power tree

解法一：树形DP

个人觉得这个方法是比较可能想到的，但是输出方案很恶心

先转换题意：“无论怎样规定叶子的初始点权，都可以通过操作你选择的点来让所有叶子的点权清空”意味着每个叶子节点都可以通过一系列操作单独+1、-1

模拟一下就可以发现，以u为根的子树中，

要想通过控制 $u$ 或 $u$ 的祖先（不管是 $u$ 还是 $u$ 的祖先都同时覆盖了子树内的所有叶子节点）
使子树内所有叶子节点均可以单独+1、-1，

至多一个叶子节点未被覆盖，

且被覆盖的叶子节点一定要可以单独+1、-1

那么状态定义就很显然了：

$f [u] [0]$ 表示以 $u$ 为根的子树内叶结点全部被覆盖，

$f [u] [1]$ 表示以

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/64654