Problem:


Score : 700 points

Problem Statement

We have a rooted binary tree with N vertices, where the vertices are numbered 1 to N.
Vertex 1 is the root, and the parent of Vertex i (i \geq 2) is Vertex \left[ \frac{i}{2} \right].

Each vertex has one item in it. The item in Vertex i has a value of V_i and a weight of W_i.
Now, process the following query Q times:

Given are a vertex v of the tree and a positive integer L.
  Let us choose some (possibly none) of the items in v and the ancestors of v so that their total weight is at most L.
  Find the maximum possible total value of the chosen items.

Here, Vertex u is said to be an ancestor of Vertex v when u is an indirect parent of v, that is, there exists a sequence of vertices w_1,w_2,\ldots,w_k (k\geq 2) where w_1=v, w_k=u, and w_{i+1} is the parent of w_i for each i.

Constraints

All values in input are integers.

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

For the values v and L given in each query, 1 \leq v \leq N and 1 \leq L \leq 10^5.

Input

Let v_i and L_i be the values v and L given in the i-th query.
Then, Input is given from Standard Input in the following format:

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

Output

For each integer i from 1 through Q,
the i-th line should contain the response to the i-th query.

Sample Input 1

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

Sample Output 1

0
3
3

In the first query, we are given only one choice: the item with (V, W)=(1,2). Since L = 1, we cannot actually choose it, so our response should be 0.

In the second query, we are given two choices: the items with (V, W)=(1,2) and (V, W)=(2,3). Since L = 5, we can choose both of them, so our response should be 3.

Sample Input 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

Sample Output 2

256
255
250
247
255
259
223
253



Sample input:
3
1 2
2 3
3 4
3
1 1
2 5
3 5


Sample output:
0
3
3

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dp_all(lis, l):
        res = [(0,0)]
        for v,w in lis:
            res += [(sv+v,sw+w) for (sv,sw) in res if sw+w <= l]
        return max(res)[0]

    def array(lis):
        res = [(0,0)]
        for v,w in lis:
            res += [(sw+w,sv+v) for (sw,sv) in res]
        res.sort(key = lambda x:(x[0],-x[1]))
        res_sw = []
        res_sv = []
        maxv = 0
        for i in range(len(res)):
            w,v = res[i]
            if v < maxv:
                continue
            res_sw.append(w)
            res_sv.append(v)
            maxv = v
        return res_sw,res_sv

    def dp(lis, res_sw, res_sv, l):
        liss = [(0,0)]
        for v,w in lis:
            liss += [(sw+w,sv+v) for (sw,sv) in liss if sw+w <= l]
        ans = 0
        for sw,sv in liss:
            j = bisect.bisect_right(res_sw, l-sw)-1
            s = sv+res_sv[j]
            if ans < s:
                ans = s
        return ans

    n = I()
    g = [None]*(n+1)
    for i in range(1,n+1):
        v,w = LI()
        g[i] = (v,w)
    q = I()
    mem_sw = defaultdict(lambda : None)
    mem_sv = defaultdict(lambda : None)
    m = n.bit_length()>>1
    for _ in range(q):
        x,l = LI()
        h = x.bit_length()
        lis = []
        bit = 0
        t = 0
        while x:
            if t+m == h:
                bit = x
            lis.append(g[x])
            x >>= 1
            t += 1
        if h <= m:
            print(dp_all(lis,l))
        else:
            if mem_sw[bit] is None:
                mem_sw[bit],mem_sv[bit] = array(lis[-m:])
            print(dp(lis[:-m],mem_sw[bit],mem_sv[bit],l))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dp_all(lis, l):
        res = [(0,0)]
        for v,w in lis:
            res += [(sv+v,sw+w) for (sv,sw) in res if sw+w <= l]
        return max(res)[0]

    def array(lis):
        res = [(0,0)]
        for v,w in lis:
            res += [(sw+w,sv+v) for (sw,sv) in res]
        res.sort(key = lambda x:(x[0],-x[1]))
        res_sw = []
        res_sv = []
        maxv = 0
        for i in range(len(res)):
            w,v = res[i]
            if v < maxv:
                continue
            res_sw.append(w)
            res_sv.append(v)
            maxv = v
        return res_sw,res_sv

    def dp(lis, res_sw, res_sv, l):
        liss = [(0,0)]
        for v,w in lis:
            liss += [(sw+w,sv+v) for (sw,sv) in liss if sw+w <= l]
        ans = 0
        for sw,sv in liss:
            j = bisect.bisect_right(res_sw, l-sw)-1
            s = sv+res_sv[j]
            if ans < s:
                ans = s
        return ans

    n = I()
    g = [None]*(n+1)
    for i in range(1,n+1):
        v,w = LI()
        g[i] = (v,w)
    q = I()
    mem_sw = defaultdict(lambda : None)
    mem_sv = defaultdict(lambda : None)
    m = n.bit_length()>>1
    for _ in range(q):
        x,l = LI()
        bit = []
        lis = []
        while x:
            bit.append(x)
            lis.append(g[x])
            x >>= 1
        h = len(lis)
        if h < m:
            print(dp_all(lis,l))
        else:
            tu = tuple(bit[-m:])
            if mem_sw[tu] is None:
                mem_sw[tu],mem_sv[tu] = array(lis[-m:])
            print(dp(lis[:-m],mem_sw[tu],mem_sv[tu],l))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dp_all(lis, l):
        res = [(0,0)]
        for v,w in lis:
            res += [(sv+v,sw+w) for (sv,sw) in res if sw+w <= l]
        return max(res)[0]

    def array(lis):
        res = [(0,0)]
        for v,w in lis:
            res += [(sw+w,sv+v) for (sw,sv) in res]
        res.sort(key = lambda x:(x[0],-x[1]))
        _res = []
        maxv = 0
        for i in range(len(res)):
            w,v = res[i]
            if v < maxv:
                continue
            _res.append((w,v))
            maxv = v
        return _res

    def dp(lis, res, l):
        liss = [(0,0)]
        for v,w in lis:
            liss += [(sw+w,sv+v) for (sw,sv) in liss if sw+w <= l]
        liss.sort(key = lambda x:(x[0],-x[1]))
        ans = 0
        pre = (-1,-1)
        for sw,sv in liss:
            if (sw,sv) < pre:
                continue
            pre = (sw,sv)
            res_sw = l-sw
            j = bisect.bisect_left(res, (res_sw, float("inf")))
            res_sv = res[j-1][1]
            s = sv+res_sv
            if ans < s:
                ans = s
        return ans

    n = I()
    g = [None]*(n+1)
    for i in range(1,n+1):
        v,w = LI()
        g[i] = (v,w)
    q = I()
    mem = defaultdict(lambda : None)
    m = n.bit_length()>>1
    for _ in range(q):
        x,l = LI()
        bit = []
        lis = []
        while x:
            bit.append(x)
            lis.append(g[x])
            x >>= 1
        h = len(lis)
        if h < m:
            print(dp_all(lis,l))
        else:
            tu = tuple(bit[-m:])
            if mem[tu] is None:
                mem[tu] = array(lis[-m:])
            print(dp(lis[:-m],mem[tu],l))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dp_all(lis, l):
        res = [(0,0)]
        for v,w in lis:
            res += [(sv+v,sw+w) for (sv,sw) in res if sw+w <= l]
        return max(res)[0]

    def array(lis):
        res = [(0,0)]
        for v,w in lis:
            res += [(sw+w,sv+v) for (sw,sv) in res]
        res.sort(key = lambda x:(x[0],-x[1]))
        _res = []
        maxv = 0
        for i in range(len(res)):
            w,v = res[i]
            if v < maxv:
                continue
            _res.append((w,v))
            maxv = v
        return _res

    def dp(lis, res, l):
        liss = [(0,0)]
        for v,w in lis:
            liss += [(sv+v,sw+w) for (sv,sw) in liss if sw+w <= l]
        ans = 0
        for sv,sw in liss:
            res_sw = l-sw
            j = bisect.bisect_left(res, (res_sw, float("inf")))
            res_sv = res[j-1][1]
            s = sv+res_sv
            if ans < s:
                ans = s
        return ans

    n = I()
    g = [None]*(n+1)
    for i in range(1,n+1):
        v,w = LI()
        g[i] = (v,w)
    q = I()
    mem = defaultdict(lambda : None)
    m = n.bit_length()>>1
    for _ in range(q):
        x,l = LI()
        bit = []
        lis = []
        while x:
            bit.append(x)
            lis.append(g[x])
            x >>= 1
        h = len(lis)
        if h < m:
            print(dp_all(lis,l))
        else:
            tu = tuple(bit[-m:])
            if mem[tu] is None:
                mem[tu] = array(lis[-m:])
            print(dp(lis[:-m],mem[tu],l))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dp_all(lis, l):
        res = 0
        for b in range(1<<len(lis)):
            sv = 0
            sw = 0
            for i,(v,w) in enumerate(lis):
                if (b>>i)&1:
                    sv += v
                    sw += w
                    if sw > l:
                        break
            else:
                if res < sv:
                    res = sv
        return res

    def array(lis):
        res = defaultdict(lambda : 0)
        for b in range(1<<len(lis)):
            sv = 0
            sw = 0
            for i,(v,w) in enumerate(lis):
                if (b>>i)&1:
                    sv += v
                    sw += w
            res[sw] = max(res[sw], sv)
        res = list(res.items())
        res.sort()
        _res = []
        maxv = 0
        for i in range(len(res)):
            w,v = res[i]
            if v < maxv:
                continue
            _res.append((w,v))
            maxv = v
        return _res

    def dp(lis, res, l):
        ret = 0
        for b in range(1<<len(lis)):
            sv = 0
            sw = 0
            for i,(v,w) in enumerate(lis):
                if (b>>i)&1:
                    sv += v
                    sw += w
                    if sw > l:
                        break
            else:
                res_sw = l-sw
                j = bisect.bisect_left(res, (res_sw, float("inf")))
                res_sv = res[j-1][1]
                s = sv+res_sv
                if ret < s:
                    ret = s
        return ret

    n = I()
    g = [None]*(n+1)
    for i in range(1,n+1):
        v,w = LI()
        g[i] = (v,w)
    q = I()
    mem = defaultdict(lambda : None)
    m = n.bit_length()>>1
    for _ in range(q):
        x,l = LI()
        bit = []
        lis = []
        while x:
            bit.append(x)
            lis.append(g[x])
            x >>= 1
        h = len(lis)
        if h < m:
            print(dp_all(lis,l))
        else:
            tu = tuple(bit[-m:])
            if mem[tu] is None:
                mem[tu] = array(lis[-m:])
            print(dp(lis[:-m],mem[tu],l))

    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n = int(input())
    vw = [list(map(int, input().split())) for _ in [0]*n]
    q = int(input())
    vl = [list(map(int, input().split())) for _ in [0]*q]

    former = min(2048, n)
    former_dp = [[-1]*100001 for _ in [0]*former]
    former_set = [set() for _ in [0]*former]

    former_dp[0][0] = 0
    former_dp[0][vw[0][1]] = vw[0][0]
    former_set[0] = {0, vw[0][1]}

    for i in range(1, former):
        v, w = vw[i]
        anc_dp = former_dp[(i-1)//2]
        now_dp = former_dp[i]
        anc_set = former_set[(i-1)//2]
        now_set = former_set[i]
        for j in anc_set:
            now_dp[j] = anc_dp[j]
            now_set.add(j)
        for j in anc_set:
            if w+j <= 100000:
                now_dp[w+j] = max(now_dp[w+j], anc_dp[j]+v)
                now_set.add(w+j)

    for i in range(former):
        m = 0
        now_dp = former_dp[i]
        for j in range(1, 100001):
            m = max(m, now_dp[j])
            now_dp[j] = m

    for v, l in vl:
        if v <= former:
            print(former_dp[v-1][l])
            continue
        later = []
        vv = v
        while vv > former:
            later.append(vw[vv-1])
            vv >>= 1
        anc_dp = former_dp[vv-1]
        m = len(later)
        ans = 0
        for i in range(2**m):
            v_sum, w_sum = 0, 0
            for j, k in later:
                if i & 1:
                    v_sum += j
                    w_sum += k
                i >>= 1
            if w_sum > l:
                continue
            ans = max(ans, v_sum+anc_dp[l-w_sum])
        print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    B = [[int(v) for v in input().split()] for _ in range(N)]
    WV = [None for _ in range(N)]
    Lim = pow(2, 9)
    WV[0] = [(0, 0), (B[0][1], B[0][0])]
    for i in range(1, min(N, Lim)):
        s = set()
        for w, v in WV[(i - 1)//2]:
            s |= {(w, v)}
            if w + B[i][1] <= 10 ** 5: s |= {(w + B[i][1], v + B[i][0])}
        WV[i] = sorted(s)
    
    for i in range(min(N, Lim)):
        for j in range(1, len(WV[i])):
            if WV[i][j-1][1] > WV[i][j][1]: WV[i][j] = (WV[i][j][0], WV[i][j-1][1])
    #print(WV)

    Q = int(input())
    Ans = [0] * Q
    for q in range(Q):
        v, L = map(int, input().split())
        add = dict()
        add[0] = 0
        while v >= Lim:
            s = set()
            for w in add:
                val = add[w]
                if w + B[v-1][1] <= L:
                    s |= {(w+B[v-1][1], val + B[v-1][0])}
            for w, val in s:
                if w in add: add[w] = max(add[w], val)
                else: add[w] = val
            v //= 2
        ans = 0
        le = len(WV[v-1])
        for w in add:
            val = add[w]
            low, high = 0, le
            #print(WV[v-1], low, high, le, v-1)
            while high - low > 1:
                mid = (high + low) // 2
                if WV[v-1][mid][0] + w > L: high = mid
                else: low = mid
            ans = max(ans, val + WV[v-1][low][1])
        Ans[q] = ans

    print(*Ans, sep="\n")

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline

N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[0 for i in range(100001)] for i in range(2**9)]
for i in range(vw[1][1],100001):
    dp[1][i]=vw[1][0]
MAX=min(2**9,N+1)
for i in range(2,MAX):
    v,w=vw[i]
    for j in range(100001):
        dp[i][j]=max(dp[i//2][j],(dp[i//2][j-w]+v)*(j>=w))

temp=[[0,0] for i in range(2**9)]

data=[[] for i in range(N+1)]
last=[-1 for i in range(N+1)]
for i in range(1,N+1):
    id=i
    while id>=2**9:
        data[i].append(vw[id])
        id//=2
    last[i]=id

def solve(v,L):
    n=len(data[v])
    for i in range(1,2**n):
        m=i.bit_length()
        temp[i][0]=temp[i-2**(m-1)][0]+data[v][m-1][0]
        temp[i][1]=temp[i-2**(m-1)][1]+data[v][m-1][1]
    ans=0
    for i in range(2**n):
        if L>=temp[i][1]:
            ans=max(ans,temp[i][0]+dp[last[v]][L-temp[i][1]])
    return ans

for i in range(int(input())):
    v,L=map(int,input().split())
    print(solve(v,L))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
vw=[(0,0)]+[tuple(map(int,input().split())) for i in range(N)]

dp=[[0 for i in range(10**5+5)] for j in range(N+1)]
updated=[0 for i in range(N+1)]

def query(v,L):
  for u in [v//(2**i) for i in range(v.bit_length()-1,-1,-1)]:
    for w in range(updated[u]+1, L+1):
      if vw[u][1] <= w:
        dp[u][w] = max(dp[u//2][w-vw[u][1]] + vw[u][0],dp[u//2][w])
      else:
        dp[u][w] = dp[u//2][w]
    updated[u] = L
  return dp[v][L]

Q=int(input())
for i in range(Q):
  v,L=map(int,input().split())
  print(query(v,L))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
vw=[(0,0)]+[tuple(map(int,input().split())) for i in range(N)]

dp=[[0 for i in range(10**5+5)] for j in range(N+1)]
updated=[0 for i in range(N+1)]

def query(v,L):
  for u in [v//(2**i) for i in range(v.bit_length()-1,-1,-1)]:
    for w in range(updated[u]+1, L+1):
      if dp[u][w] != 0:continue
      if vw[u][1] <= w:
        dp[u][w] = max(dp[u//2][w-vw[u][1]] + vw[u][0],dp[u//2][w])
      else:
        dp[u][w] = dp[u//2][w]
    updated[u] = L
  return dp[v][L]

Q=int(input())
for i in range(Q):
  v,L=map(int,input().split())
  print(query(v,L))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
VW = []
for _ in range(N):
    v,w = map(int,input().split())
    VW.append((v,w))
Q = int(input())

# 深さ9まではDPテーブルで計算　(L_max = 10**5+1)
# 親のDPテーブルから遷移させる
L_max = 10**5+1
N_max = min(1<<10, N)
dp = [[0]*L_max for _ in range(N_max+1)]
for i in range(N_max):
    for j in range(L_max):
        if j>=VW[i][1]:
            dp[i+1][j] = max(dp[(i+1)//2][j], dp[(i+1)//2][j-VW[i][1]]+VW[i][0])
        else:
            dp[i+1][j] = dp[(i+1)//2][j]

def rec(i, tw, tv):
    if tw>L: return 0
    if i==len(weights):
        return tv+dp[v][L-tw]
    ans = 0
    ans = max(ans, rec(i+1, tw, tv))
    ans = max(ans, rec(i+1, tw+weights[i][1], tv+weights[i][0]))
    return ans

Th  = 1<<10
for _ in range(Q):
    v, L = map(int,input().split())
    if v <= Th:
        print(dp[v][L])
        continue
    
    # v>Thの場合，vからThより大きい番号の祖先を使って全列挙
    # 全列挙して，DPテーブルと組み合わせて最大値を計算
    
    ans = 0
    # 末端の要素でリスト生成
    weights = []
    while v>Th:
        weights.append((VW[v-1][0],VW[v-1][1]))
        v >>= 1
    # bit全探索
    print(rec(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
VW = []
for _ in range(N):
    v,w = map(int,input().split())
    VW.append((v,w))
Q = int(input())

# 深さ9まではDPテーブルで計算　(L_max = 10**5+1)
# 親のDPテーブルから遷移させる
L_max = 10**5+1
N_max = min(1<<9, N)
dp = [[0]*L_max for _ in range(N_max+1)]
for i in range(N_max):
    for j in range(L_max):
        if j>=VW[i][1]:
            dp[i+1][j] = max(dp[(i+1)//2][j], dp[(i+1)//2][j-VW[i][1]]+VW[i][0])
        else:
            dp[i+1][j] = dp[(i+1)//2][j]

def rec(i, tw, tv):
    if tw>L: return 0
    if i==len(weights):
        return tv+dp[v][L-tw]
    ans = 0
    ans = max(ans, rec(i+1, tw, tv))
    ans = max(ans, rec(i+1, tw+weights[i][1], tv+weights[i][0]))
    return ans

Th  = 1<<9
for _ in range(Q):
    v, L = map(int,input().split())
    if v <= Th:
        print(dp[v][L])
        continue
    
    # v>Thの場合，vからThより大きい番号の祖先を使って全列挙
    # 全列挙して，DPテーブルと組み合わせて最大値を計算
    
    ans = 0
    # 末端の要素でリスト生成
    weights = []
    while v>Th:
        weights.append((VW[v-1][0],VW[v-1][1]))
        v >>= 1
    # bit全探索
    print(rec(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
VW = [list(map(int,input().split())) for _ in range (N)]
Q = int(input())
vL = [list(map(int,input().split())) for _ in range (Q)]

# 深さ9まではDPテーブルで計算　(L_max = 10**5+1)
# 親のDPテーブルから遷移させる
L_max = 10**5+1
N_max = min(1<<8, N)
dp = [[0]*L_max for _ in range(N_max+1)]
for i in range(N_max):
    for j in range(L_max):
        if j>=VW[i][1]:
            dp[i+1][j] = max(dp[(i+1)//2][j], dp[(i+1)//2][j-VW[i][1]]+VW[i][0])
        else:
            dp[i+1][j] = dp[(i+1)//2][j]

Th  = 1<<8
for v, L in vL:
    if v <= Th:
        print(dp[v][L])
        continue
    # v>Thの場合，vからThより大きい番号の祖先を使って全列挙
    # 全列挙して，DPテーブルと組み合わせて最大値を計算

    ans = 0
    # 末端の要素でリスト生成
    weights = []
    while v>Th:
        weights.append((VW[v-1][0],VW[v-1][1]))
        v >>= 1
    # bit全探索
    for i in range(1<<(len(weights))):
        tw, tv = 0,0
        for j in range(len(weights)):
            if i==0:
                break
            if i&1:
                tw += weights[j][1]
                tv += weights[j][0]
            i >>= 1

        if tw>L:continue
        tv += dp[v][L-tw]
        ans = max(tv, ans)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
VW = [list(map(int,input().split())) for _ in range (N)]
Q = int(input())
vL = [list(map(int,input().split())) for _ in range (Q)]

# 深さ9まではDPテーブルで計算　(L_max = 10**5+1)
# 親のDPテーブルから遷移させる
L_max = 10**5+1
N_max = min(1<<9, N)
dp = [[0]*L_max for _ in range(N_max+1)]
for i in range(N_max):
    for j in range(L_max):
        if j>=VW[i][1]:
            dp[i+1][j] = max(dp[(i+1)//2][j], dp[(i+1)//2][j-VW[i][1]]+VW[i][0])
        else:
            dp[i+1][j] = dp[(i+1)//2][j]

Th  = 1<<9
for v, L in vL:
    if v <= Th:
        print(dp[v][L])
        continue
    # v>Thの場合，vからThより大きい番号の祖先を使って全列挙
    # 全列挙して，DPテーブルと組み合わせて最大値を計算

    ans = 0
    # 末端の要素でリスト生成
    weights = []
    while v>Th:
        weights.append((VW[v-1][0],VW[v-1][1]))
        v >>= 1
    # bit全探索
    for i in range(1<<(len(weights))):
        tw, tv = 0,0
        for j in range(len(weights)):
            if i==0:
                break
            if i&1:
                tw += weights[j][1]
                tv += weights[j][0]
            i >>= 1

        if tw>L:continue
        tv += dp[v][L-tw]
        ans = max(tv, ans)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    n = N.bit_length()
    V = [0]*N; W = [0]*N
    for i in range(N):
        V[i], W[i] = LI()
    q = I()
    Q = [LI()for _ in range(q)]
    ans = [0]*q
    if N<1024:
        S = [[]for _ in range(N)]
        for i in range(N):
            key = i + 1
            cur = []
            while (key > 0):
                cur.append(key-1)
                key //= 2
            dp = {0: 0}
            for loop in range(1 << (len(cur))):
                value, weight = 0, 0
                for j in range(len(cur)):
                    if loop & (1 << j):
                        value += V[cur[j]]
                        weight += W[cur[j]]
                if weight in dp:
                    if dp[weight] < value:
                        dp[weight] = value
                else:
                    dp[weight] = value
            D = sorted(dp.items())
            #print(D)
            now = 0
            for j in range(len(D)):
                if now < D[j][1]:
                    now = D[j][1]
                else:
                    D[j] = [D[j][0],now]
            S[i] = D

        for i,[v,l] in enumerate(Q):
            D = S[v-1]
            for j in range(len(D))[::-1]:
                if D[j][0]<=l:
                    ans[i] = D[j][1]
                    break
        for v in ans:
            print(v)
        return


    half = 1<<9
    S = [[0]*(100001) for _ in range(half)]
    for i in range(half//2,half):
        key = i + 1
        cur = []
        while (key > 0):
            cur.append(key-1)
            key //= 2
        dp = {0: 0}
        for loop in range(1 << (len(cur))):
            value, weight = 0, 0
            for j in range(len(cur)):
                if loop & (1 << j):
                    value += V[cur[j]]
                    weight += W[cur[j]]
            if weight in dp:
                if dp[weight] < value:
                    dp[weight] = value
            else:
                dp[weight] = value
        D = sorted(dp.items())
        now = 0
        for j in range(len(D)):
            if now < D[j][1]:
                now = D[j][1]
            else:
                D[j] = [D[j][0],now]
        now = 0
        j = 0
        for s in range(100001):
            if j<len(D) and s==D[j][0]:
                now = D[j][1]
                j += 1
            S[i][s] = now

    for i,[v,l] in enumerate(Q):
        v -= 1
        key = v + 1
        if key<=512:
            cur = []
            while (key > 0):
                cur.append(key-1)
                key //= 2
            dp = {0: 0}
            for loop in range(1 << (len(cur))):
                value, weight = 0, 0
                for j in range(len(cur)):
                    if loop & (1 << j):
                        value += V[cur[j]]
                        weight += W[cur[j]]
                if weight in dp:
                    if dp[weight] < value:
                        dp[weight] = value
                else:
                    dp[weight] = value
            D = sorted(dp.items())
            if D[j][0] <= l:
                if ans[i]<D[j][1]:
                    ans[i] = D[j][1]
            continue
        cur = []
        while (key > 512):
            cur.append(key-1)
            key //= 2
        dp = {0: 0}
        for loop in range(1 << (len(cur))):
            value, weight = 0, 0
            for j in range(len(cur)):
                if loop & (1 << j):
                    value += V[cur[j]]
                    weight += W[cur[j]]
            if weight in dp:
                if dp[weight] < value:
                    dp[weight] = value
            else:
                dp[weight] = value

        D2 = S[key-1]


    for v in ans:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""

        for weight,value in dp:
            if weight>l:
                continue
            now = l-weight
            if ans[i]<D2[now]+value:
                ans[i] = D2[now]+value
"""