TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4065
  • 题目
  • P4065【ZJOI2007】Hide 捉迷藏
    限制 : 时间限制 : - MS   空间限制 : 256000 KB
    问题描述

    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。

    样例输入 1

    8
    1 2
    2 3
    3 4
    3 5
    3 6
    6 7
    6 8
    7
    G
    C 1
    G
    C 2
    G
    C 1
    G

    样例输出 1

    4
    3
    3
    4

    样例输入 2

    9
    1 2
    2 3
    2 4
    2 5
    1 6
    6 7
    7 8
    7 9
    15
    G
    C 1
    G
    C 2
    G
    C 3
    G
    C 4
    G
    C 5
    G
    C 1
    G
    C 3
    G

    样例输出 2

    5
    5
    5
    5
    2
    3
    5

    提示

    对于100%的数据, N ≤100000, M ≤500000。


    来源  感谢1879570236低声下气地讨要数据并搬运