Trees and Queries 10

You are given a tree with $N$ vertices. A tree is a connected undirected graph with no cycle. The vertices are numbered from 1 to $N$, and each vertex carries one integer weight.

Write a program that processes the following two kinds of queries.

• 1 u v: list the vertices on the path from $u$ to $v$ in the order they are visited, then report the largest sum of a contiguous block of that list. The empty block is allowed, so the answer is always at least 0.
• 2 u v w: change the weight of every vertex on the path from $u$ to $v$ to $w$.

Exactly one path joins two vertices of a tree, so the path of each query is unique. If $u$ equals $v$, the path is that single vertex.

The first line contains the number of vertices $N$ ($2 \le N \le 100{,}000$).

The second line contains the weights of vertices 1 through $N$ in order. Each weight is an integer whose absolute value is at most 10,000.

Each of the next $N-1$ lines contains two vertex numbers $u$ and $v$ joined by an edge. The given edges form a tree.

The next line contains the number of queries $M$ ($1 \le M \le 100{,}000$).

Each of the next $M$ lines contains one query in the form 1 u v or 2 u v w, where $1 \le u, v \le N$ and $w$ is an integer whose absolute value is at most 10,000.

For each query of the first kind, print its answer on its own line, in the order the queries are given. A query of the second kind prints nothing.