1901E
CF1901E Compressed Tree 题解
原题链接:CF1901E,树形 dp + 神奇分类讨论。 很容易想到树形 dp。难点在于如何转移以及统计答案,需要大量分讨。 父亲(及其以上)和自己组成连通块,不缩。(只保留自己并且往上传递) 连通块中只有自己一个(记录答案) 一个儿子和自己组成连通块,且自己作为根节点,不和父亲收缩(记录答案) 一 ......
CF1901E Compressed Tree(树dp)
Problem 题目地址 Solution 来自fcy大佬的思路 记 \(f_u\) 表示假定以 \(u\) 为根的子树,在压缩后,(子树内的某一个点(包括 \(u\)))可以向外(除\(u\)为根的子树外所以点的集合)连一条边时的最大 \(sum\)。换言之,我们把树拆成 以\(u\)为根的子树( ......