3445. [CTSC 2020]有根树

【题目描述】

给定一棵包含n个结点的有根树，结点从1~n编号，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表示结点数。

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

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

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

初始时S为空集

【输出格式】

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

【样例输入】

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

【提示】

样例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。

【来源】

在此键入。