![【BZOJ3302】[Shoi2005]树的双中心【DFS】【TreeDP】](/uploads/reation/bcimg10.png)
【BZOJ3302】[Shoi2005]树的双中心【DFS】【TreeDP】
【题目链接】考虑暴力做法，我们可以枚举删掉某条边，然后在两个子树里找重心，统计答案即可，O(n^2)的。发现树高最多100，并且发现每次转移只可能向着权值和更大的地方移动，那么我们可以记录出每个节点权值和最大的儿子。但是如果删掉一条边的时候，把这个儿子给归到另一个子树里了，所以我们还得记录次大权值和的儿子。复杂度O(nh)。设sum[x]表示x的子树中的权值和。设res
