首先你得看了题和题解至少算法二之前的部分。
题解地址:http://vfleaking.blog.uoj.ac/blog/2292
我们把每个询问转化为总和减去大于等于最大权值的部分的后缀和。
接着我们按w从大到小加入点,考虑维护每个点的子树中的最小深度。
这个怎么维护呢,考虑一个点肯定是更新它到根的路径,所以我们用类似LCT的access的方法更新,我们可以保证随时每个链的最小深度都相同,如果当前的链的最小深度小于用来更新的值就直接退出,否则的话我们就更新,最后再把这些更新了的链连起来。
复杂度显然是$O((n + m)\log{n})$的,用类似证明LCT复杂度的方法证明即可。
答案也很好算,记录一个后缀和即可,你会发现更新的时候也很好打标记,询问也很好处理。
怎样,是不是只要有模板就好写又好调?而且时间效率还不错呢。