分数: 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