DFS序练习2

题目描述

给一棵$n$个点的树，每个点有点权$w_i$，1号点为根。给$q$个操作：

1. 1 x y，将$x$点的点权改成$y$。
2. 2 x，询问$x$点子树的点权和。
3. 3 x，将根换到$x$位置。

输入格式

第一行两个整数$n, q (1\leq n, q\leq 2\times 10^5)$。

接下来$n-1$行，每行两个整数$u, v$表示一条边的两个端点。

接下来一行$n$个数，$w_1, w_2, \dots, w_n (1\leq w_i\leq 10^9)$。

接下来$q$行，每行一个操作，保证$1\leq x\leq n, 1\leq y\leq 10^9$。

输出格式

对于每个询问操作，输出一个数表示答案。

样例输入

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

样例输出

8
23
18