Description

风见幽香有一个好朋友叫八云紫,她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动,打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦,但是她们也发现她们面临着一个问题,那就是店开在哪里,面向什么样的人群。

很神奇的是,幻想乡的地图是一个树形结构,幻想乡一共有 n 个地方,编号为 1 到 n,被 n-1 条带权的边连接起来。每个地方都住着一个妖怪,其中第 i 个地方的妖怪年龄是 $x_i$​。妖怪都是些比较喜欢安静的家伙,所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 3。妖怪和人一样,兴趣点随着年龄的变化自然就会变化,比如我们的 18 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现,基本上妖怪的兴趣只跟年龄有关,所以幽香打算选择一个地方 u(u 为编号),然后在 u 开一家面向年龄在 L 到 R 之间(即年龄大于等于 L、小于等于 R)的妖怪的店。也有可能 u 这个地方离这些妖怪比较远,于是幽香就想要知道所有年龄在 L 到 R 之间的妖怪,到点 u 的距离的和是多少(妖怪到 u 的距离是该妖怪所在地方到 u 的路径上的边的权之和) ,幽香把这个称为这个开店方案的方便值。

幽香她们还没有决定要把店开在哪里,八云紫倒是准备了很多方案,于是幽香想要知道,对于每个方案,方便值是多少呢。

Simplified Description

给你一棵 $n$ 个点树,每个点都有一个权值。 有 $m$ 次询问,每次询问给你一个点,问这个点到所有权值在 $L$ 到 $R$ 之间 的点的距离和为多少。强制在线。

Idea

先将答案差分,考虑权值在 $[1,r]$ 内点到给定点的距离之和,可以用如下式子表示

$$\sum_{i=1}^r (dep_u+dep_i-2\times dep_{lca})=\sum_{i=1}^r dep_i+dep_u\times r+\sum dep_{lca}$$

发现除了 $\sum dep_{lca}$ 都挺好求的。

这时我们可以将点按照权值排序,然后依次插入。插入后它会给每个节点造成它自己深度的贡献,用树链剖分套线段树的区间操作即可。

因为我们需要询问在一段区间内的答案,因此需要将线段树可持久化。此时我们换用带修主席树维护。

时间复杂度 $\Theta(n\log^2n)$。

Code