CF1856E1 题解

· · 个人记录

赛时没过真的遗憾。

大概错的原因是 dp 转移写挂了。

Sol

设 dp_u 为以 u 为根的子树的答案。

考虑当前为 x，那么如何合并 x 的子树的答案。

显然先把所有子树答案加起来，然后，不同子树节点的 lca 一定是 x。

应该将 x 的所有子树划分成两个部分（注意不能分割子树)，使得两个部分的大小乘积最大。

树上背包就能解决。

Submission