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

样例输出

#4649. Sum

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示