AC. 梦想

frank_c1

[BZOJ 1095] 捉迷藏

发布于2016年03月23日 | 暂无评论 | 559阅读 | 树分治

题目描述

捉迷藏 Jiajia和Wind是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的,孩子们负责躲藏,Jiajia负责找,而Wind负责操纵这N个屋子的灯。在起初的时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,但是为了增加刺激性,孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性,Jiajia希望知道可能的最远的两个孩子的距离(即最远的两个关灯房间的距离)。 我们将以如下形式定义每一种操作: C(hange) i 改变第i个房间的照明状态,若原来打开,则关闭;若原来关闭,则打开。 G(ame) 开始一次游戏,查询最远的两个关灯房间的距离。

输入格式

第一行包含一个整数N,表示房间的个数,房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b,表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q,表示操作次数。接着Q行,每行一个操作,如上文所示。

输出格式

对于每一个操作Game,输出一个非负整数到hide.out,表示最远的两个关灯房间的距离。若只有一个房间是关着灯的,输出0;若所有房间的灯都开着,输出-1。

题目解析

这种动态点分治的题目真是考验代码能力。很久以前就想做,然而智商不足并想不出来……

昨天听了余姚中学李昊神犇在ZJOI上的讲课,感觉很有启发,突然就明白这道题的搞法了。先对树分治,可以采用基于点的分治。对于每个分治结构,维护两个堆。对于分治点x,建一个堆C(x)维护各子分治树T_i(x)x的最远白点距离,具体可以对于子分治树T_i(x)建一个堆B(T_i(x)),维护该树中所有白点到x的距离,那么B(T_i(x))的堆顶就保存在C(x)中。再建一个全局的答案堆A,对于分治点x,保存C(x)中最大和次大的元素之和到A

对于每次修改,若x开灯,则在与x有关的分治树的堆中删除x到分治树根的距离;若x关灯,则在与x有关的分治树的堆中添加x到分治树根的距离。如果对堆B的会影响到堆C,A,那就在相关堆中修改元素即可。

一开始没有想通堆怎么支持修改操作,后来终于想到。首先,修改等价于删除原值和插入新值。对于删除操作,我们另建一个堆del保存待删除的值,如果当前堆顶和del堆顶相同,那我们就将两个堆顶都弹出,表示执行存下来的删除操作。

这道题还有一些其他的细节需要耐心处理。