4649. Sum
#4649. Sum
题目描述
给一棵大小为(n<=100000)的树，每个点有权值vi。要求支持以下操作：
子树加、子树对某数取max/min、链加、链对某数取max/min、子树修改、链修改、链权值翻转、子树求和、链求和。输出对10^9+7取模的非负结果即可。
树有根为1。保证输入中的链权值翻转操作的i为j的祖先。
输入格式
输入第一行一个正整数n，第二行n个整数v，第三行到第n+1行每行两个数u、v代表u和v之间有一条边。
接下来一行一个整数(m<=100000)，下面m行每行一个操作。操作格式如下：
SUBADD i v i的子树加上v
SUBMAX i v i的子树对v取max
SUBMIN i v i的子树对v取min
CHAINADD i j v i到j的路径上每个点加上v
CHAINMAX i j v i到j的路径上每个点对v取max
CHAINMIN i j v i到j的路径上每个点对v取min
SUBXGW i v i的子树修改为v
CHAINXGW i j v i到j的路径上每个点修改为v
CHAINREV i j i到j的路径进行权值翻转
SUBQUE i 输出i的子树和
CHAINQUE i j 输出i到j路径上的权值和
操作中所有v和点的初始权值v满足v<=1000000，保证全程不会有点权值超过10^9+7
输出格式
对于每个求和操作输出一行代表对应权值和。
样例
样例输入
10
-3 -2 1 3 1 -2 0 -5 1 4
2 1
3 1
4 1
5 2
6 4
7 3
8 2
9 3
10 2
19
SUBADD 4 2
SUBXGW 9 -5
CHAINQUE 1 1
SUBQUE 9
SUBMAX 7 -1
SUBMIN 10 2
CHAINQUE 6 9
SUBQUE 1
CHAINADD 9 3 4
CHAINXGW 5 7 5
CHAINQUE 7 7
SUBQUE 1
CHAINMAX 8 7 -5
CHAINMIN 5 3 4
CHAINQUE 3 1
SUBQUE 5
CHAINREV 1 7
CHAINQUE 3 2
SUBQUE 7
样例输出
1000000004
1000000002
1000000005
1000000001
5
26
8
4
13
4