#1827. 树据结构

    ID: 1827 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1787来源:qoj.ac数据:公开样例搜索队列线段树树状数组

树据结构

树据结构

题目描述

标题: 树据结构 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

给出一棵 n 个点的树,满足以下性质:

  1. 每个叶子的深度都相同

  2. 树的编号按照 BFS 序标号,构造方法具体如下:

    1. 设根节点为标号1,将1加入队列
    2. 每次取出队列头,将其儿子依次设为下一个未使用的标号,并按标号顺序加入队列

每个点都有一个权值,初始为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