P10783 [MX-J1-T3] "FLA - III" Anxiety

Original link: 。 --- I came. I saw. I had anxiety. I left.

Given a binary tree with $2^n-1$ nodes, the weight of node $i$ is $w_i$, and node $1$ is the root. For every non-root node $i$, there is an undirected edge connecting node $i$ and node $\left\lfloor \frac{i}{2} \right\rfloor$. Note that $\left\lfloor X \right\rfloor$ denotes the greatest integer not exceeding $X$. Define the distance between nodes $u,v$ as the minimum number of edges that must be traversed to go from node $u$ to node $v$. Given $m$ queries, the $i$-th query provides three positive integers $x_i,y_i,k_i$. You need to output the sum of weights of all nodes in the tree whose distances to both nodes $x_i$ and $y_i$ are no more than $k_i$.

The first line contains two positive integers $n,m$. The second line contains $2^n-1$ positive integers; the $i$-th integer is $w_i$. The next $m$ lines each contain three positive integers $x_i,y_i,k_i$ on the $i$-th line.

Output $m$ lines, each containing one integer. The integer on the $i$-th line is the answer to the $i$-th query.

**"Sample Explanation #1"**  For the first query, the nodes that satisfy the condition are $1,2$, and the sum of weights is $2$. For the second query, the nodes that satisfy the condition are $1,2,3,4,5,6,7$, and the sum of weights is $7$. For the third query, the nodes that satisfy the condition are $1,2,3$, and the sum of weights is $3$. **"Constraints"** |Test Point ID|$n \leq$|$m \leq$|$k_i \leq$|$w_i \leq$| |:-:|:-:|:-:|:-:|:-:| |$1$|$2$|$5$|$5$|$10$| |$2 \sim 3$|$10$|$1000$|$1000$|$1000$| |$4 \sim 5$|$18$|$2 \times 10^5$|$5$|$10^9$| |$6 \sim 7$|$18$|$2 \times 10^5$|$10^9$|$1$| |$8 \sim 10$|$18$|$2 \times 10^5$|$10^9$|$10^9$| For $100\%$ of the testdata, $2 \leq n \leq 18$, $1 \leq m \leq 2 \times 10^5$, $1 \leq x_i,y_i \leq 2^n-1$, $1 \leq k_i \leq 10^9$, $1 \leq w_i \leq 10^9$, and $x_i \neq y_i$. Node indices are integers from $1$ to $2^n-1$. Translated by ChatGPT 5