#P3221. [Codechef FEB13] Obserbing the tree树上询问

    ID: 2405 传统题 1000ms 512MiB 尝试: 588 已通过: 79 难度: 8 上传者: 标签>难度分类提高+/省选-树算法树链剖分LCA数据结构可持久化线段树路径复制历史版本查询排序与序列处理一维前缀和标记永久化CF2500

[Codechef FEB13] Obserbing the tree树上询问

Observing the Tree 树上询问

题目描述

给定一棵 nn 个结点的树,结点从 11 到 nn 编号,初始点权均为 00。初始状态保存为版本 00。支持以下三种操作。

  • 修改。从 xx 到 yy 按路径顺序给各结点的点权依次增加 a,a+b,a+2b,…a,a+b,a+2b,\ldots。操作完成后保存新版本,其编号为已执行的修改次数。
  • 查询。求当前状态下从 xx 到 yy 的路径点权之和。
  • 读取。将当前状态切换到指定的已保存版本。此前保存的各版本仍可读取。

输入格式

第一行输入两个整数 n,mn,m,分别表示结点数和操作数。接下来 n−1n-1 行,每行两个整数 ui,viu_i,v_i,表示一条无向边。

接下来 mm 行,每行开头有一个小写字母。设 tt 为最近一次输出的查询答案,初始为 00。

  • c x1 y1 a b 将 x1,y1x_1,y_1 分别与 tt 按位异或,得到 x,yx,y。对该路径执行修改,首项为 aa,公差为 bb。
  • q x1 y1 将 x1,y1x_1,y_1 分别与 tt 按位异或,得到 x,yx,y。查询该路径,输出答案,并将 tt 更新为这个答案。
  • l x1 将 x1x_1 与 tt 按位异或,得到要读取的版本编号。读取版本时,tt 保持原值。

输出格式

每次查询输出一行一个整数,表示路径上的点权之和。

样例

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

数据范围

n,m≤105n,m\le 10^5,0≤a,b≤10000\le a,b\le 1000,修改次数严格小于 m/2m/2。解码后的结点编号有效,读取的版本已经保存。

加密后的点编号和版本编号可能超过 32 位。由上述范围及修改次数可知,任意查询答案小于 2582^{58},因此加密参数均为小于 2582^{58} 的非负整数。