AT_tokiomarine2020_d Knapsack Queries on a tree

有一棵包含 $N$ 个顶点的有根二叉树，每个顶点编号为 $1$ 到 $N$。顶点 $1$ 是根节点，对于每个顶点 $i$（$i \geq 2$），其父节点为顶点 $\left\lfloor \frac{i}{2} \right\rfloor$。 每个顶点上有一个物品。顶点 $i$ 上物品的价值为 $V_i$，重量为 $W_i$。现在，请你回答 $Q$ 个如下的查询： - 给定二叉树中的顶点 $v$ 和正整数 $L$，你可以从 $v$ 及其所有祖先节点上的物品中选择若干个（可以为 $0$ 个），使得所选物品的总重量不超过 $L$。请你求出所选物品的最大总价值。 这里，顶点 $u$ 是顶点 $v$ 的祖先，指的是 $u$ 是 $v$ 的间接父节点。也就是说，存在一个顶点序列 $w_1, w_2, \ldots, w_k$（$k \geq 2$），满足 $w_1 = v$，$w_k = u$，并且对于每个 $i$，$w_{i+1}$ 是 $w_i$ 的父节点。

第 $i$ 次查询给定的 $v$ 和 $L$ 分别为 $v_i$ 和 $L_i$。输入以如下格式从标准输入读入： > $N$ $V_1$ $W_1$ $:$ $V_N$ $W_N$ $Q$ $v_1$ $L_1$ $:$ $v_Q$ $L_Q$

对于每个 $i$（$1 \leq i \leq Q$），输出第 $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$ - 输入中所有数均为整数。 ### 样例解释 1 对于第一个查询，能选择的物品只有 $(V, W) = (1, 2)$，但由于 $L = 1$，无法选择任何物品。因此答案为 $0$。而对于第二个查询，能选择的物品有 $(V, W) = (1, 2)$ 和 $(V, W) = (2, 3)$，由于 $L = 5$，可以选择这两个物品。因此答案为 $3$。 由 ChatGPT 4.1 翻译