7407: GSS7 - Can you answer these queries VII
[Creator : ]
Description
Given a tree with $N\ (N \leq 100,000)$ nodes. Each node has a integer value $x_i\ (|x_i| \leq 10,000)$.
You have to apply $Q\ (Q \leq 100,000)$ operations:
1. 1 a b : answer the maximum contiguous sum (maybe empty, will always larger than or equal to 0) from the path a->b ( inclusive ).
2. 2 a b c : change all value in the path a->b ( inclusive ) to c. (|c| <= 10000)
You have to apply $Q\ (Q \leq 100,000)$ operations:
1. 1 a b : answer the maximum contiguous sum (maybe empty, will always larger than or equal to 0) from the path a->b ( inclusive ).
2. 2 a b c : change all value in the path a->b ( inclusive ) to c. (|c| <= 10000)
Input
first line consists one integer $N$.
next line consists $N$ integer $x_i$.
next $N-1$ line, each consists two integer $u, v$, means that node $u$ and node $v$ are connected
next line consists one interger $Q$.
next $Q$ line : 1 a b or 2 a b c .
next line consists $N$ integer $x_i$.
next $N-1$ line, each consists two integer $u, v$, means that node $u$ and node $v$ are connected
next line consists one interger $Q$.
next $Q$ line : 1 a b or 2 a b c .
Output
For each query, output one line the maximum contiguous sum.
Sample 1 Input
5
-3 -2 1 2 3
1 2
2 3
1 4
4 5
3
1 2 5
2 3 4 2
1 2 5
Sample 1 Output
5
9