本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-06 10:28:11

赛时没过真的遗憾。

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

Sol

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

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

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

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

树上背包就能解决。

Submission