[BZOJ3572/Luogu3233][HNOI2014]世界树(虚树,树型动态规划)

发布于 2018-05-27  292 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3572/Luogu3233][HNOI2014]世界树(虚树,树型动态规划)

Description

世界树是一棵无比巨大的树,它伸出的枝干构成了整个世界。在这里,生存着各种各样的种族和生灵,他们共同信奉着绝对公正公平的女神艾莉森,在他们的信条里,公平是使世界树能够生生不息、持续运转的根本基石。
世界树的形态可以用一个数学模型来描述:世界树中有n个种族,种族的编号分别从1到n,分别生活在编号为1到n的聚居地上,种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连,道路的长度为1。保证连接的方式会形成一棵树结构,即所有的聚居地之间可以互相到达,并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度;例如,若聚居地a和b之间有道路,b和c之间有道路,因为每条道路长度为1而且又不可能出现环,所卧a与c之间的距离为2。
出于对公平的考虑,第i年,世界树的国王需要授权m[i]个种族的聚居地为临时议事处。对于某个种族x(x为种族的编号),如果距离该种族最近的临时议事处为y(y为议事处所在聚居地的编号),则种族x将接受y议事处的管辖(如果有多个临时议事处到该聚居地的距离一样,则y为其中编号最小的临时议事处)。
现在国王想知道,在q年的时间里,每一年完成授权后,当年每个临时议事处将会管理多少个种族(议事处所在的聚居地也将接受该议事处管理)。 现在这个任务交给了以智慧著称的灵长类的你:程序猿。请帮国王完成这个任务吧。

Tag

虚树,树型动态规划

解决思路

首先对于每一个询问建立出虚树。对于在虚树中的点,我们可以比较方便地求出距离每一个点最近的议事处的位置。那么对于不在虚树中的点,它一定能连接到虚树上的点或虚树上的边。
对于虚树上的每一对边,如果边两边的点被管辖的点相同,那么这整个一条边上的点都是如此。反之,我们可以倍增地找到一个中间点,使得这个点以下的部分与下端点同,以上的部分与上端点同。
当然,由于建立出虚树后有一些点已经在虚树中统计过了,所以另外还要考虑去重的问题。可以用一个$sum$数组来统计,表示虚树上的贡献,开始的时候置为$size$,然后每计算一部分就从中减掉,最后再把虚树上的贡献统计到答案中。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3572/Luogu3233][HNOI2014]世界树(虚树,树型动态规划)


HNCJ OIer