#WD231105B. 异或树(xortree)
题目描述
给定一棵
- 换根:将一个指定的节点设置为树的新根。
- 修改路径权值:给定两个节点,将这两个节点间路径上的所有节点权值(含这两个节点)增加一个给定的值。
- 修改子树权值:给定一个节点,将以该节点为根的子树内的所有节点权值增加一个给定的值。
- 询问路径:询问某条路径上节点的权值和。
- 询问子树:询问某个子树内节点的权值和。
输入格式
第一行一个整数
第二行
第三行
第四行一个整数
接下来
- 若类型为
,则接下来一个整数 ,表示新根的编号。 - 若类型为
,则接下来三个整数 ,分别表示路径两端的节点编号以及增加的权值。 - 若类型为
,则接下来两个整数 ,分别表示子树根节点编号以及增加的权值。 - 若类型为
,则接下来两个整数 ,表示路径两端的节点编号。 - 若类型为
,则接下来一个整数 ,表示子树根节点编号。
输出格式
对于每一个类型为
样例
输入数据 1
6
1 2 3 4 5 6
1 2 1 4 4
6
4 5 6
2 2 4 1
5 1
1 4
3 1 2
4 2 5
输出数据 1
15
24
19
更多样例,见选手文件。
数据范围与提示
对于
对于
对于
对于