abc337g 题解

abc337g 思路 固定 $w$，将树分为子树内外两部分，分别考虑子树内到子树外，子树外到子树内，两个儿子之间的贡献。 需要支持查询 $u$ 子树内比 $u$ 大的数的个数，做子树加。后半部分可以 dfn 序上线段树区间加，前面部分没想到从小到大加入 $w$，直接用权值线段树合并。复杂度 $O(n
posted @ 2024-05-08 18:14  yhddd  阅读(2)  评论(0)  编辑  收藏  举报