UOJ Logo Universal Online Judge

UOJ

#545. 【WC2020】有根树

附件下载 统计

给定一棵包含 n 个结点的有根树,结点从 1n 编号,1 号点为根结点。小明有一个结点集合 S,对于 S 中的结点 u,他定义 wu 的值为 u 的子树中(包括 u 本身)被包含在集合 S 内的结点数,为了方便叙述,对于不在 S 中的结点,我们认为其 wu=0

接下来,小明需要你选择一个包含根结点的连通块 C。记 a 表示连通块 C 中被包含在集合 S 内的结点数,b 表示不在连通块 C 中的结点的 w 值最大值,若不存在不在 C 中的结点,则 b=0,小明希望你能最小化 max(a,b)

小明觉得这个问题还比较简单,所以还给出了 q 次操作,每次会令集合 S 加入或删除一个结点,请你对每次操作后的集合 S 给出 max(a,b) 的最小值。

输入格式

第一行一个正整数 n 表示结点数。

接下来 n1 行,每行两个整数 x,y,表示树上的一条边 (x,y)

接下来一行一个正整数 q 表示操作数。

接下来 q 行,每行两个数 t,v 表示一次操作。若 t=1 则该操作为将结点 v 加入 S,保证操作前 vS。若 t=2 则该操作为将结点 vS 中删去,保证操作前 vS

初始时 S 为空集。

输出格式

每次操作后,输出一行一个整数表示答案。

样例1

input

5
1 2
1 3
1 4
2 5
5
1 4
1 1
1 2
1 5
2 2

output

1
1
1
2
1

explanation

第一次操作后 S={4},一个选择方案为 C={1},此时 a=0,b=1

第二次操作后 S={1,4},一个选择方案为 C={1},此时 a=1,b=1

第三次操作后 S={1,2,4},一个选择方案为 C={1},此时 a=1,b=1

第四次操作后 S={1,2,4,5},一个选择方案为 C={1,2},此时 a=2,b=1

第五次操作后 S={1,4,5},一个选择方案为 C={1},此时 a=0,b=1

样例2

见附加文件。

样例3

见附加文件。

数据范围

对于所有测试点:1n5×1051q106,1x,y,vn,t{1,2}

测试点编号nq特殊限制
12100500
342×1042×104
561052×105A
782×1054×105B
911C
1216
17205×105106

表格中特殊限制一栏符号的含义为:

A:任意时刻集合 S 的大小不超过 50

B:树的形态是一条链且 1 号结点度数为 1

C:树上每个结点的双亲结点编号小于它本身,n=q 且第 i 次操作为将 i 号点加入 S

时间限制: 5s

空间限制: 512MB

附加文件

考虑到评测机性能差异,时间限制放宽一秒。求不虐萌萌哒评测机。