#3329. 「WC2020」有根树

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

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

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

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

输入格式

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

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

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

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

输出格式

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

样例

样例输入 1

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

样例输出 1

1
1
1
2
1

样例解释 1

第一次操作后 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=1,b=1

样例 2

见附加文件中的 tree2.intree2.ans

样例 3

见附加文件中的 tree3.intree3.ans

数据范围与提示

对于所有测试点: 1\le n\le 5\times 10^5 1\le q\le 10^6 1\le x,y,v\le n t\in \{1,2\}

测试点编号 n\leq q\leq 特殊限制
1\sim 2 100 500
3\sim 4 2\times 10^4
5\sim 6 10^5 2\times 10^5 A
7\sim 8 2\times 10^5 4\times 10^5 B
9\sim 11 C
12\sim 16
17\sim 20 5\times 10^5 10^6

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

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

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

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