D. Ralph And His Tour in Binary Country

Codeforces

IDCF894D

Time2000ms

Memory512MB

Difficulty—

brute forcedata structurestrees

English · Original

Chinese · Translation

Formal · Original

Ralph is in the Binary Country. The Binary Country consists of _n_ cities and (_n_ - 1) bidirectional roads connecting the cities. The roads are numbered from 1 to (_n_ - 1), the _i_\-th road connects the city labeled (here ⌊ _x_⌋ denotes the _x_ rounded down to the nearest integer) and the city labeled (_i_ + 1), and the length of the _i_\-th road is _L__i_. Now Ralph gives you _m_ queries. In each query he tells you some city _A__i_ and an integer _H__i_. He wants to make some tours starting from this city. He can choose any city in the Binary Country (including _A__i_) as the terminal city for a tour. He gains happiness (_H__i_ - _L_) during a tour, where _L_ is the distance between the city _A__i_ and the terminal city. Ralph is interested in tours from _A__i_ in which he can gain positive happiness. For each query, compute the sum of happiness gains for all such tours. Ralph will never take the same tour twice or more (in one query), he will never pass the same city twice or more in one tour. ## Input The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 106, 1 ≤ _m_ ≤ 105). (_n_ - 1) lines follow, each line contains one integer _L__i_ (1 ≤ _L__i_ ≤ 105), which denotes the length of the _i_\-th road. _m_ lines follow, each line contains two integers _A__i_ and _H__i_ (1 ≤ _A__i_ ≤ _n_, 0 ≤ _H__i_ ≤ 107). ## Output Print _m_ lines, on the _i_\-th line print one integer — the answer for the _i_\-th query. [samples] ## Note Here is the explanation for the second sample. Ralph's first query is to start tours from city 2 and _H__i_ equals to 4. Here are the options: * He can choose city 5 as his terminal city. Since the distance between city 5 and city 2 is 3, he can gain happiness 4 - 3 = 1. * He can choose city 4 as his terminal city and gain happiness 3. * He can choose city 1 as his terminal city and gain happiness 2. * He can choose city 3 as his terminal city and gain happiness 1. * Note that Ralph can choose city 2 as his terminal city and gain happiness 4. * Ralph won't choose city 6 as his terminal city because the distance between city 6 and city 2 is 5, which leads to negative happiness for Ralph. So the answer for the first query is 1 + 3 + 2 + 1 + 4 = 11.

Ralph 在 Binary Country 中。Binary Country 由 #cf_span[n] 座城市和 #cf_span[(n - 1)] 条双向道路组成，这些道路连接着城市。道路编号从 #cf_span[1] 到 #cf_span[(n - 1)]，第 #cf_span[i] 条道路连接编号为 #cf_span[⌊ i/2 ⌋] 的城市（此处 #cf_span[⌊ x⌋] 表示将 #cf_span[x] 向下取整到最近的整数）和编号为 #cf_span[(i + 1)] 的城市，且第 #cf_span[i] 条道路的长度为 #cf_span[Li]。现在 Ralph 给你 #cf_span[m] 个查询。在每个查询中，他告诉你某个城市 #cf_span[Ai] 和一个整数 #cf_span[Hi]。他希望从这个城市出发进行一些旅行。他可以选择 Binary Country 中的任意城市（包括 #cf_span[Ai]）作为旅行的终点城市。在一次旅行中，他获得的幸福值为 #cf_span[(Hi - L)]，其中 #cf_span[L] 是城市 #cf_span[Ai] 与终点城市之间的距离。 Ralph 对那些能获得正幸福值的旅行感兴趣。对于每个查询，计算所有此类旅行的幸福值总和。 Ralph 在一次查询中不会重复进行相同的旅行，也不会在一次旅行中经过同一城市两次或以上。第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 106]，#cf_span[1 ≤ m ≤ 105]）。接下来 #cf_span[(n - 1)] 行，每行包含一个整数 #cf_span[Li]（#cf_span[1 ≤ Li ≤ 105]），表示第 #cf_span[i] 条道路的长度。接下来 #cf_span[m] 行，每行包含两个整数 #cf_span[Ai] 和 #cf_span[Hi]（#cf_span[1 ≤ Ai ≤ n]，#cf_span[0 ≤ Hi ≤ 107]）。请输出 #cf_span[m] 行，第 #cf_span[i] 行输出一个整数 —— 第 #cf_span[i] 个查询的答案。以下是第二个样例的解释。 Ralph 的第一个查询是从城市 #cf_span[2] 出发，且 #cf_span[Hi] 等于 #cf_span[4]。可能的选择如下：因此第一个查询的答案是 #cf_span[1 + 3 + 2 + 1 + 4 = 11]。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 106]，#cf_span[1 ≤ m ≤ 105]）。#cf_span[(n - 1)] 行随后出现，每行包含一个整数 #cf_span[Li]（#cf_span[1 ≤ Li ≤ 105]），表示第 #cf_span[i] 条道路的长度。#cf_span[m] 行随后出现，每行包含两个整数 #cf_span[Ai] 和 #cf_span[Hi]（#cf_span[1 ≤ Ai ≤ n]，#cf_span[0 ≤ Hi ≤ 107]）。 ## Output 请输出 #cf_span[m] 行，第 #cf_span[i] 行输出一个整数 —— 第 #cf_span[i] 个查询的答案。 [samples] ## Note 以下是第二个样例的解释。 Ralph 的第一个查询是从城市 #cf_span[2] 出发，且 #cf_span[Hi] 等于 #cf_span[4]。可能的选择如下：他可以选择城市 #cf_span[5] 作为终点。由于城市 #cf_span[5] 与城市 #cf_span[2] 之间的距离为 #cf_span[3]，他可以获得幸福值 #cf_span[4 - 3 = 1]。他可以选择城市 #cf_span[4] 作为终点，获得幸福值 #cf_span[3]。他可以选择城市 #cf_span[1] 作为终点，获得幸福值 #cf_span[2]。他可以选择城市 #cf_span[3] 作为终点，获得幸福值 #cf_span[1]。注意，Ralph 可以选择城市 #cf_span[2] 作为终点，获得幸福值 #cf_span[4]。 Ralph 不会选择城市 #cf_span[6] 作为终点，因为城市 #cf_span[6] 与城市 #cf_span[2] 之间的距离为 #cf_span[5]，这会导致他的幸福值为负。因此第一个查询的答案是 #cf_span[1 + 3 + 2 + 1 + 4 = 11]。

Let $ T $ be a rooted binary tree with $ n $ nodes labeled $ 1 $ to $ n $, where node $ i $ (for $ 2 \leq i \leq n $) is connected to node $ \lfloor i/2 \rfloor $ by an edge of length $ L_{i-1} $. The tree is rooted at node 1. For each query $ (A_i, H_i) $, define the set of valid terminal cities as: $$ S_i = \{ v \in \{1, 2, \dots, n\} \mid d(A_i, v) < H_i \} $$ where $ d(u, v) $ denotes the unique path distance between nodes $ u $ and $ v $ in the tree. The happiness gained for a tour from $ A_i $ to terminal city $ v $ is $ H_i - d(A_i, v) $. The answer for query $ i $ is: $$ \sum_{v \in S_i} (H_i - d(A_i, v)) $$ Equivalently: $$ |S_i| \cdot H_i - \sum_{v \in S_i} d(A_i, v) $$ Compute this for each query $ i = 1, 2, \dots, m $.

Samples

Input #1

Output #1

11
4

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. Ralph And His Tour in Binary Country",
    "description": {
      "content": "Ralph is in the Binary Country. The Binary Country consists of _n_ cities and (_n_ - 1) bidirectional roads connecting the cities. The roads are numbered from 1 to (_n_ - 1), the _i_\\-th road connects",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF894D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ralph is in the Binary Country. The Binary Country consists of _n_ cities and (_n_ - 1) bidirectional roads connecting the cities. The roads are numbered from 1 to (_n_ - 1), the _i_\\-th road connects...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Ralph 在 Binary Country 中。Binary Country 由 #cf_span[n] 座城市和 #cf_span[(n - 1)] 条双向道路组成，这些道路连接着城市。道路编号从 #cf_span[1] 到 #cf_span[(n - 1)]，第 #cf_span[i] 条道路连接编号为 #cf_span[⌊ i/2 ⌋] 的城市（此处 #cf_span[⌊ x⌋] 表示将 ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ T $ be a rooted binary tree with $ n $ nodes labeled $ 1 $ to $ n $, where node $ i $ (for $ 2 \\leq i \\leq n $) is connected to node $ \\lfloor i/2 \\rfloor $ by an edge of length $ L_{i-1} $. The...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments