Background

Original link: https://oier.team/problems/J1C。

I came. I saw. I had anxiety. I left.

Problem Description

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

Input Format

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 Format

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

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

2
7
3

4 5
3 4 10 7 1 6 10 6 16 5 3 16 6 2 9
1 4 6
4 2 1
1 14 5
6 13 3
11 15 2

104
11
74
51
0

Hint

"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"

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