[Login|Register]
Problems

Status

Rank

Problem 1303
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, 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
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
7 12
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.8ms with 1 query(s).