Problem E - USTC Online Judge

Rank

Problem E

Special tree

Time Limit: 3000ms
Memory Limit: 65536kb

Description

There is a special tree with N nodes and N-1 bidirectional edges in our campus, and each node has one value initially. Based on tree's property, traveling between any two nodes is possible.
As we know any one edge can divide the tree into two connected components named P1 and P2. Now two operations, described as follows in details, can be done.
1)Add X A B: X means the X-th edge according to the input order, and the X-th edge can divide the tree into two connected components, named P1 and P2. Now we use C to denote the number of nodes in P1, D to denote the number of nodes in P2.
If C<D, then add value A to every node of P1 and add value B to every node of P2.
If C>D, then add value B to every node of P1 and add value A to every node of P2.
If C=D, do nothing.
2)Query X: (X, P1, P2 the same meaning as above). We use M1 to denote the maximum value among all nodes in P1, M2 to denote the maximum value among all nodes in P2.
If M1<M2 output M1 M2
If M1>=M2 output M2 M1

Input

The first line, an integer T, indicates the number of test cases (T<=10). For each test case:
The first part: two integers N (2<=N<=10000), Q (1<=Q<=100000), indicating number of nodes and number of operations we need do respectively.
The second part: a line containing N integers (positive integer not larger than 100), indicating the initial weight of each node.
Then followed by N-1 lines and each line contains two integers u and v, meaning node u and node v are connected directly by a bidirectional edge .and edge’s input order is from 1 to N-1.
Each of the last Q lines is in one of the two forms: Add X A B or Query X.
1<=X<=N-1, 1<=A, B<=1000.
All the numbers above are integers.

Output

For each "Query", output the corresponding answer.

Sample Input

1
4 3
2 1 4 8
3 1
3 4
2 1
Query 1
Add 2 4 5
Query 1

Sample Output

2 8
6 13

[Submit|Discuss|Add to bookmark]