GSS7 - Can you answer these queries VII
Given a tree with N (N <= 100000) nodes. Each node has a interger value x_i (|x_i| <= 10000).
You have to apply Q (Q <= 100000) 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 interger N.
next line consists N interger x_i.
next N-1 line , each consists two interger u,v , means that node u and node v are connected
next line consists 1 interger 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
|
DK...:
2017-11-04 16:03:34
it's not necesary to use scanf/printf, simple fast I/O got AC |
|
weramajstor:
2017-01-15 23:52:24
Like Dante said,"You who enter leave all your hope behind!" |
|
Ghost Of Perdition:
2014-01-24 05:09:39
very hard-implementation problem !!!! |
Added by: | 刘启鹏 |
Date: | 2010-06-14 |
Time limit: | 0.200s-0.570s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
Resource: | my own problems |