标签 - 点分树

? 解题记录 ? ? 洛谷 ? ? 点分治 ? ? 点分树 ? ? 堆 ?    2018-05-26 22:06:41    505    0    0
题目描述给出一棵边带权的节点数量为n的树,初始树上所有节点都是白色。有两种操作: C x,改变节点x的颜色,即白变黑,黑变白 A,询问树中最远的两个白色节点的距离,这两个白色节点可以重合(此时距离为0)。 输入输出格式输入格式:  In the first line there is an integer N (N <= 100000) In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a,
? 解题记录 ? ? 洛谷 ? ? 点分治 ? ? 点分树 ? ? 堆 ?    2018-05-26 21:49:01    557    0    0
题目描述Jiajia和Wind是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋子都互相可达。 游戏是这样进行的,孩子们负责躲藏,Jiajia负责找,而Wind负责操纵这N个屋子的灯。在起初的时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,但是为了增加刺激性,孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性,Jiajia希望知道可能的最远的两个孩子的距离(即最远的两个关灯房间的距离)。 我们将以如下形