Time Limit: 3000ms
Memory Limit: 65536kb
DescriptionThere 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, do nothing. Else
Adding value Min(A,B) to every node of less nodes between P1 and P2.
Adding value Max(A,B) to every node of more nodes between P1 and P2.
Min(A , B) : taking smaller value of A and B.
Max(A,B): taking bigger value of A and B.
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
InputThe 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.
OutputFor each "Query", output the corresponding answer.
1 4 3 2 1 4 8 3 1 3 4 2 1 Query 1 Add 2 4 5 Query 1
2 8 7 12