[BZOJ3991/Luogu3320][SDOI2015]寻宝游戏(dfs序)

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


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

本文链接地址:[BZOJ3991/Luogu3320][SDOI2015]寻宝游戏(dfs序)

Description

小B最近正在玩一个寻宝游戏,这个游戏的地图中有N个村庄和N-1条道路,并且任何两个村庄之间有且仅有一条路径可达。游戏开始时,玩家可以任意选择一个村庄,瞬间转移到这个村庄,然后可以任意在地图的道路上行走,若走到某个村庄中有宝物,则视为找到该村庄内的宝物,直到找到所有宝物并返回到最初转移到的村庄为止。小B希望评测一下这个游戏的难度,因此他需要知道玩家找到所有宝物需要行走的最短路程。但是这个游戏中宝物经常变化,有时某个村庄中会突然出现宝物,有时某个村庄内的宝物会突然消失,因此小B需要不断地更新数据,但是小B太懒了,不愿意自己计算,因此他向你求助。为了简化问题,我们认为最开始时所有村庄内均没有宝物

Tag

dfs序

解决思路

题目中并没有限制询问点数之和,所以不能用虚树做呢。
但是,询问有一个良好的性质,即每一次最多只会动一个点。考虑询问的内容,我们发现,只要从任意一个关键点出发,每次均走到没有经过$dfn$序最近的的一个关键点,最后再返回来即可。
所以用$set$以$dfn$序维护一个点的集合,每一次加入或删除的时候讨论一下,维护答案。
注意当集合中元素个数小于等于$2$个和插入元素为头或尾的时候的特殊处理。

代码

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

本文链接地址:[BZOJ3991/Luogu3320][SDOI2015]寻宝游戏(dfs序)


HNCJ OIer