#1752. 树特卡克林

    ID: 1752 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1091来源:qoj.ac数据:公开样例分块

树特卡克林

树特卡克林

题目描述

标题: 树特卡克林 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

给定一棵包含 n 个点的由有根树构成的森林(初始没有边,每个顶点是一棵有根树的根),顶点由 1 到 n 的整数编号表示。你需要维护森林的轻重链剖分结构,具体如下:

对每个顶点 ω(1≤ω≤n),记其孩子构成的集合为 children(ω)。对于每个 ω,若 ω 不是根,则记其父亲为 father(ω)。

一个顶点 ω 的子树规模 size(ω) 定义为 1+∑u∈children(ω)size(u)

一个顶点 ω 如果不是叶子(即 children(ω)≠∅),则它的重孩子 he(ω) 被定义为 arg⁡maxu∈children(ω)size(u)⋅n+max(u,he(u),he(he(u)),⋯),即子树规模最大的孩子(若有多个孩子 u 的子树规模相同,则取以 u 为根的子树中,u 所在的重链中最大的编号最大);

重链是一个由顶点构成的序列 ω1,ω2,⋯,ωk(k>0),满足条件:

  • ω1 是根或 ω1≠he(father(ω1))
  • ωi=he(ωi−1)(2≤i≤k)

对一棵树,每个顶点恰好属于一条重链。重链的权值为 ω1⊕ω2⊕⋯⊕ωk,即序列中顶点编号的按位异或和。

需要依次进行 2m 次操作,操作类型如下:

  • 加边:给出两个顶点 a,b,令 b 成为 b 所在有根树的根(设定点构成的序列 t1,t2,⋯,tl 满足 tl=b 且 t1 为根,(ti,ti+1),1≤i<l 是 b 所在有根树上的有向边,将这些边反转为 (ti+1,ti) 即可令 b 成为根),然后加入 a 到 b 的有向边 (a,b),保证操作前 a,b 在不同的有根树上。
  • 删边:给出两个顶点 a,b,删除 a,b 间的有向边(可能为 (a,b) 或 (b,a)),保证这条边之前存在。
  • 查询:给出一个整数 k,设当前共有 N 条重链,询问当前存在的所有重链按权值从小到大排序后,第 ((k−1)modN)+1 小的权值。

输入格式

第一行有两个整数 n,m;

接下来 m 行,每行四个整数 oabk,若 o=1 则表示先加边 a,b 然后查询 k,若 o=0 则表示先删边 a,b 然后查询 k。

输出格式

共 m 行,每行一个整数,依次为每次查询操作的结果。

样例数据

样例输入

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

样例输出

4
5
7
4
6
6
6
4
5
4

子任务

共 31 个测试点,所有测试点满足 1≤n≤105,1≤m≤5×105,0≤o≤1,1≤a,b,k≤n,n,m,o,a,b,k 均为整数。

测试点可能具有以下性质:

  • 性质 1:操作使用以下策略随机生成,重复直到生成了 m 行的操作序列。

    • 在 [1,n] 中等概率随机选取三个整数 x,y,k,若 x,y 在不同的有根树上,则生成一行 1 x y k,否则若 x 不是根,等概率地生成一行 0 x father(x) k 或 0 father(x) x k 之一,否则不进行操作。
  • 性质 2:m=n−1,且对 2≤i≤n,数据的第 i 行为 1 a i k,其中 a 在 [1,i−1] 中的整数等概率选取。

  • 性质 3:m=n−1,且对 2≤i≤n,数据的第 i 行为 1 i b k,其中 b 在 [1,i−1] 中的整数等概率选取。

每个测试点的性质如下。

  • 子任务 1(5 分):测试点 1,n=10,m=50,满足性质 1。
  • 子任务 2(5 分):测试点 2,n=100,m=500,满足性质 1。
  • 子任务 3(10 分):测试点 3,n=1000,m=5000,满足性质 1。
  • 子任务 4(10 分):测试点 4,满足性质 2。
  • 子任务 5(10 分):测试点 5,满足性质 3。
  • 子任务 6(20 分):测试点 6-10,满足性质 1。
  • 子任务 7(40 分):测试点 11-31,没有特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 10
1 1 2 3
1 2 3 3
1 2 4 3
1 3 5 3
0 2 3 3
1 1 3 3
0 1 2 3
1 2 3 3
0 3 5 3
1 1 5 3
4
5
7
4
6
6
6
4
5
4