Maximum weight in a monochromatic component

A tree with N vertices is given. A tree is a connected undirected graph with no cycles. The vertices are numbered 1 to N and the edges are numbered 1 to N-1. Every vertex is either black or white, and every vertex carries a natural number weight.

Vertices u and v are connected when every vertex on the path from u to v has the same color. u and v may be the same vertex.

Write a program that handles the following three queries.

• 1 i: change the color of vertex i. White becomes black, and black becomes white.
• 2 u: print the largest weight among the vertices connected to u.
• 3 u w: change the weight of vertex u to w.

The first line contains the number of vertices N. (2 ≤ N ≤ 100,000)

Each of the next N-1 lines contains the numbers u and v of the two vertices joined by edge i.

The next line contains the colors of vertices 1 through N in order. A color is 0 or 1, where 0 is black and 1 is white.

The next line contains the weights of vertices 1 through N in order.

The next line contains the number of queries M. (1 ≤ M ≤ 100,000)

Each of the next M lines contains one query.

Every weight is a natural number at most $10^9$, and so is the w of a type 3 query.

For each type 2 query, print its answer on its own line, in the order the queries are given.