[BZOJ4012/Luogu3241][HNOI2015]开店(树链剖分,主席树)

发布于 2018-01-28  8 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4012/Luogu3241][HNOI2015]开店(树链剖分,主席树)

Description

风见幽香有一个好朋友叫八云紫,她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动,打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦,但是她们也发现她们面临着一个问题,那就是店开在哪里,面向什么样的人群。很神奇的是,幻想乡的地图是一个树形结构,幻想乡一共有 n个地方,编号为 1 到 n,被 n-1 条带权的边连接起来。每个地方都住着一个妖怪,其中第 i 个地方的妖怪年龄是 x_i。妖怪都是些比较喜欢安静的家伙,所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 3。妖怪和人一样,兴趣点随着年龄的变化自然就会变化,比如我们的 18 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现,基本上妖怪的兴趣只跟年龄有关,所以幽香打算选择一个地方 u(u为编号),然后在 u开一家面向年龄在 L到R 之间(即年龄大于等于 L、小于等于 R)的妖怪的店。也有可能 u这个地方离这些妖怪比较远,于是幽香就想要知道所有年龄在 L 到 R 之间的妖怪,到点 u 的距离的和是多少(妖怪到 u 的距离是该妖怪所在地方到 u 的路径上的边的权之和) ,幽香把这个称为这个开店方案的方便值。幽香她们还没有决定要把店开在哪里,八云紫倒是准备了很多方案,于是幽香想要知道,对于每个方案,方便值是多少呢。

Http

BZOJ
Luogu

Tag

树链剖分,主席树

解决思路

先不考虑年龄的限制,考虑其它点\(x\)到一个指定点\(u\)的距离,设\(dis[i]\)表示点\(i\)到根(默认是\(1\))的距离,那么就是\(\sum dis[u]+dis[x]-2*dis[lca(u,x)]\),这个式子的前两项都比较好处理,一个直接用\(dis[u]\)乘以点数,另一个可以用前缀和维护,那么关键是\(dis[lca(u,x)]\)这一项怎么求。
这个的求法可以参考这一道题,类似的,我们用树链剖分+线段树的方法,对点\(x\)到根的路径的边都+1,这样查询\(u\)到根的路径和就可以得到\(dis[lca(u,x)]\)了。
最后把年龄的限制加上去,我们把妖怪按照年龄排序后,以此以树链剖分的形式插入主席树,这样就可以实现对年龄区间的查询。注意要标记永久化。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4012/Luogu3241][HNOI2015]开店(树链剖分,主席树)


HNCJ OIer 一枚