[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，不会读取没保存的局面
题目来源
持久化线段树