前言

没有发现 dsu on tree 题解，虽然复杂度不是很好不过胜在好想，来写一篇。

思路

首先考虑枚举一条边，则已经有一个联通块大小可以确定，那么剩下两个联通块大小尽量平均时最优。

两条边有祖孙关系是好搞的，直接 dfs 时把从根到当前节点的所有子树大小扔进 multiset 里并二分，回溯时 erase 掉即可。

两条边没有祖孙关系时，若当前遍历到节点 uu，那么此时 multiset 中应当包括除了根到 uu 和 uu 子树里的所有节点的子树大小 szvsz_v。如果一开始将所有点的子树大小全部插入，则有一个 O(n2log⁡n)\mathcal{O}(n^2 \log n) 的暴力算法，即遍历到每个点都直接将子树里的所有值清空，然后再统计答案。

考虑使用 dsu on tree，计算重儿子答案时不还原 multiset 里的值，这样遍历到每个点时只需要暴力清空轻儿子的值就可以计算答案。

复杂度 O(nlog⁡2n)\mathcal{O}(n\log ^2n)，两个 log⁡\log 分别来自 dsu on tree 和 multiset。