#P6729. [WC2020] 有根树

[WC2020] 有根树

题目描述

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

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

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

输入格式

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

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

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

接下来 qq 行,每行两个数 t,vt,v 表示一次操作。若 t=1t=1 则该操作为将结点 vv 加入 SS,保证操作前 vSv \notin S。若 t=2t=2 则该操作为将结点 vvSS 中删去,保证操作前 vSv\in S。 初始时 SS 为空集。

输出格式

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

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

提示

样例解释

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

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

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

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

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

数据范围

对于所有测试点:1n5×1051\le n\le 5\times 10^51q1061\le q\le 10^61x,y,vn1\le x,y,v\le nt{1,2}t\in \{1,2\}

测试点编号 nn\leq qq\leq 特殊限制
121\sim 2 100100 500500
343\sim 4 2×1042\times 10^4
565\sim 6 10510^5 2×1052\times 10^5 A
787\sim 8 2×1052\times 10^5 4×1054\times 10^5 B
9119\sim 11 C
121612\sim 16
172017\sim 20 5×1055\times 10^5 10610^6

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

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

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

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