UOJ Logo Universal Online Judge

UOJ

#545. 【WC2020】有根树

附件下载 统计

给定一棵包含 $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 \not \in S$。若 $t=2$ 则该操作为将结点 $v$ 从 $S$ 中删去,保证操作前 $v\in S$。

初始时 $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

见附加文件。

数据范围

对于所有测试点:$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 \le$$q \le$特殊限制
$1 \sim 2$$100$$500$
$3 \sim 4$$2 \times 10^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$。

时间限制: $5\texttt{s}$

空间限制: $512\texttt{MB}$

附加文件

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