Sum
时间限制：50s 空间限制：512MB
题目描述
给一棵大小为(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
提示
没有写明提示
题目来源
By DpDarkFantasy