DFS Order Exercise 1

Problem Description

You are given a tree with $n$ vertices, each carrying a point weight $w_i$, with vertex $1$ as the root. You must answer $q$ operations:

1. 1 x y: change the point weight of vertex $x$ to $y$.
2. 2 x: query the sum of point weights of the subtree of $x$, and the sum of point weights of the path from $x$ up to the root (both sums include vertex $x$ itself).

Input Format

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

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

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

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

Output Format

For each query operation, output two numbers: the two answers.

Sample Input

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

Sample Output

15 1
8 6
23 1
8 14

Constraints

• $1 \leq n, q \leq 2 \times 10^5$
• $1 \leq w_i \leq 10^9$
• $1 \leq x \leq n,\ 1 \leq y \leq 10^9$