OI题库

【题目描述】

“大话西游”是一个在中国非常流行的在线游戏，由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

【提示】

在此键入。

【来源】

在此键入。