P5314 [Ynoi2011] ODT

To be updated.

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$.

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.

For each operation of type $2$, output one line with one integer, the answer. It is guaranteed that the answer exists for every query.

- 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