[bzoj3252]-[SCOI2017]攻略

真没想到去年SCOI出原题…..

(所以标题我自己加了个SCOI2017上去233)

题目(BZOJ)

 

这题其实很好做…..

亏我一开始把网络流建图给想出来了233

然后又去思考了一下树剖,LCT,dfs序啥的…

发现这题根本不需要这么麻烦,只需要做一次长链树剖(每次沿链最长的点,平常的树剖是沿子树大小最大的点)就行了,因为剖下来的每条链的末尾一定是叶子结点并且不会出现重叠情况,所以将每条链的总权值从大到小排序,选前k个就行了(我用的vector)