CF894D Ralph And His Tour in Binary Country

Ralph 身处“二进制国”。“二进制国”由 $n$ 个城市和 $n-1$ 条无向道路构成，这些道路编号为 $1$ 到 $n-1$。第 $i$ 条道路连接标号为 $⌊i/2⌋ + 1$ 的城市（这里 $⌊x⌋$ 表示 $x$ 向下取整）和标号为 $i+1$ 的城市，第 $i$ 条道路的长度为 $L_i$。 现在 Ralph 给你 $m$ 个询问。每个询问会告诉你一个城市 $A_i$ 和一个整数 $H_i$。他想从该城市出发进行旅行。他可以选择“二进制国”中的任意城市（包括 $A_i$）作为旅行的终点。对于一次旅行，他获得的快乐值为 $H_i - L$，其中 $L$ 是城市 $A_i$ 和所选终点城市之间的距离。 Ralph 只关心那些从 $A_i$ 出发、能够获得正快乐值的旅行。对于每个询问，请你计算所有这种旅行获得的快乐值之和。 Ralph 不会在同一个询问中重复相同的旅行路线，也不会在一次旅行中经过同一个城市两次或以上。

第一行包含两个整数 $n$ 和 $m$，满足 $1 \leq n \leq 10^6$，$1 \leq m \leq 10^5$。 接下来 $n-1$ 行，每行包含一个整数 $L_i$，$1 \leq L_i \leq 10^5$，表示第 $i$ 条道路的长度。 接下来 $m$ 行，每行包含两个整数 $A_i$ 和 $H_i$，$1 \leq A_i \leq n$，$0 \leq H_i \leq 10^7$。

输出 $m$ 行，每行一个整数，第 $i$ 行表示第 $i$ 个询问的答案。

这里给出第二个样例的解释。 Ralph 的第一个询问是从城市 $2$ 出发，$H_i$ 是 $4$。具体选择如下： - 他可以选择城市 $5$ 作为终点。由于城市 $2$ 到城市 $5$ 的距离是 $3$，他能获得的快乐值是 $4 - 3 = 1$。 - 他可以选择城市 $4$ 作为终点，获得 $3$ 的快乐值。 - 他可以选择城市 $1$ 作为终点，获得 $2$ 的快乐值。 - 他可以选择城市 $3$ 作为终点，获得 $1$ 的快乐值。 - 注意，Ralph 也可以选择城市 $2$ 作为终点，获得 $4$ 的快乐值。 - Ralph 不会选择城市 $6$ 作为终点，因为城市 $2$ 到城市 $6$ 的距离是 $5$，快乐值为负，不计算在内。 所以第一个询问的答案为 $1 + 3 + 2 + 1 + 4 = 11$。 由 ChatGPT 5 翻译