Description

You are given a tree where each edge has weight $1$, and each node has a weight.

Support two operations:

• 1 x y z: Add $z$ to the weights of all nodes on the simple path from $x$ to $y$.
• 2 x y: Query the $y$-th smallest node weight among all nodes whose distance to node $x$ is less than or equal to $1$.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers, the weight of each node.

Then follow $n-1$ lines, each containing two integers $x, y$ indicating that there is an edge between $x$ and $y$.

Then follow $m$ lines, each in the form 1 x y z or 2 x y, as described above.

Output Format

For each operation of type $2$, output one line with one integer, the answer.

It is guaranteed that the answer exists for every query.

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

4
3
4

Hint

• Idea: nzhtl1477.
• Solution: nzhtl1477 ( $O( n\log^2 n / \log\log n )$ solution ), negiizhao ( $O( n\log n\log\log\log n )$ solution ), ccz181078 ( $O( n\log n )$ solution ).
• Code: nzhtl1477 ( $O( n\log^2 n / \log\log n )$ code ).
• Data: nzhtl1477 ( partially uploaded ).

Subtask 1: $20\%$ $n, m \leq 1000$.

Subtask 2: $10\%$ the tree is a chain.

Subtask 3: $20\%$ $n, m \leq 10^5$.

Subtask 4: $30\%$ $n, m \leq 4\times 10^5$.

Subtask 5: $20\%$ $n, m \leq 10^6$.

Constraints: For $100\%$ of the testdata, $1 \leq n, m \leq 10^6$, $0 \leq$ the value added in each update $\leq 2000$, $0 \leq$ the initial node weights $\leq 2000$.

Translated by ChatGPT 5