BZPRO

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

内存限制：512 MiB 时间限制：20 Sec
提交 提交记录 讨论

题目描述

      小N最近在做关于树的题。今天她想了这样一道题，给定一棵N个节点的树，节点按1~N编号，一开始每个节点上的权值都是0，接下来有M个操作。第一种操作是修改，给出4个整数X,Y,A,B,对于X到Y路径上加上一个首项是A，公差是B的等差数列，因为小N十分谨慎，所以她每做完一个修改操作就会保存一次，初始状态是第0次保存的局面。第二种操作是求和，给出2个整数X,Y，输出X到Y路径上所有节点的权值和。第三种操作是读取之前第X次保存的局面，所有节点的状态回到之前第X次保存的状态。现在请你对每一个求和操作输出答案。

输入格式

      第一行2个整数N,M表示节点个数和操作次数。
      接下来N-1行每行2个整数Ui,Vi表示了这棵树中Ui和Vi这2个节点间有边相连。
      接下来M行每行先有一个字符表示了操作的类型：
           如果是’c’，那么代表了一个修改操作，接下来有4个整数X1,Y1,A,B，为了使得询问在线，正确的X=X1 xor上次输出的数,Y=Y1 xor上次输出的数,如果之前没有输出过那么当成0。
           如果是’q’，那么代表了一个求和操作，接下来有2个整数X1,Y1,和修改操作一样需要xor上次输出。
           如果是’l’，那么代表了一次读取操作，接下来1个整数X1，正确的X=X1 xor上次输出的数。

输出格式

 
      对于每一个求和操作，输出求和后的值。

样例

样例输入


			
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

数据范围与提示



     100%的数据中N,M<=100000,0<=A,B<=1000,0<=X1,Y1<=10^1,修改次数<M/2，不会读取没保存的局面

BZPRO Powered by Remmina.
Github Repository