#P12239. [2024年联测]选拔赛

    ID: 11388 传统题 3000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>数据结构树算法树链剖分CF2600线段树堆模拟构造

[2024年联测]选拔赛

选拔赛(ctt)

题目描述

你要给 CTT D3T3 写一个交互库,因此你需要解决下面这个问题:

有一棵 nn 个点的树和一个点集 SS。初始时 SS 为空,而你需要维护两种操作:

  • “1 x” 向 SS 中加入一个点。
  • “2 x” 从 SS 中删除一个点。

每次操作之后,你需要在 SS 形成的导出子图(一条边在导出子图内,当且仅当其两端点在 SS 内)中找出最大的连通块,并输出它的大小(点数)。

由于你要写的是交互库,所以这题强制在线。

输入格式

从标准输入读入数据。

第一行输入3个数 n,m,typen,m,type 表示点数和操作数,以及是否强制在线。

接下来 n−1n-1 行每行两个数 u,vu,v,表示有一条边连接点 uu 和点 vv。

接下来 mm 行,每行两个整数表示操作。

如果这不是第一次操作,则你需要在输入 xx 之后,把 xx 对 lastans×typelastans\times type 按位异或后,才能得到真正的 xx。其中 lastanslastans 表示上次询问的答案。

输出格式

输出到标准输出。

在每次操作之后,输出一行表示答案。

样例 1

输入

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

输出

1
1
3
2
3

样例 2

输入

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

输出

1
1
3
2
3

数据范围

对于所有数据,0≤type≤10\le type\le1,1≤n≤2×1051\le n\le2\times10^5,1≤m≤5×1051\le m\le5\times10^5。

试点编号 n≤n\le m≤m\le 特殊性质
1∼41\sim4 10001000 无
5∼85\sim8 2×1052\times10^5 5×1055\times10^5 A
9∼129\sim12 B
13∼1613\sim16 10510^5 2×1052\times10^5 无
17∼2017\sim20 2×1052\times10^5 5×1055\times10^5

特殊性质 A:对于每条边 (u,v)(u,v),存在 ii 使得 u=i,v=i+1u=i,v=i+1。

特殊性质 B:type=0type=0。