[Codechef FEB13] Obserbing the tree树上询问

时间限制:20s      空间限制:1280MB

题目描述

      小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,不会读取没保存的局面


题目来源

持久化线段树