GSS7  Can you answer these queries VII
Given a tree with N (N <= 100000) nodes. Each node has a integer value x_i (x_i <= 10000).
You have to apply Q (Q <= 100000) operations:
 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 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 N1 line, each consists two integer u, v, means that node u and node v are connected
next line consists 1 integer Q.
next Q line : 1 a b or 2 a b c .
Output
For each query, output one line the maximum contiguous sum.
Example
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 Output: 5 9
hide comments
cuichengxi:
20240227 14:17:33
I have nothing to say to this problem


thuylinhcbhk64:
20231105 17:45:14
"maybe empty" =)) 

changyouren:
20211002 07:43:33
nice problem 

DK...:
20171104 16:03:34
it's not necesary to use scanf/printf, simple fast I/O got AC 

weramajstor:
20170115 23:52:24
Like Dante said,"You who enter leave all your hope behind!" 

Ghost Of Perdition:
20140124 05:09:39
very hardimplementation problem !!!! 
Added by:  刘启鹏 
Date:  20100614 
Time limit:  0.200s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  my own problems 