#P3221. [Codechef FEB13] Obserbing the tree树上询问
[Codechef FEB13] Obserbing the tree树上询问
Observing the Tree 树上询问
题目描述
给定一棵 个结点的树,结点从 到 编号,初始点权均为 。初始状态保存为版本 。支持以下三种操作。
- 修改。从 到 按路径顺序给各结点的点权依次增加 。操作完成后保存新版本,其编号为已执行的修改次数。
- 查询。求当前状态下从 到 的路径点权之和。
- 读取。将当前状态切换到指定的已保存版本。此前保存的各版本仍可读取。
输入格式
第一行输入两个整数 ,分别表示结点数和操作数。接下来 行,每行两个整数 ,表示一条无向边。
接下来 行,每行开头有一个小写字母。设 为最近一次输出的查询答案,初始为 。
c x1 y1 a b将 分别与 按位异或,得到 。对该路径执行修改,首项为 ,公差为 。q x1 y1将 分别与 按位异或,得到 。查询该路径,输出答案,并将 更新为这个答案。l x1将 与 按位异或,得到要读取的版本编号。读取版本时, 保持原值。
输出格式
每次查询输出一行一个整数,表示路径上的点权之和。
样例
5 7
1 2
2 3
3 4
4 5
c 2 5 2 3
c 3 4 5 10
q 1 3
l 13
q 13 15
l 6
q 6 4
12
7
7
数据范围
,,修改次数严格小于 。解码后的结点编号有效,读取的版本已经保存。
加密后的点编号和版本编号可能超过 32 位。由上述范围及修改次数可知,任意查询答案小于 ,因此加密参数均为小于 的非负整数。