#1827. 树据结构
树据结构
树据结构
题目描述
标题: 树据结构 - Problem - QOJ.ac
The problem was used in the following contests:
给出一棵 n 个点的树,满足以下性质:
-
每个叶子的深度都相同
-
树的编号按照 BFS 序标号,构造方法具体如下:
- 设根节点为标号1,将1加入队列
- 每次取出队列头,将其儿子依次设为下一个未使用的标号,并按标号顺序加入队列
每个点都有一个权值,初始为0
给出两种操作:
- 操作 1:对点 x 所在子树内的每个点加 y
- 操作 2:进行点权的轮换,将点 i 的权值移动到(imodn)+1处
求 q 次操作后每个点的权值,为避免输出过大,请输出每个点权值的异或和
输入格式
第一行两个数 n 与 q,表示树的大小以及操作次数
接下来一行 n−1 个数,第 i 个数fa[i+1]表示点i+1的父亲节点(根据 BFS 的性质,当 i≤j 时有 fa[i]≤fa[j])
之后 q 行,分别表示每次操作,若为 1 x y 则表示操作 1,对子树 x 的点加 y;若为 2 则表示操作 2,进行轮换操作
输出格式
一行一个数,表示所有点权的异或和
样例输入
6 10
1 1 2 3 3
1 3 1
1 2 2
2
1 4 3
1 5 4
2
2
1 1 5
2
1 6 6
样例输出
10
样例解释
实际答案为
9 11 6 6 5 13
异或和为10
数据范围
对于100的数据:n,Q≤100000,y≤10000
子任务编号 n,Q≤ 特殊性质 分值 1 1000 21 2 100000 只有操作1 8 3 fa[i+1]=i 8 4 给出的是一棵完全二叉树,n=2k−1 13 5 叶子个数 ≤20 13 6 50000 21 7 100000 16
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
6 10
1 1 2 3 3
1 3 1
1 2 2
2
1 4 3
1 5 4
2
2
1 1 5
2
1 6 6
10