DFS Order Practice 2

Problem Description

Given a tree with $n$ vertices, each vertex has a weight $w_i$, and vertex $1$ is the root. There are $q$ operations:

1. 1 x y: change the weight of vertex $x$ to $y$.
2. 2 x: query the sum of weights in the subtree of vertex $x$.
3. 3 x: move the root to vertex $x$.

Input Format

The first line contains two integers $n, q\ (1 \le n, q \le 2 \times 10^5)$.

The next $n-1$ lines each contain two integers $u, v$, denoting an edge.

The next line contains $n$ integers $w_1, w_2, \dots, w_n\ (1 \le w_i \le 10^9)$.

The next $q$ lines each describe one operation. It is guaranteed that $1 \le x \le n,\ 1 \le y \le 10^9$.

Output Format

For each query operation (type 2), output one number: the answer.

Sample Input

5 6
1 2
2 3
2 4
3 5
1 2 3 4 5
2 3
1 2 10
3 3
2 3
3 5
2 3

Sample Output

8
23
18