GSS7 - Can you answer these queries VII

# 题目描述 给定一棵树，有$N(N \le 100000)$个节点，每一个节点都有一个权值$x_i (|x_i| \le 10000)$ 你需要执行$Q (Q \le 100000)$次操作： 1. `1 a b` 查询`(a,b)`这条链上的最大子段和，可以为空（即输出$0$） 2. `2 a b c` 将`(a,b)`这条链上的所有点权变为`c` $(|c| <= 10000)$ # 输入格式： 第一行一个整数$N$ 接下来一行有$N$个整数表示$x_i$ 接下来$N-1$行，每行两个整数$u,v$表示$u$和$v$之间有一条边相连 接下来一行一个整数$Q$ 之后有$Q$行，每行诸如`1 a b`或者`2 a b c` # 输出格式 对于每一个询问，输出答案 # 输入样例 ``` plain 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 ``` # 输出样例 ``` plain 5 9 ```

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)

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_ .

For each query, output one line the maximum contiguous sum.

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

5
9