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

## 输入输出样例

### 输入样例 #1

``````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``````

### 输出样例 #1

``````5
9``````