题目内容

塔子哥有一题$n$个节点的树，树中每一条边都有一个权值，多多还有一个长度为$n$的正整数序列:$v_1,v_2,...,v_n$

删除树中若干条边之后(或者不删)，就会变成一个有$x$个连通块的图，此时的得分为：剩余边权和$+v_i$（两个可以互相到达的节点属于同一个连通块，注意一个孤点也是一个连通块）

塔子哥可以删除图中若干条边（可以不删）。现在塔子哥想知道，最多能够得到多少分。现在请你告诉塔子哥答案。

思路：贪心

一个点可以为一个连通块，每连接两个点，都会由两个连通块合并为一个连通块。

如果最开始将所有边都删除，则得到$n$个连通块，此时答案即为$v[n]$。之后每连接一条边，则连通块减少一个，要让得分最大，就需要连接最大的边。

对边进行排序后，从大到小扫描边并逆序更新答案即可。