← 返回题目列表

Codeforces · 894/D

D. 拉尔夫和他的二进制国家之旅

中文机器翻译题面 查看原题

拉尔夫在二元国家。二元国家由 n 个城市和连接城市的 (n - 1) 条双向道路组成。道路编号从 1 到 (n - 1),第 i 条道路连接标记为 $$\left\lfloor \frac{i+1}{2} \right\rfloor$$ 的城市(这里 ⌊ x⌋ 表示 x 向下舍入到最接近的整数)和标记为 (i + 1) 的城市,第 i 条道路的长度为 Li。

现在拉尔夫给你 m 个疑问。在每个查询中,他都会告诉您一些城市 Ai 和一个整数 Hi。他想从这座城市出发进行一些旅行。他可以选择二元国的任意一个城市(包括艾城)作为游览的终点城市。他在一次旅行中获得了幸福感(Hi - L),其中L是城市Ai与终点城市之间的距离。

拉尔夫对来自艾城的旅行很感兴趣,在旅行中他可以获得积极的快乐。对于每个查询,计算所有此类旅行的幸福感增益总和。

拉尔夫永远不会在同一个旅行中两次或多次(在一个查询中),他永远不会在一次旅行中两次或多次经过同一个城市。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 106, 1 ≤ m ≤ 105)。

接下来有 ​​(n - 1) 行,每行包含一个整数 Li (1 ≤ Li ≤ 105),表示第 i 条路的长度。

m 行,每行包含两个整数 Ai 和 Hi (1 ≤ Ai ≤ n, 0 ≤ Hi ≤ 107)。

输出

打印 m 行,在第 i 行打印一个整数——第 i 个查询的答案。

示例

输入 #1

2 2
5
1 8
2 4

输出 #1

11
4

输入 #2

6 4
2
1
1
3
2
2 4
1 3
3 2
1 7

输出 #2

11
6
3
28

注意

这是第二个示例的说明。

Ralph 的第一个查询是从城市 2 开始游览,Hi 等于 4。以下是选项:

- 他可以选择城市 5 作为他的终端城市。由于城市5与城市2的距离为3,因此他可以获得的幸福感为4 - 3 = 1。
- 他可以选择城市4作为他的终点城市并获得幸福3。
- 他可以选择城市1作为他的终点城市并获得幸福2。
- 他可以选择城市3作为他的终点城市并获得幸福1。
- 请注意,拉尔夫可以选择城市 2 作为他的终点城市并获得幸福 4。
- 拉尔夫不会选择城市6作为他的终点城市,因为城市6和城市2之间的距离是5,这会导致拉尔夫的幸福感为负。

因此第一个查询的答案是 1 + 3 + 2 + 1 + 4 = 11。