P13567 "CZOI-R5" Warp Points

An interstellar war has broken out in the universe.

To perform instant movement in the interstellar war, we have built $n$ warp points in the occupied star regions. All warp points form a rooted tree with warp point $1$ as the root. The energy value of warp point $i$ is $a_i$. We say that warp point $u$ can reach warp point $v$ after $x$ consecutive warps if and only if starting from warp point $u$, after walking along $x$ edges we can arrive at warp point $v$, and during the process the distance to warp point $1$ keeps strictly increasing or keeps strictly decreasing. Now we need to perform $m$ maintenance operations of the following types: 1. **Space Energy Boost**: For all warp points that can be reached from warp point $u$ after $x$ consecutive warps, add $y$ to their energy values. 2. **Warp Test**: For all warp points that can be reached from warp point $u$ after $x$ consecutive warps, output the sum of their energy values.

The first line contains $2$ integers $n, m$. The second line contains $n$ integers; the $i$-th one is $a_i$. The next $n - 1$ lines each contain $2$ integers $u, v$, representing an edge. The next $m$ lines each start with an integer $p$, then: - If $p=1$, input $3$ integers $u, x, y$, representing one **Space Energy Boost**. - If $p=2$, input $2$ integers $u, x$, representing one **Warp Test**.

Output several lines of integers, which are the results of all **Warp Tests**.

**Sample Explanation**  The tree is shown in the figure. In the first operation, the warp points that satisfy the condition are warp points $3, 5$. After the operation, $a=\{6,8,11,10,13\}$. In the second operation, the warp points that satisfy the condition are warp points $1, 5$, and the answer is $6+13=19$. In the third operation, the warp point that satisfies the condition is warp point $2$, and the answer is $8$. In the fourth operation, the warp points that satisfy the condition are warp points $1, 3$. After the operation, $a=\{10,8,15,10,13\}$. In the fifth operation, the warp points that satisfy the condition are warp points $3, 5$, and the answer is $15+13=28$. **Constraints** **This problem uses bundled testdata.** - Subtask #1 ($15\text{ pts}$): $n, m \le 10^3$. - Subtask #2 ($15\text{ pts}$): $x \le 1$. - Subtask #3 ($25\text{ pts}$): $x \le 50$. - Subtask #4 ($45\text{ pts}$): No special constraints. For $100\%$ of the testdata, $1\le u\le n\le3\times10^5$, $1 \le m \le 3 \times 10^5$, $1 \le a_i, y \le 10^9$, $0 \le x \le n$, $p\in\{1,2\}$。 Translated by ChatGPT 5