← 返回题目列表

AtCoder · tokiomarine2020_d

D. 树上的背包查询

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

分数: 700 点

问题陈述

我们有一个有根二叉树 N 顶点,其中顶点编号 1 to N。 顶点 1 是根,也是顶点的父级 i (i \geq 2) 是顶点 \left[ \frac{i}{2} \right].

每个顶点都有一个项目。顶点中的项目 i 的值为 V_i 和重量 W_i。 现在,处理以下查询 Q 次:

  • 给定一个顶点 树的 v 和一个正整数 L。 让我们选择一些(可能没有)项目 v 和祖先 v 使得它们的总重量最多为 L。 找出所选项目的最大可能总价值。

在这里,顶点 当存在连接它们的边时, u 据说是Vertex的祖先 v 当 u 是 v,即存在一系列顶点 w_1,w_2,\ldots,w_k (k\geq 2) 其中 w_1=v, w_k=u,和 w_{i+1} 是父级 w_i 对于每个 i.

约束

  • 输入中的所有值都是整数。
  • 1 \leq N < 2^{18}
  • 1 \leq Q \leq 10^5
  • 1 \leq V_i \leq 10^5
  • 1 \leq W_i \leq 10^5
  • 对于值 每个查询中给出的 v 和 L , 1 \leq v \leq N 和 1 \leq L \leq 10^5.

输入

让 v_i 和 L_i 是值 v 和 L 中给出 i第一个查询。 然后,输入从标准输入以以下格式给出:

N
V_1 W_1
:
V_N W_N
Q
v_1 L_1
:
v_Q L_Q

输出

对于每个整数 i 来自 1 通过 Q, 的 i- 第行应包含对 i-第一个查询。


示例输入 1

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

示例输出 1

0
3
3

在第一个查询中,我们只有一个选择:带有 (V, W)=(1,2)。自从 L = 1,我们实际上无法选择它,所以我们的回应应该是 0.

在第二个查询中,我们有两个选择:带有 (V, W)=(1,2) 和 (V, W)=(2,3)。自从 L = 5,我们可以两者都选择,所以我们的响应应该是 3.


示例输入 2

15
123 119
129 120
132 112
126 109
118 103
115 109
102 100
130 120
105 105
132 115
104 102
107 107
127 116
121 104
121 115
8
8 234
9 244
10 226
11 227
12 240
13 237
14 206
15 227

示例输出 2

256
255
250
247
255
259
223
253