Doctor Who的TARDIS 2
背景
刚才,Doctor Who
在餐厅里招待了Clara
。
描述
TARDIS
上有\( n\)个房间,编号分别为\(1\)到\(n\),每个房间都有一个门牌号\(w\)。
Doctor Who
兴致勃勃地希望Clara
完成以下操作:
I.CHANGE u t
: 把房间\(u\)的门牌号改为\(t\)。
II.QMAX u v
: 询问从房间\( u\)到房间\(v \)的路径上的房间的最大门牌号。
III.QSUM u v
问从房间\( u\)到房间\( v\)的路径上的房间的门牌号和。
注意:从点\(u \)到点\(v \)的路径上的房间包括\( u\)和\( v\)本身。
格式
输入格式
输入文件的第一行为一个整数\(n\),表示房间的个数。
接下来\( n-1\)行,每行\( 2\)个整数\(a \)和\(b\),表示房间\(a \)和房间\(b \)之间有一条走廊相连。
接下来一行\(n\)个整数,第\( i\)个整数\( w_i\)表示节点房间\(i \)的门牌号。
接下来\( 1\)行,为一个整数\( q\),表示操作的总数。
接下来\(q \)行,每行一个操作,以CHANGE u t
或者QMAX u v
或者QSUM u v
的形式给出。
输出格式
对于每个QMAX
或者QSUM
的操作,每行输出一个整数表示要求输出的结果。
样例1
输入样例1
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
输出样例1
4
1
2
2
10
6
5
6
5
16
限制
对于\( 100 \%\)的数据,保证\( 1\le n \le 3\times 10^4,0\le q\le 2\times 10^5\)。
中途操作中保证每个房间的门牌号\(w \)在\( -3\times 10^4\)到\( 3\times 10^4\)之间。