题目描述

$N$ 頂点からなる根付き二分木があり、各頂点には $1$ から $N$ までの番号がついています。 頂点 $1$ が根であり、頂点 $i$ ($i\ \geqq\ 2$) の親は頂点 $\left[\ \frac{i}{2}\ \right]$ です。

各頂点には $1$ つのアイテムがあります。頂点 $i$ にあるアイテムの価値は $V_i$ であり、重さは $W_i$ です。 そこで、次のクエリに $Q$ 回答えてください。

• 二分木の頂点 $v$ 及び正の整数 $L$ が与えられる。 $v$ 及び $v$ の先祖にあるアイテムを、重さの合計が $L$ 以下となるようにいくつか（$0$ 個でもよい）選ぶ。 このとき、選んだアイテムの価値の総和の最大値を求めよ。

ただし、頂点 $u$ が頂点 $v$ の先祖であるとは、頂点 $u$ が頂点 $v$ の間接的な親である、つまり、 $w_1=v$、$w_k=u$、さらに各 $i$ について $w_{i+1}$ が $w_i$ の親となるような頂点の列 $w_1,w_2,\ldots,w_k$ ($k\geqq\ 2$) が存在することを指します。

输入格式

$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$

输出格式

$1$ から $Q$ までの各整数 $i$ について、 $i$ 回目のクエリに対する答えを $i$ 行目に出力せよ。

题目大意

给定一个 $N$ 个节点的二叉树，编号 1 到 $N$，根为 $1$，对于任意一个非根节点 $i$，$i$ 的父亲为 $\lfloor \frac{i}{2}\rfloor$，每一个节点 $j$ 都有一个价值 $V_j$ 和权重 $W_j$.

接下来有 $Q$ 次询问，每次询问给出两个正整数 $v$，$L$，请你在 $v$ 和 $v$ 的祖先中选出若干个(可以为 0 个)节点，使得选出的节点的权重不超过 $L$，求最大能选出的价值。

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

0
3
3

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

256
255
250
247
255
259
223
253

提示

制約

• $1\ \leqq\ N\ <\ 2^{18}$
• $1\ \leqq\ Q\ \leqq\ 10^5$
• $1\ \leqq\ V_i\ \leqq\ 10^5$
• $1\ \leqq\ W_i\ \leqq\ 10^5$
• 各クエリで指定される $v$, $L$ は $1\ \leqq\ v\ \leqq\ N$, $1\ \leqq\ L\ \leqq\ 10^5$ を満たす。
• 入力で与えられる値はすべて整数である。

Sample Explanation 1

最初のクエリでは、選ぶことのできるアイテムは $(V,W)=(1,2)$ なるアイテムのみであるので、 $L=1$ より $1$ つもアイテムを選ぶことができません。 したがって、答えは $0$ になります。 一方で $2$ 番目のクエリでは、選ぶことのできるアイテムは $(V,W)=(1,2)$ なるアイテムと $(V,W)=(2,3)$ なるアイテムの $2$ つであり、 $L=5$ より両方を選ぶことができます。 したがって、答えは $3$ になります。