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:
def calc_rec(node):
    if node in D.keys():
        return D[node]

    do_list=[node]
    while True:
        node//=2
        if node in D.keys():
            break
        else:
            do_list.append(node)
    for node in reversed(do_list):
        new_dp =calc_dp_step(node)
    return new_dp


def calc_dp_step(node_id):
    cur_dp = D[node_id//2]
    (node_val,node_weight) = nodes[node_id]

    new_dp=[0]*Vmax
    for j in range(Vmax):
        if j < node_weight: 
            new_dp[j] = cur_dp[j]
        else:
            new_dp[j] = max(cur_dp[j],cur_dp[j-node_weight]+node_val)
    D[node_id]=new_dp
    return new_dp

N = int(input())

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

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

D=dict()
Vmax=10**5+1

#DP[weight]=val
D[0]=[0]*Vmax
Q_ans=dict()
for v,L in query:
    if v in D.keys():
        new_dp = D[v]
    else:
        new_dp = calc_rec(v)

    print(max(D[v][:L+1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
data = list(map(int,read().split()))

V = data[:2*n:2]
W = data[1:2*n:2]
q = data[2*n]
v = data[2*n+1::2]
L = data[2*n+2::2]

if(n==1):
    ans = []
    for i,j in zip(v,L):
        if(W[i-1] <= j):
            ans.append(V[0])
        else:
            ans.append(0)
    print('\n'.join(map(str,ans)))
    exit()

# 前処理　最大2**9まで前計算
b_len = min(9, n.bit_length()-1)
bef = [ [0]*(10**5 + 1) for _ in range(2**b_len)]

for i in range(1,2**b_len):
    iw,iv = W[i-1],V[i-1]
    par = i//2
    for j in range(1,10**5+1):
        bef[i][j] = bef[par][j]
        if(j>=iw):
            bef[i][j] = max(bef[i][j] , bef[par][j-iw]+iv)

ans = []
for vi,Li in zip(v,L):
    if(vi==1):
        if(W[0] <= Li):
            ans.append(V[0])
        else:
            ans.append(0)
        continue

    aft = [(0,0)]
    x = vi
    while(x >= 2**b_len):
        xw,xv = W[x-1],V[x-1]
        aft2 = aft[::]
        for jw,jv in aft:
            aft2.append((xw+jw,xv+jv))
        x //= 2
        aft = aft2[::]

    max_ans = 0
    for aw,av in aft:
        lim_w = Li - aw
        if(lim_w < 0):
            continue
        max_ans = max(max_ans, bef[x][lim_w]+av)

    ans.append(max_ans)

print('\n'.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys
input = sys.stdin.readline
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

def knapsack(W,wt,val,n): 
	K = [[0 for x in range(W + 1)] for x in range(n + 1)] 
	for i in range(1,n+1): 
		for w in range(1,W+1): 
			if wt[i] <= w: 
				K[i][w] = max(val[i] + K[i//2][w-wt[i]], K[i//2][w]) 
			else: 
				K[i][w] = K[i//2][w] 
	return K

n = inp()
v = [0]*(n+1)
w = [0]*(n+1)
for i in range(1,n+1):
    v[i],w[i] = ip()
q = inp()
ver,L = [0]*q,[0]*q
mx = 0
for i in range(q):
    ver[i],L[i] = ip()
K = knapsack(max(L),w,v,max(ver))
for i in range(q):
    print(K[ver[i]][L[i]])

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    input = sys.stdin.readline

    n = int(input())
    items = [tuple(map(int, input().split())) for _ in range(n)]

    q = int(input())
    v_to_il = [[] for _ in range(n)]
    flag = [False] * n
    for i in range(q):
        v, l = map(int, input().split())
        v -= 1
        v_to_il[v].append((i, l))
        flag[v] = True
        while v > 0:
            v = (v - 1) // 2
            if flag[v]:
                break
            flag[v] = True

    MAX = 10**5
    # dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
    dp = [[0] * (MAX + 1) for _ in range(19)]
    ans = [0] * q

    queue = [(0, 0, [])]
    while queue:
        v, depth, items_sub = queue.pop()
        val, w = items[v]

        if depth < 10:
            for j in range(MAX + 1):
                if j < w:
                    dp[depth + 1][j] = dp[depth][j]
                else:
                    dp[depth + 1][j] = max(dp[depth][j],
                                           dp[depth][j - w] + val)
        else:
            items_sub.append((val, w))

        if len(v_to_il[v]) > 0:
            if depth < 10:
                for i, l in v_to_il[v]:
                    ans[i] = dp[depth + 1][l]
            else:
                cand = 0
                m = len(items_sub)
                for bit in range(1 << m):
                    s_val = s_w = 0
                    for i, (val, w) in enumerate(items_sub):
                        if (bit >> i) & 1:
                            s_val += val
                            s_w += w
                    for i, l in v_to_il[v]:
                        if s_w <= l:
                            ans[i] = max(ans[i], dp[10][l - s_w] + s_val)

        if v * 2 + 1 < n and flag[v * 2 + 1]:
            queue.append((v * 2 + 1, depth + 1, items_sub))
        if v * 2 + 2 < n and flag[v * 2 + 2]:
            queue.append((v * 2 + 2, depth + 1, items_sub))

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
data = list(map(int,read().split()))

V = data[:2*n:2]
W = data[1:2*n:2]
q = data[2*n]
v = data[2*n+1::2]
L = data[2*n+2::2]

if(n==1):
    ans = []
    for i,j in zip(v,L):
        if(W[i-1] <= j):
            ans.append(V[0])
        else:
            ans.append(0)
    print('\n'.join(map(str,ans)))
    exit()

# 前処理　最大2**9まで前計算
b_len = min(8, n.bit_length()-1)
bef = [ [0]*(10**5 + 1) for _ in range(2**b_len)]

for i in range(1,2**b_len):
    iw,iv = W[i-1],V[i-1]
    par = i//2
    for j in range(1,10**5+1):
        bef[i][j] = bef[par][j]
        if(j>=iw):
            bef[i][j] = max(bef[i][j] , bef[par][j-iw]+iv)

ans = []
for vi,Li in zip(v,L):
    if(vi==1):
        if(W[0] <= Li):
            ans.append(V[0])
        else:
            ans.append(0)
        continue

    aft = [(0,0)]
    x = vi
    while(x >= 2**b_len):
        xw,xv = W[x-1],V[x-1]
        aft2 = aft[::]
        for jw,jv in aft:
            aft2.append((xw+jw,xv+jv))
        x //= 2
        aft = aft2[::]

    max_ans = 0
    for aw,av in aft:
        lim_w = Li - aw
        if(lim_w < 0):
            continue
        max_ans = max(max_ans, bef[x][lim_w]+av)

    ans.append(max_ans)

print('\n'.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from operator import itemgetter
from bisect import bisect_left

n = int(readline())
g = []
for i in range(n):
  v,w = map(int,readline().split())
  g.append((v,w))
  
q = int(readline())
for i in range(q):
  p,w_max = map(int,readline().split())
  V = []
  W = []
  N = 0
  while p > 0:
    a,b = g[p-1]
    V.append(a); W.append(b)
    N += 1
    p //= 2
  left = [(0,0)] # weight, value
  right = [(0,0)]
  for i in range(N//2):
    left += [(x+W[i],y+V[i]) for x,y in left]
  for i in range(N//2,N):
    right += [(x+W[i],y+V[i]) for x,y in right]
  left.sort() # 重さ順
  right.sort()
  def remove_worthless(li):
    temp = []
    current_value = -1
    for w,v in li:
      if w > w_max:
        break
      # valueを更新したものに制限
      if v > current_value:
        current_value = v
        temp.append((w,v))
    return temp
  left = remove_worthless(left)
  right = remove_worthless(right)
  INF = 10**10
  right.append((INF,0))
  j = 0
  x = 0
  for wL,vL in left[::-1]:
    wR_max = w_max-wL
    while right[j+1][0] <= wR_max:
      j += 1
    vLR = vL + right[j][1]
    if x < vLR:
      x = vLR
  print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
import numpy as np


def dfs(u, dp):
    global n, ans
    if u > n:
        return
    r = required[u]
    if r == -1:
        return
    v = vvv[u]
    w = www[u]
    ndp = dp.copy()
    ndp[w:] = np.maximum(dp[w:], dp[:-w] + v)

    if u in query_ls:
        for l in query_ls[u]:
            a = ndp[l]
            for i in query_idx[u, l]:
                ans[i] = a

    dfs(u << 1, ndp)
    dfs((u << 1) + 1, ndp)


n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]
mp = iter(inp[n * 2 + 1:])
query_ls = defaultdict(list)
query_idx = defaultdict(list)
required = [-1] * (n + 1)
max_l = 0
for i, q in enumerate(zip(mp, mp)):
    u, l = q
    query_idx[q].append(i)
    query_ls[u].append(l)
    max_l = max(max_l, l)
    while u > 0:
        if required[u] >= l:
            break
        required[u] = l
        u >>= 1

ans = [0] * inp[n * 2]
dp = np.zeros(max_l + 1, np.int64)
dfs(1, dp)

print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import numba

@numba.njit("i8[:,:](i8[:,:],i8)", cache=True)
def make(S, W):
    T = {0: 0}
    for i in range(len(S)):
        v = S[i][0]
        w = S[i][1]
        # 価値v, 重さw
        T0 = T.copy()
        T_list = list(T.items())
        for j in range(len(T)):
            k = T_list[j][0]
            val = T_list[j][1]
            if k+w > W:
                continue
            if k+w in T0:
                if val+v > T0[k+w]:
                    T0[k+w] = val + v
            else:
                T0[k+w] = val + v
        T = T0
    v = 0
    R = [(0,0)]*0
    T = np.array(list(T.items()), dtype=np.int64)
    T = T[np.argsort(T[:, 0])]
    for i in range(len(T)):
        k = T[i][0]
        Tk = T[i][1]
        if Tk > v:
            v = Tk
        # (重さk, 重さk以下での価値の最大v)
        R.append((k, v))
    return np.array(R, dtype=np.int64)

@numba.njit("i8(i8[:,:],i8[:,:],i8)", cache=True)
def solve_(T0, T1, W):
    T0 = T0[np.argsort(T0[:, 0])]
    T1 = T1[np.argsort(T1[:, 0])]
    T1 = T1[::-1]
    
    idx_T0 = 0
    idx_T1 = 0
    k1, v1 = T1[idx_T1][0], T1[idx_T1][1]
    ma = 0
    for idx_T0 in range(len(T0)):
        k0, v0 = T0[idx_T0][0], T0[idx_T0][1]
        # 重さの和がW以下になるようにスライドする
        while k0 + k1 > W and idx_T1+1 < len(T1):
            idx_T1 += 1
            k1, v1 = T1[idx_T1][0], T1[idx_T1][1]
        if v0+v1 > ma and k0 + k1 <= W:
            ma = v0+v1
    return ma

@numba.njit("i8(i8,i8,i8[:,:])", cache=True)
def solve(N, W, S):
    # S[i] = (v, w): 価値v, 重さw
    
    if N==1:
        return S[0][0] if S[0][1] <= W else 0

    
    # ２つの集合に分けて、それぞれ全列挙
    T0 = make(S[:N//2], W)
    T1 = make(S[N//2:], W)

    # 2つの全列挙を元に解を求める
    return solve_(T0, T1, W)

def main():
    input = sys.stdin.readline
    N = int(input())
    VW = np.array([[0,0]] + [list(map(int, input().split())) for _ in range(N)])
    Q = int(input())
    Ans = []
    for _ in range(Q):
        V, L = map(int, input().split())
        Idx = []
        while V > 0:
            Idx.append(V)
            V //= 2
        vw = VW[Idx]
        ans = solve(len(vw), L, vw)
        Ans.append(int(ans))
    print("\n".join(map(str, Ans)))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import numba

@numba.njit("i8[:,:](i8[:,:],i8)", cache=True)
def make(S, W):
    T = {0: 0}
    for i in range(len(S)):
        v = S[i][0]
        w = S[i][1]
        # 価値v, 重さw
        T0 = T.copy()
        T_list = list(T.items())
        for j in range(len(T)):
            k = T_list[j][0]
            val = T_list[j][1]
            if k+w > W:
                continue
            if k+w in T0:
                if val+v > T0[k+w]:
                    T0[k+w] = val + v
            else:
                T0[k+w] = val + v
        T = T0
    v = 0
    R = [(0,0)]*0
    T = np.array(list(T.items()), dtype=np.int64)
    T = T[np.argsort(T[:, 0])]
    for i in range(len(T)):
        k = T[i][0]
        Tk = T[i][1]
        if Tk > v:
            v = Tk
        # (重さk, 重さk以下での価値の最大v)
        R.append((k, v))
    return np.array(R, dtype=np.int64)

@numba.njit("i8(i8[:,:],i8[:,:],i8)", cache=True)
def solve_(T0, T1, W):
    T0 = T0[np.argsort(T0[:, 0])]
    T1 = T1[np.argsort(T1[:, 0])]
    T1 = T1[::-1]
    
    idx_T0 = 0
    idx_T1 = 0
    k1, v1 = T1[idx_T1][0], T1[idx_T1][1]
    ma = 0
    for idx_T0 in range(len(T0)):
        k0, v0 = T0[idx_T0][0], T0[idx_T0][1]
        # 重さの和がW以下になるようにスライドする
        while k0 + k1 > W and idx_T1+1 < len(T1):
            idx_T1 += 1
            k1, v1 = T1[idx_T1][0], T1[idx_T1][1]
        if v0+v1 > ma and k0 + k1 <= W:
            ma = v0+v1
    return ma

@numba.njit("i8(i8,i8,i8[:,:])")
def solve(N, W, S):
    # S[i] = (v, w): 価値v, 重さw
    
    if N==1:
        return S[0][0] if S[0][1] <= W else 0

    
    # ２つの集合に分けて、それぞれ全列挙
    T0 = make(S[:N//2], W)
    T1 = make(S[N//2:], W)

    # 2つの全列挙を元に解を求める
    return solve_(T0, T1, W)

def main():
    input = sys.stdin.readline
    N = int(input())
    VW = np.array([[0,0]] + [list(map(int, input().split())) for _ in range(N)])
    Q = int(input())
    Ans = []
    for _ in range(Q):
        V, L = map(int, input().split())
        Idx = []
        while V > 0:
            Idx.append(V)
            V //= 2
        vw = VW[Idx]
        ans = solve(len(vw), L, vw)
        Ans.append(int(ans))
    print("\n".join(map(str, Ans)))

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    M = 2**9
    N = int(input())
    V = []
    W = []
    for i in range(N):
        v,w = map(int,input().split())
        V.append(v)
        W.append(w)

    dp = [[0]*(10**5+1) for _ in range(min(M,N+1))]

    for n in range(1,min(M,N+1)):
        for l in range(10**5+1):
            c = 0
            if l>=W[n-1]:
                c = dp[n//2][l-W[n-1]]+V[n-1]
            dp[n][l] = max(dp[n//2][l],c)
    for n in range(min(M,N+1)):
        for l in range(1,10**5+1):
            dp[n][l] = max(dp[n][l],dp[n][l-1])

    def cal(n,l):
        if n < M:
            return dp[n][l]
        else:
            v = []
            while n >= M:
                v.append(n)
                n //= 2
            m = len(v)
            res = dp[v[-1]//2][l]
            for n in range(2**m):
                v_tot = 0
                w_tot = 0
                for k in range(m):
                    if 2**k&n==2**k:
                        v_tot += V[v[k]-1]
                        w_tot += W[v[k]-1]
                if w_tot <= l:
                    res = max(res,v_tot+dp[v[-1]//2][l-w_tot])
            return res

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

    for i in range(Q):
        v,L = vL[i]
        print(cal(v,L))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import numba

#@numba.njit("i8(i8,i8,i8[:,:])")

@numba.njit("i8[:,:](i8[:,:],i8)", cache=True)
def make(S, W):
    T = {0: 0}
    for i in range(len(S)):
        v = S[i][0]
        w = S[i][1]
        # 価値v, 重さw
        T0 = T.copy()
        T_list = list(T.items())
        for j in range(len(T)):
            k = T_list[j][0]
            val = T_list[j][1]
            if k+w > W:
                continue
            if k+w in T0:
                if val+v > T0[k+w]:
                    T0[k+w] = val + v
            else:
                T0[k+w] = val + v
        T = T0
    v = 0
    R = [(0,0)]*0
    T = np.array(list(T.items()), dtype=np.int64)
    T = T[np.argsort(T[:, 0])]
    for i in range(len(T)):
        k = T[i][0]
        Tk = T[i][1]
        if Tk > v:
            v = Tk
        # (重さk, 重さk以下での価値の最大v)
        R.append((k, v))
    return np.array(R, dtype=np.int64)

@numba.njit("i8(i8[:,:],i8[:,:],i8)", cache=True)
def solve_(T0, T1, W):
    T0 = T0[np.argsort(T0[:, 0])]
    T1 = T1[np.argsort(T1[:, 0])]
    T1 = T1[::-1]
    
    idx_T0 = 0
    idx_T1 = 0
    k1, v1 = T1[idx_T1][0], T1[idx_T1][1]
    ma = 0
    for idx_T0 in range(len(T0)):
        k0, v0 = T0[idx_T0][0], T0[idx_T0][1]
        # 重さの和がW以下になるようにスライドする
        while k0 + k1 > W and idx_T1+1 < len(T1):
            idx_T1 += 1
            k1, v1 = T1[idx_T1][0], T1[idx_T1][1]
        if v0+v1 > ma and k0 + k1 <= W:
            ma = v0+v1
    return ma

def solve(N, W, S):
    # S[i] = (v, w): 価値v, 重さw
    
    if N==1:
        return S[0][0] if S[0][1] <= W else 0

    
    # ２つの集合に分けて、それぞれ全列挙
    T0 = make(np.array(S[:N//2], dtype=np.int64), W)
    T1 = make(np.array(S[N//2:], dtype=np.int64), W)

    # 2つの全列挙を元に解を求める
    return solve_(T0, T1, W)

def main():
    #input = sys.stdin.readline
    N = int(input())
    VW = np.array([[0,0]] + [list(map(int, input().split())) for _ in range(N)])
    Q = int(input())
    Ans = []
    for _ in range(Q):
        V, L = map(int, input().split())
        Idx = []
        while V > 0:
            Idx.append(V)
            V //= 2
        vw = VW[Idx]
        ans = solve(len(vw), L, vw)
        Ans.append(int(ans))
    print("\n".join(map(str, Ans)))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n = int(input())
vw = [list(map(int, input().split())) for i in range(n)]
q = int(input())
vl = [list(map(int, input().split())) for i in range(q)]

ans = [0]*q

top = set()
mid = set()

m = 12

for v,l in vl:
    if v < 1<<(m-1):
        top.add(v)
    elif v < 1<<m:
        mid.add(v)
    else:
        while 1<<m <= v:
            v //= 2
        mid.add(v)

def get_parents(node,end=0):
    a = []
    while node > end:
        a.append(vw[node-1])
        node //= 2
    return a

max_l = 10**5
def knapsack(vw_list, l, l_list=[0]*(max_l+1),):
    x = len(vw_list)
    ret = 0
    for i in range(x):
        for state in range(1<<x):
            v_sum = 0
            w_sum = 0
            for j in range(x):
                if state & 1<<j:
                    v_sum += vw_list[j][0]
                    w_sum += vw_list[j][1]
                if w_sum > l:
                    break
            if w_sum > l:
                continue
            res = l-w_sum
            ret = max(ret, v_sum + l_list[res])
    return ret

def knapsack_mid(vw_list):
    x = len(vw_list)
    ret = [0]*(max_l+1)
    for i in range(x):
        for state in range(1<<x):
            v_sum = 0
            w_sum = 0
            for j in range(x):
                if state & 1<<j:
                    v_sum += vw_list[j][0]
                    w_sum += vw_list[j][1]
                if w_sum > max_l:
                    break
            if w_sum > max_l:
                continue
            if ret[w_sum] < v_sum:
                ret[w_sum] = v_sum
            #ret[w_sum] = max(ret[w_sum], v_sum)
    return ret

d = dict()
for v in mid:
    a = get_parents(v)
    b = knapsack_mid(a)
    for i in range(max_l):
        if b[i] > b[i+1]:
            b[i+1] = i
    d[v] = b

for i, (v,l) in enumerate(vl):
    if v in top:
        a = get_parents(v)
        ans[i] = knapsack(a,l)
    elif v in mid:
        ans[i] = d[v][l]
    else:
        vv = v
        while 1<<m <= vv:
            vv //=2
        a = get_parents(v, end=vv)
        ans[i] = knapsack(a, l, l_list=d[vv])

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

Submission status: Time Limit Exceeded

Solution code:
def linked_merge_sort(l): #マージソート
    if len(l) == 1:
        return
    q, r = divmod(len(l), 2)
    left = [l.pop() for _ in range(q)]
    right = [l.pop() for _ in range(q + r)]
    
    linked_merge_sort(left)
    linked_merge_sort(right)
    
    left.reverse()
    right.reverse()
    while left and right:
        if left[-1] <= right[-1]:
            l.append(left.pop())
        else:
            l.append(right.pop())
    while left:
        l.append(left.pop())
    while right:
        l.append(right.pop())
    return

n=int(input())
v=[0]*(n+1)
w=[0]*(n+1)
for i in range(1,n+1):
    v[i],w[i]=map(int,input().split())
q=int(input())
for i in range(q):
    r,l=map(int,input().split())
    x=[[0 for j in range(2)]]
    while r>0:
        x.append([v[r],w[r]])
        r = int(r//2)
    m = len(x)
    y=[]

    for i in range(2 ** m):
        va = 0
        wa = 0
        for j in range(m):
            if ((i >> j) & 1):
                va += x[j][0] 
                wa += x[j][1]
        if (wa <= l):
            y.append(va)
    linked_merge_sort(y)
    print(y[len(y)-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import numba

#@numba.njit("i8(i8,i8,i8[:,:])")

@numba.njit("i8[:,:](i8[:,:],i8)", cache=True)
def make(S, W):
    T = {0: 0}
    for i in range(len(S)):
        v = S[i][0]
        w = S[i][1]
        # 価値v, 重さw
        T0 = T.copy()
        T_list = list(T.items())
        for j in range(len(T)):
            k = T_list[j][0]
            val = T_list[j][1]
            if k+w > W:
                continue
            if k+w in T0:
                if val+v > T0[k+w]:
                    T0[k+w] = val + v
            else:
                T0[k+w] = val + v
        T = T0
    v = 0
    R = [(0,0)]*0
    T = np.array(list(T.items()), dtype=np.int64)
    T = T[np.argsort(T[:, 0])]
    for i in range(len(T)):
        k = T[i][0]
        Tk = T[i][1]
        if Tk > v:
            v = Tk
        # (重さk, 重さk以下での価値の最大v)
        R.append((k, v))
    return np.array(R, dtype=np.int64)

@numba.njit("i8(i8[:,:],i8[:,:],i8)", cache=True)
def solve_(T0, T1, W):
    T0 = T0[np.argsort(T0[:, 0])]
    T1 = T1[np.argsort(T1[:, 0])]
    T1 = T1[::-1]
    
    idx_T0 = 0
    idx_T1 = 0
    k1, v1 = T1[idx_T1][0], T1[idx_T1][1]
    ma = 0
    for idx_T0 in range(len(T0)):
        k0, v0 = T0[idx_T0][0], T0[idx_T0][1]
        # 重さの和がW以下になるようにスライドする
        while k0 + k1 > W and idx_T1+1 < len(T1):
            idx_T1 += 1
            k1, v1 = T1[idx_T1][0], T1[idx_T1][1]
        if v0+v1 > ma and k0 + k1 <= W:
            ma = v0+v1
    return ma

def solve(N, W, S):
    # S[i] = (v, w): 価値v, 重さw
    
    if N==1:
        return S[0][0] if S[0][1] <= W else 0

    
    # ２つの集合に分けて、それぞれ全列挙
    T0 = make(np.array(S[:N//2], dtype=np.int64), W)
    T1 = make(np.array(S[N//2:], dtype=np.int64), W)

    # 2つの全列挙を元に解を求める
    return solve_(T0, T1, W)

def main():
    #input = sys.stdin.readline
    N = int(input())
    VW = [0] + [list(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    Ans = []
    for _ in range(Q):
        V, L = map(int, input().split())
        vw = []
        while V > 0:
            vw.append(VW[V])
            V //= 2
        ans = solve(len(vw), L, vw)
        Ans.append(int(ans))
    print("\n".join(map(str, Ans)))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
M = 10 ** 5 + 1
K = 9
A = [(0, 0)] * max(N + 1, 1 << K)
X = [[], [-1] * M]
X[1][0] = 0
v, w = map(int, input().split())
X[1][w] = v
A[1] = (v, w)
for i in range(2, min(N + 1, 1 << K)):
    v, w = map(int, input().split())
    if i % 2 == 0:
        X.append(X[i // 2][:])
    else:
        X.append([])
        X[i] = X[i // 2]
    
    for j in range(w, M)[::-1]:
        if X[i][j-w] >= 0:
            X[i][j] = max(X[i][j], X[i][j-w] + v)
    
    A[i] = (v, w)

for i in range(1 << K, N + 1):
    v, w = map(int, input().split())
    A[i] = (v, w)

if len(X) < 1 << K:
    for i in range(len(X), 1 << K):
        X.append([-1] * M)

for i in range(1 << K - 1, 1 << K):
    for j in range(1, M):
        X[i][j] = max(X[i][j], X[i][j-1])

Q = int(input())
for _ in range(Q):
    i, maw = map(int, input().split())
    if i < 1 << K - 1:
        V = []
        W = []
        while i:
            v, w = A[i]
            V.append(v)
            W.append(w)
            i //= 2
        k = len(V)
        ma = 0
        WW = [0] * (1 << k)
        VV = [0] * (1 << k)
        for i in range(1, 1 << k):
            a = i & (-i)
            b = a.bit_length() - 1
            ww = WW[i-a] + W[b]
            WW[i] = ww
            if ww > maw: continue
            vv = VV[i-a] + V[b]
            VV[i] = vv
            ma = max(ma, vv)
        print(ma)
    else:
        V = []
        W = []
        while i >= 1 << K:
            v, w = A[i]
            V.append(v)
            W.append(w)
            i //= 2
        ii = i
        k = len(V)
        WW = [0] * (1 << k)
        VV = [0] * (1 << k)
        ma = X[ii][maw]
        for i in range(1, 1 << k):
            a = i & (-i)
            b = a.bit_length() - 1
            ww = WW[i-a] + W[b]
            WW[i] = ww
            if ww > maw: continue
            vv = VV[i-a] + V[b]
            VV[i] = vv
            ma = max(ma, X[ii][maw - ww] + vv)
        print(ma)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
lines = sys.stdin.readlines()

N = int(lines[0])
Q = int(lines[N+1])
vL = [list(map(int,s.split())) for s in lines[N+2:]]
vs,Ls = zip(*vL)
VW = {}

appear = []
for v in vs:
    v *= 2
    while v:
        v //= 2
        appear.append(v)

appear = list(set(appear))
M = len(appear)+1
dic = {v:i for i,v in enumerate(appear)}

for v in appear:
    VW[dic[v]] = list(map(int, lines[v].split()))

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

maxL = max(Ls)
dp = np.array(dpinit((M+1,maxL+2),0), dtype=np.int)
ans = []

visited = [False] * (M+1)
visited[0] = True
for v,L in vL:
    orgv = v
    seq = []
    v *= 2
    while v:
        v //= 2
        seq.append(v)
        rv = dic[v]
        if visited[rv]:
            break
        visited[rv] = True
    seq = seq[::-1]
    for s,ns in zip(seq,seq[1:]):
        s = dic[s]
        ns = dic[ns]
        V,W = VW[ns]
        for i in range(W):
            dp[ns][i] = dp[s][i]
        for i in range(W,maxL+2):
            dp[ns][i] = max(dp[s][i], dp[s][i-W] + V)
        temp = np.zeros(maxL+2,dtype=int)
        temp[W:] = dp[s][:maxL+2-W]+V
        dp[ns] = np.max((dp[s], temp),axis=0)
    ans.append(dp[dic[orgv]][L])

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys, math, bisect
sys.setrecursionlimit(300000)


def solve(N: int, V: "List[int]", W: "List[int]", Q: int, VV: "List[int]", LL: "List[int]"):
    d = int(math.log(N, 2)) + 1
    #print(d)
    hd = d // 2
    max_m = 2 ** (d // 2) - 1
    dp = [{} for _ in range(max_m + 1)]
    dp[0] = {0: 0}
    for i in range(max_m):
        v, w = V[i], W[i]
        idx = i + 1
        par = idx // 2
        for ww, vv in dp[par].items():
            dp[idx][ww] = dp[par][ww]
        for ww, vv in dp[par].items():
            if ww + w in dp[idx]:
                dp[idx][ww + w] = max(dp[idx][ww + w], dp[par][ww] + v)
            else:
                dp[idx][ww + w] = dp[par][ww] + v
    items = []
    for i in range(max_m + 1):
        tmp = list(dp[i].items())
        tmp.sort()
        max_v = 0
        hoge = []
        for ww, vv in tmp:
            max_v = max(max_v, vv)
            hoge.append((ww, max_v))
        items.append(hoge)

    #print(dp)
    #print(items)

    for q in range(Q):
        ret = 0
        idx, l = VV[q], LL[q]
        pre = {0: 0}
        while idx > max_m:
            w, v = W[idx - 1], V[idx - 1]
            cur = {ww: vv for ww, vv in pre.items()}
            for ww, vv in pre.items():
                if ww + w in cur:
                    cur[ww + w] = max(cur[ww + w], cur[ww] + v)
                else:
                    cur[ww + w] = cur[ww] + v
            pre = cur
            idx //= 2
        #print(pre, items[idx], l)
        for ww, vv in pre.items():
            if l < ww:
                continue
            max_l = l - ww
            x = bisect.bisect_right(items[idx], (max_l, float('inf')))
            if x < 1:
                vvv = 0
            else:
                vvv = items[idx][x - 1][1]
            ret = max(ret, vv + vvv)
            #print(ww, vv, max_l, x, vvv, ret)
        print(ret)
        #print(' ************* ')
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    V = [int()] * (N)  # type: "List[int]"
    W = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        V[i] = int(next(tokens))
        W[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    v = [int()] * (Q)  # type: "List[int]"
    L = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        v[i] = int(next(tokens))
        L[i] = int(next(tokens))
    solve(N, V, W, Q, v, L)

if __name__ == '__main__':
    main()