题目描述

给一棵大小为(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