做完之后真的有一种 艹这么简单嘚题为什么我考场上没想出来 的感觉
当时在考场上已经被两个计数题的dp洗脑了于是对着这道题推了半天的dp，最后写了个奇怪的记忆化搜索+一条链然而写一条链的时候可能也只有我这种菜逼没看见题目里说1不一定是链的端点了。。最后就只拿了45分
我要是能花时间好好想想一条链怎么做这题就切了。因为一条链的情况实在是离正解很近很近

一条链的做法：1号点至多两个分支，给每个分支开个堆每次從两个堆里各弹一个值出来，取大的那个加入答案即可
那么显然这个做法可以扩展到树上：给每个节点都开个堆，dfs的时候合并子树的堆即可好像有大佬写左偏树写挂了，事实上这题只要启发式合并就行了