[Home|Training|Problems|Contests|C Language] | [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 0.9ms with 1 query(s).

Online Judge for ACM/ICPC

Processed in 0.9ms with 1 query(s).