21668_WestwardJourneyOnline

"Westward Journey" is one of the most popular online games in China, which is developed and run by NIE. The game is based on the famous and romantic Chinese classical fiction "Journey to the West", and the well-know film by Stephen Chow. The story behind "Westward Journey" is fantasy and thus attracts many players.

The game contains many regions, and different regions are ruled by different dominators. One of the regions which named "Tree World" is now ruled by a monster. There are N castles in this region, and each of them has its importance value (a positive integer not larger than 10⁸). The castles are connected by (N - 1) bidirectional roads. The roads make all the castles connected (that means you can travel between any two castles of them). The importance values of the castles are variable. Now, the monster wants to know something if he destroys one of the roads. In detail, you are to handle totally Q instructions: each of them can be one of the following forms.

The first line contains an integer T ( T ≤ 10 ), the number of test cases.

For each test case, the first line contains two integers N ( 2 ≤ N ≤ 100000 ) and Q ( 1 ≤ Q ≤ 100000 ), indicating the number of castles and instructions.

The following line contains N integers (positive integer not larger than 10⁸), indicating the initial importance value of each castle (castles are numbered from 1 to N).

The following (N-1) lines each contains two integers u and v, indicating castle u and castle v are connected directly by a bidirectional road (the roads are numbered from 1 to N-1).

The following Q lines each contains an instruction according to the specification above.

For each "QUERY" instruction, output the result on a separate line.

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

11
110