大话西游

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file westward.in Output file westward.out

【题目描述】


“大话西游”是一个在中国非常流行的在线游戏,由NIE公司开发和维护。这个游戏来源于著名的小说《西游记》和周星弛的电影,游戏的背景故事充满奇幻色彩,引人入胜。

游戏里面有很多片区域,不同的区域由不同的统治者管辖,其中有一个地方名叫“树国”,由一个妖怪控制着。这里有N个城堡,每个城堡都有其重要程度值(一个正整数,不超过10^8),这些城堡被N-1条双向道路所连接,任意两个城堡均可互达,城堡的重要程度值是可变的。现在,妖怪想知道如果破坏其中的一条道路会发生什么。本题中,你总共需要处理Q条指令,每一个都具有下面所述的格式:

(1)CHANGE

i w

本指令的含义为:将第i个城堡的重要程度值变为w(1<=w<=10^8)

(2)QUERY

j

本指令的含义为:输出min1*max1+min2*max2的值,详细如下:

第j条道路可以把“树国”分成两个连通块,分别称为part1和part2,其中

min1为part1中的最小重要程度值;

max1为part1中的最大重要程度值;

min2为part2中的最小重要程度值;

max2为part2中的最大重要程度值。


【输入格式】


第一行有两个整数N(2<=N<=100000)和Q(1<=Q<=100000),分别表示城堡的个数及指令的数目。


接下来的一行有N个整数(正整数,不超过10^8),表示起初每一个城堡的重要程度值(城堡的编号为1~N)。


接下来有N-1行,每行有两个整数u,v,表示在城堡u和城堡v之间有一条无向边相连,(边的编号依次为1~N-1)。

接下来有Q行,每行有一个指令,格式如下所述。


【输出格式】

对于每个"QUERY"指令,在单独一行输出结果。

【样例输入】

5 3
1 2 3 4 5
1 2
2 3
3 4
4 5
QUERY 1
CHANGE 1 10
QUERY 1

【样例输出】

11
110

【提示】

在此键入。

【来源】

在此键入。