Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def bisect_left_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番左側のidxとなる。
    '''
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok
def main2():
    n = int(input())
    l=[int(i) for i in input().split()]
    l.sort(reverse = True)
    res = 0
    for i in range(n-1):
        for j in range(i+1, n-1):
            #index がj以降で　k < c を満たすcで一番小さいc'を探す
            #index(c')-j - 1が三角形の条件を満たす
            nibu = l[j+1:]
            k = max(l[i]-l[j],l[j]-l[i])
            left=bisect_left_reverse(nibu,k)
            res += left
    print(res)

if __name__ == '__main__':
    main2()


Fixed submission:
import bisect
def bisect_right_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番右側のidx+1となる。
    '''
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok
def bisect_left_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番左側のidxとなる。
    '''
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok
def main2():
    n = int(input())
    l=[int(i) for i in input().split()]
    l.sort(reverse = True)
    res = 0
    for i in range(n-1):
        for j in range(i+1, n-1):
            #index がj以降で　k < c を満たすcで一番小さいc'を探す
            #index(c')-j - 1が三角形の条件を満たす
            nibu = l[j+1:]
            k = max(l[i]-l[j],l[j]-l[i])
            left=bisect_left_reverse(nibu,k)
            res += left
    print(res)

if __name__ == '__main__':
    main2()
Buggy python submission (verdict: Runtime Error):
n,q=map(int, input().split())
edges = [[]for _ in range(n)]
counter = [0]*n
done = [0]*n

for i in range(n-1):
    a,b=map(int, input().split())
    #頂点a, bのどちらが親か調べる 頂点1が根
    edges[a-1].append(b-1)



for i in range(q):
    a,b=map(int, input().split())
    counter[a-1]+=b

def dfs(i: int):
    for j in edges[i]:
        counter[j]+=counter[i]
        dfs(j)

dfs(0)
print(*counter)


Fixed submission:
from collections import deque
n,q=map(int, input().split())
edges = [[]for _ in range(n)]
counter = [0]*n
visited=[-1]*n
que=deque()

for i in range(n-1):
    a,b=map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)



for i in range(q):
    a,b=map(int, input().split())
    counter[a-1]+=b


que.append(0)
while que:
    v=que.popleft()
    visited[v]=1
    for next_v in edges[v]:
        if visited[next_v]!=-1:continue
        counter[next_v]+=counter[v]
        que.append(next_v)
print(*counter)
Buggy python submission (verdict: Runtime Error):
import collections
def main4():
    dd = collections.defaultdict(int)
    n = int(input())
    res = 0
    for i in range(n):
        s = input()
        s.sort()
        dd[''.join(s)]+=1
    for i in dd.values():
        res += (i*(i-1))//2
    print(res)

if __name__ == '__main__':
    main4()

Fixed submission:
import collections
def main4():
    n = int(input())
    l = []
    for i in range(n):
        s = input()
        l.append((sorted(s)))
    l.sort()
    dd = collections.defaultdict(int)
    k = []
    for i in range(n):
        k.append(''.join(l[i]))
    res = 0
    for i in range(n):
        dd[k[i]]+=1
    for i in dd.values():
        res += (i*(i-1))//2
    print(res)

if __name__ == '__main__':
    main4()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s=input()
    n = len(s)
    dp = [[0]*(13) for _ in range(100005)]
    MOD = 10**9 + 7
    dp[0][0]=1

    for i in range(n):
        c=0
        if(s[i]=="?"):c=-1
        else:c = int(s[i])

        for j in range(10):
            if(c!=-1 and c!=j):
                continue
            for ki in range(13):
                dp[i+1][(ki*10+j)%13] += dp[i][ki]

        for j in range(13):
            dp[i+1][j]%=MOD
    res = dp[n][5]

    print(res)





if __name__ == '__main__':
    main()


Fixed submission:
def main():
    s=input()
    n = len(s)
    dp = [[0]*(13) for _ in range(100005)]
    MOD = 10**9 + 7
    dp[0][0]=1

    for i in range(n):
        c=0
        if(s[i]=="?"):c=-1
        else:c = int(s[i])

        for j in range(10):
            if(c!=-1 and c!=j):
                continue
            for ki in range(13):
                dp[i+1][(ki*10+j)%13] += dp[i][ki]

        for j in range(13):
            dp[i+1][j]%=MOD
    res = dp[n][5]

    print(res)





if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
res_graph = [[1,i] for i in range(2,n+1)]
res = (n-1)*(n-2)//2

if(k > (n-2)*(n-1)//2):
    print(-1)
    exit()

tmp = 1
tmp_edge = 2

while 1:
    if res==k:
        break
    chek = [0]*(n-tmp_edge)
    for i in range(tmp_edge-1,len(chek)+1):
        res_graph.append([tmp_edge, i+tmp_edge])
        res -=1
        if(res==k):
            break
    tmp_edge+=1
    if res==k:
        break

print(len(res_graph))
for i,j in res_graph:
    print(i,j)


Fixed submission:
n,k = map(int,input().split())
res_graph = [[1,i] for i in range(2,n+1)]
res = (n-1)*(n-2)//2

if(k > (n-2)*(n-1)//2):
    print(-1)
    exit()

tmp_edge = 2
while res!=k:
    tmp = 1
    for i in range(n-tmp_edge):
        res_graph.append([tmp_edge,tmp+tmp_edge])
        res-=1
        tmp+=1
        if res==k:
            break
    tmp_edge+=1

print(len(res_graph))
for i,j in res_graph:
    print(i,j)

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
res_graph = [[1,i] for i in range(2,n+1)]
res = (n-1)*(n-2)//2

if(k > (n-2)*(n-1)//2):
    print(-1)
    exit()

tmp = 1
tmp_edge = 2
while 1:
    chek = [0]*(n-tmp_edge)
    for i in range(tmp_edge-1,len(chek)+1):
        res_graph.append([tmp_edge, i+tmp_edge])
        res -=1
        if(res==k):
            break
    tmp_edge+=1
    if res==k:
        break
print(len(res_graph))
for i,j in res_graph:
    print(i,j)


Fixed submission:
n,k = map(int,input().split())
res_graph = [[1,i] for i in range(2,n+1)]
res = (n-1)*(n-2)//2

if(k > (n-2)*(n-1)//2):
    print(-1)
    exit()

tmp_edge = 2
while res!=k:
    tmp = 1
    for i in range(n-tmp_edge):
        res_graph.append([tmp_edge,tmp+tmp_edge])
        res-=1
        tmp+=1
        if res==k:
            break
    tmp_edge+=1

print(len(res_graph))
for i,j in res_graph:
    print(i,j)
Buggy python submission (verdict: Runtime Error):
import heapq
import itertools
def main():
    n,k=map(int, input().split())
    v=[int(i) for i in input().split()]
    #k回Vの両端から取り出したり詰めたりして持ってるものの価値の最大化をする
    v_1 = v[::-1]
    #左から取る回数をA、右から取る回数をBとしたとき、価値が負の宝石を捨てる操作は（k-(A+B)）回できる
    #これを利用して全探索
    res = 0
    for i in range(k+1):
        j = 0
        while(i+j<=k):
            q = []
            tmp = 0
            if(i>0):
                for l in range(i):
                    if(v[l]<0):
                        heapq.heappush(q,v[l])
                    tmp += v[l]
            if(j>0):
                for l in range(j):
                    if(v_1[l]<0):
                        heapq.heappush(q,v_1[l])
                    tmp += v_1[l]
            for l in range(k-(i+j)):
                if(len(q)>0):
                    z = heapq.heappop(q)
                    tmp -= z
            j+=1
            res = max(res,tmp)

    print(res)
if __name__ == '__main__':
    main()


Fixed submission:
import heapq
import itertools
def main():
    n,k=map(int, input().split())
    v=[int(i) for i in input().split()]
    #k回Vの両端から取り出したり詰めたりして持ってるものの価値の最大化をする
    v_1 = v[::-1]
    #左から取る回数をA、右から取る回数をBとしたとき、価値が負の宝石を捨てる操作は（k-(A+B)）回できる
    #これを利用して全探索
    res = 0
    for i in range(k+1):
        j = 0
        while(i+j<=min(n,k)):

            q = []
            tmp = 0
            if(i>0):
                for l in range(i):
                    if(v[l]<0):
                        heapq.heappush(q,v[l])
                    tmp += v[l]
            if(j>0):
                for l in range(j):
                    if(v_1[l]<0):
                        heapq.heappush(q,v_1[l])
                    tmp += v_1[l]
            for l in range(k-(i+j)):
                if(len(q)>0):
                    z = heapq.heappop(q)
                    tmp -= z
            j+=1
            res = max(res,tmp)

    print(res)
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
from operator import itemgetter
import sys
input = sys.stdin.readline
#参考
#https://atcoder.jp/contests/abc128/submissions/15199101
class PseudoSet():
    def __init__(self):
        self.s = []  # set
        self.e = []  # erase candidate

    def insert(self, x):
        heappush(self.s, x)

    def erase(self, x):
        heappush(self.e, x)

    def get_min(self):
        while self.e and self.e[0] == self.s[0]:
            _ = heappop(self.s)
            _ = heappop(self.e)
        return self.s[0] if len(self.s) > 0 else None

def main():
    n,q=map(int, input().split())
    event = []
    end = []
    for i in range(n):
        s,t,x=map(int, input().split())
        event.append([s-x,1,x])
        event.append([t-x,0,x])

    for i in range(q):
        d = int(input())
        event.append([d,2,i])
    event.sort(key = itemgetter(0,1))
    res = [-1]*q
    ps = PseudoSet()
    for time,type,x in event:
        if(type==1):
            ps.insert(x)
        elif(type==0):
            ps.erase(x)
        else:
            k = ps.get_min()
            if k is not None:
                res[x]=k
    print(*res,sep="\n")

if __name__ == '__main__':
    main()


Fixed submission:
from heapq import heappush, heappop
from operator import itemgetter
import sys
input = sys.stdin.readline
#参考
#https://atcoder.jp/contests/abc128/submissions/15199101
class PseudoSet():
    def __init__(self):
        self.s = []  # set
        self.e = []  # erase candidate

    def insert(self, x):
        heappush(self.s, x)

    def erase(self, x):
        heappush(self.e, x)

    def get_min(self):
        while self.e and self.e[0] == self.s[0]:
            _ = heappop(self.s)
            _ = heappop(self.e)
        return self.s[0] if len(self.s) > 0 else None

def main():
    n,q=map(int, input().split())
    event = []
    end = []
    for i in range(n):
        s,t,x=map(int, input().split())
        event.append([s-x,1,x])
        event.append([t-x,0,x])

    for i in range(q):
        d = int(input())
        event.append([d,2,i])
    event.sort(key = itemgetter(0,1))
    res = [-1]*q
    ps = PseudoSet()
    for time,type,x in event:
        if(type==1):
            ps.insert(x)
        elif(type==0):
            ps.erase(x)
        else:
            k = ps.get_min()
            if k is not None:
                res[x]=k
    print(*res,sep="\n")

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
n,m=map(int, input().split())
A=[int(i) for i in input().split()]
A.sort()
bc=[]
for i in range(m):
    b,c=map(int, input().split())
    bc.append([b,c])
bc.sort(key = lambda x:x[1], reverse=True)
count=0
for i in bc:
    for j in range(i[0]):
        if A[count]<i[1]:
            A[count]=i[1]
            count+=1
        else:
            break
        if count==n:
            break
print(sum(A))


Fixed submission:
n,m=map(int, input().split())
A=[int(i) for i in input().split()]
tmp = min(A)
A.sort()
ab=[]
for i in range(m):
    b,c=map(int, input().split())
    if not c<tmp:
        ab.append([b, c])
ab.sort(key=lambda x:x[1], reverse = True)
f=False
a = 0
for i in range(len(ab)):
    for j in range(min(ab[i][0], n)):
        if A[a]>ab[i][1]:
            f=True
            break
        A[a]=ab[i][1]
        a+=1
        if a==n:
            f=True
            break
    if f==True:break
print(sum(A))

Buggy python submission (verdict: Runtime Error):
n,m=map(int, input().split())
A=[int(i) for i in input().split()]
A.sort()
bc=[]
for i in range(m):
    b,c=map(int, input().split())
    bc.append([b,c])
bc.sort(key = lambda x:x[1], reverse=True)
count=0
for i in bc:
    for j in range(i[0]):
        if A[count]<i[1]:
            A[count]=i[1]
            count+=1
        else:
            break
print(sum(A))


Fixed submission:
n,m=map(int, input().split())
A=[int(i) for i in input().split()]
tmp = min(A)
A.sort()
ab=[]
for i in range(m):
    b,c=map(int, input().split())
    if not c<tmp:
        ab.append([b, c])
ab.sort(key=lambda x:x[1], reverse = True)
f=False
a = 0
for i in range(len(ab)):
    for j in range(min(ab[i][0], n)):
        if A[a]>ab[i][1]:
            f=True
            break
        A[a]=ab[i][1]
        a+=1
        if a==n:
            f=True
            break
    if f==True:break
print(sum(A))
Buggy python submission (verdict: Runtime Error):
def main():
    s  = int(input())
    k = s//100
    t = s%100

    if(k>0 and k<13) and (t>0 and t<13):
        res = "AMBIGUOUS"
    elif(k>0 and k<13) and
        res = "MMYY"
    elif(t>0 and t<13):
        res = "YYMM"
    else:
        res = "NA"
    print(res)






if __name__ == '__main__':
    main()


Fixed submission:
def main():
    s  = int(input())
    k = s//100
    t = s%100

    if(k>0 and k<13) and (t>0 and t<13):
        res = "AMBIGUOUS"
    elif(k>0 and k<13):
        res = "MMYY"
    elif(t>0 and t<13):
        res = "YYMM"
    else:
        res = "NA"
    print(res)






if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,n=map(int, input().split())
ans=0

for r in range(n+1):
    if r%R==0:
        for g in range(n+1-r):
            b = n-r-g
            if b%B==0 and r%R==0 and g%G==0:
                ans+=1

print(ans)


Fixed submission:
R,G,B,n=map(int, input().split())
ans=0

for r in range(n+1):
    if r%R==0:
        for g in range(n+1-r):
            b = n-r-g
            if b%B==0 and r%R==0 and g%G==0:
                ans+=1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,n=map(int, input().split())
ans=0

for r in range(n+1):
    for g in range(n+1-r):
        b = n-r-g
        if b%B==0 and r%R==0 and g%G==0:
            ans+=1

print(ans)


Fixed submission:
R,G,B,n=map(int, input().split())
ans=0

for r in range(n+1):
    if r%R==0:
        for g in range(n+1-r):
            b = n-r-g
            if b%B==0 and r%R==0 and g%G==0:
                ans+=1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int, input().split())
s=input()
ans=[]
for i in range(q):
    a,b=map(int, input().split())
    ans.append((s[a-1:b].count("AC")))

for i in ans:
    print(i)


Fixed submission:
n,q=map(int, input().split())
s=input()
sn=""
ans=[0]*(n+1)

for i in range(n):
    if s[i:i+2]=="AC":
        ans[i+1]=ans[i]+1
    else:
        ans[i+1]=ans[i]

for i in range(q):
    a,b=map(int, input().split())
    print(ans[b-1]-ans[a-1])
Buggy python submission (verdict: Runtime Error):
a,b=map(int, input().split())
ans=a
if(b-a==0):
    print(b)
    exit()
#[2, 3, 4]a=2, b=4
#[1, 2, 3]
if(b-a+1)%2==1:#中が奇数こ
    if a%2==0:
        print(b^((b-a)//2)%2)
    else:
        print(a^((b-a)//2)%2)

#[2, 3, 4, 5]
#[1, 2, 3, 4]
else:
    if a%2==1:
        print(a^b^((b-a-1)/2)%2)
    else:
        print(0)


Fixed submission:
def main():
    a,b = map(int, input().split())
    n = (b-a+1)#要素数
    k = n//2

    if n%2==0:
        if a%2==0:
            if k%2==0:
                res = 0
            else:
                res =1
        else:
            k = (n-2)//2
            if k%2 == 1:
                res=(a^b^1)
            else:
                res = a^b
    else:
        if a%2 == 0:
            if k%2 == 0:
                res = (b)
            else:
                res = b^1
        else:
            if k%2==1:
                res = a^1
            else:
                res = a
    print(res)





if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
n,m=map(int, input().split())
x=[int(i) for i in input().split()]
x.sort()
dist = abs(x[-1]-x[0])
diff = []

for i in range(m-1):
    diff.append([abs(x[i]-x[i+1]),i])

diff.sort(key = lambda x:x[0],reverse = True)
for i in range(n-1):
    dist-=diff[i][0]
print(dist)


Fixed submission:
import itertools
n,m=map(int, input().split())
x=[int(i) for i in input().split()]
x.sort()
if(n>=m):
    print(0)
    exit()
dist = abs(x[-1]-x[0])

diff = []

for i in range(m-1):
    diff.append([abs(x[i]-x[i+1]),i])

diff.sort(key = lambda x:x[0],reverse = True)
for i in range(n-1):
    dist-=diff[i][0]
print(dist)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = []
for i in range(n):
  a.append(int(input()%2))
k = sum(a)

if(k%2)or n==2:
  print("first")
else:
  print("second")


Fixed submission:
n = int(input())
f=True
for i in range(n):
  s = int(input())
  if s%2==1:
    f = False 
if not f:
  print("first")
else:
  print("second")

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = []
for i in range(n):
  a.append(int(input()%2))
k = sum(a)
if(k%2):
  print("first")
else:
  print("second")

Fixed submission:
n = int(input())
f=True
for i in range(n):
  s = int(input())
  if s%2==1:
    f = False 
if not f:
  print("first")
else:
  print("second")
Buggy python submission (verdict: Runtime Error):
s = input()
n = int(input())
i = 0
while s[i]=="1":
    if n==i:
        print(1)
        exit()
    i+=1

for i in range(len(s)):
    if s[i]!="1":
        print(s[i])
        exit()


Fixed submission:
s = input()
n = int(input())
i = 0
while s[i]=="1":
    if n==i+1:
        print(1)
        exit()
    i+=1
    if i==len(s):
        break

for i in range(len(s)):
    if s[i]!="1":
        print(s[i])
        exit()
Buggy python submission (verdict: Runtime Error):
h,w = map(int, input().split())

grid = [[str(i) for i in input()]for _ in range(h)]
dxdy = [[1, 0], [0, 1], [-1, 0], [0, -1]]

for i in range(h):
    for j in range(w):
        if grid[i][j]=="#":
            f = False
            for d in dxdy:
                if(i+d[0]>-1 and j+d[1]>-1 and i+d[0]<w and j+d[1]<h):
                    if grid[i+d[0]][j+d[1]]=="#":
                        f = True
                        continue
            if f==False:
                print("No")
                exit()


print("Yes")


Fixed submission:
h,w = map(int, input().split())

grid = [[str(i) for i in input()]for _ in range(h)]
dxdy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for i in range(h):
    for j in range(w):
        if grid[i][j]=="#":
            f = False
            for d in dxdy:
                if(i+d[0]>-1 and j+d[1]>-1 and j+d[1]<w and i+d[0]<h):
                    if grid[i+d[0]][j+d[1]]=="#":
                        f = True
                        continue
            if f==False:
                print("No")
                exit()
print("Yes")

Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())

grid = [[str(i) for i in input()]for _ in range(a)]
dxdy = [[1, 0], [0, 1], [-1, 0], [0, -1]]

for i in range(b):
    for j in range(a):
        if grid[i][j]=="#":
            f = False
            for d in dxdy:
                if(i+d[0]>-1 and j+d[1]>-1 and i+d[0]<b and j+d[1]<a):
                    if grid[i+d[0]][j+d[1]]=="#":
                        f = True
                        continue
            if f==False:
                print("No")
                exit()


print("Yes")


Fixed submission:
h,w = map(int, input().split())

grid = [[str(i) for i in input()]for _ in range(h)]
dxdy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for i in range(h):
    for j in range(w):
        if grid[i][j]=="#":
            f = False
            for d in dxdy:
                if(i+d[0]>-1 and j+d[1]>-1 and j+d[1]<w and i+d[0]<h):
                    if grid[i+d[0]][j+d[1]]=="#":
                        f = True
                        continue
            if f==False:
                print("No")
                exit()
print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations
n,m,r=map(int, input().split())
r_l=[int(i)-1 for i in input().split()]
town = [[0]*n for _ in range(n)]
for i in range(m):
    a,b,c=map(int, input().split())
    town[a-1][b-1]=c
    town[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            town[i][j] = min(town[i][j],town[i][k]+town[k][j])
res = float("INF")
for root in list(permutations(r_l)):
    tmp = 0
    for i in range(1,r):
        tmp += town[root[i]][root[i-1]]
    res = min(tmp,res)

print(res)


Fixed submission:
from itertools import permutations
n,m,r=map(int, input().split())
r_l=[int(i)-1 for i in input().split()]
town = [[float("INF")]*n for _ in range(n)]
for i in range(m):
    a,b,c=map(int, input().split())
    town[a-1][b-1]=c
    town[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            town[i][j] = min(town[i][j],town[i][k]+town[k][j])
res = float("INF")
for root in list(permutations(r_l)):
    tmp = 0
    for i in range(1,r):
        tmp += town[root[i]][root[i-1]]
    res = min(tmp,res)

print(res)
Buggy python submission (verdict: Runtime Error):
n = int(input())
visited = [0]*n
def dfs(edge, dist, k):
    visited[k]=1
    for i in edge[k]:
        if visited[i[0]]==0:
            dist[i[0]]=i[1]+dist[k]
            dfs(edge, dist, i[0])


    return dist
def main():
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a,b,c=map(int, input().split())
        edge[a-1].append([b-1,c])
        edge[b-1].append([a-1,c])

    q,k=map(int, input().split())
    #頂点kから各頂点への距離を最初に求めておくdist[i]:頂点kから頂点iまでの距離　 dist[k]=0
    dist = [0]*n
    visited[k-1]=1
    dist = dfs(edge, dist, k-1)

    res = [0]*q
    for i in range(q):
        x,y=map(int, input().split())
        res[i]=dist[x-1]+dist[y-1]


    for i in range(q):
        print(res[i])
if __name__ == '__main__':
    main()


Fixed submission:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
visited = [0]*n
def dfs(edge, dist, k):
    visited[k]=1
    for i in edge[k]:
        if visited[i[0]]==0:
            dist[i[0]]=i[1]+dist[k]
            dfs(edge, dist, i[0])


    return dist
def main():
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a,b,c=map(int, input().split())
        edge[a-1].append([b-1,c])
        edge[b-1].append([a-1,c])

    q,k=map(int, input().split())
    #頂点kから各頂点への距離を最初に求めておくdist[i]:頂点kから頂点iまでの距離　 dist[k]=0
    dist = [0]*n
    visited[k-1]=1
    dist = dfs(edge, dist, k-1)

    res = [0]*q
    for i in range(q):
        x,y=map(int, input().split())
        res[i]=dist[x-1]+dist[y-1]


    for i in range(q):
        print(res[i])
if __name__ == '__main__':
    main()