Problem:


Score : 400 points

Problem Statement

You are given a tree with N vertices.

Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N-1 edges, where N is the number of its vertices.

The i-th edge (1≤i≤N-1) connects Vertices a_i and b_i, and has a length of c_i.

You are also given Q queries and an integer K. In the j-th query (1≤j≤Q):

find the length of the shortest path from Vertex x_j and Vertex y_j via Vertex K.

Constraints

3≤N≤10^5 

1≤a_i,b_i≤N (1≤i≤N-1) 

1≤c_i≤10^9 (1≤i≤N-1) 

The given graph is a tree.

1≤Q≤10^5 

1≤K≤N 

1≤x_j,y_j≤N (1≤j≤Q) 

x_j≠y_j (1≤j≤Q) 

x_j≠K,y_j≠K (1≤j≤Q) 

Input

Input is given from Standard Input in the following format:  

N  
a_1 b_1 c_1  
:  
a_{N-1} b_{N-1} c_{N-1}
Q K
x_1 y_1
:  
x_{Q} y_{Q}

Output

Print the responses to the queries in Q lines.

In the j-th line j(1≤j≤Q), print the response to the j-th query.

Sample Input 1

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

Sample Output 1

3
2
4

The shortest paths for the three queries are as follows:

Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3 

Query 2: Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2 

Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4 

Sample Input 2

7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7

Sample Output 2

5
14
22

The path for each query must pass Vertex K=2.

Sample Input 3

10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10

Sample Output 3

17000000000



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


Sample output:
3
2
4

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            index=0
            a,b,c=(ls[i]+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True


## Segment Tree ##

## Initializer Template ##
# Range Sum:        sg=SegTree(n)
# Range Minimum:    sg=SegTree(n,inf,min,inf)

class SegTree:

    def __init__(self,n,init_val=0,function=lambda a,b:a+b,ide=0):
        self.n=n
        self.ide_ele=ide_ele=ide
        self.num=num=2**(n-1).bit_length()
        self.seg=seg=[self.ide_ele]*2*self.num
        self.lazy=lazy=[self.ide_ele]*2*self.num
        self.segfun=segfun=function
        #set_val
        for i in range(n):
            self.seg[i+self.num-1]=init_val
        #built
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.segfun(self.seg[2*i+1],self.seg[2*i+2])
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfun(self.seg[k*2+1],self.seg[k*2+2])
        
        
    def evaluate(k,l,r): #遅延評価処理
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res
    
    def find_min_index(self,p,q,m):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res


    def __str__(self):
        # 生配列を表示
        rt=self.seg[self.num-1:self.num-1+self.n]
        return str(rt)

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)


n=I()
tr=Tree(n)
v=tr.dfs(0)

q,k=LI()
for i in range(q):
    x,y=LI_()
    print(v[x]+v[y])

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
nb = [[] for _ in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    nb[a].append((c, b))
    nb[b].append((c, a))
for x in nb:
    x.sort()

Q, K = map(int, input().split())
K -= 1

dist = [10 ** 10] * N
visited = set()
h = [(0, K, -1)]
while h:
    d0, node, parent = heapq.heappop(h)
    if node in visited:
        continue
    visited.add(node)
    dist[node] = d0
    for d1, child in nb[node]:
        d = d0 + d1
        if child != parent and d < dist[child]:
            heapq.heappush(h, (d, child, node))

for i in range(Q):
    x, y = map(int, input().split())
    # print(f"{x}->K = {dist[x]}, K->{y} = {dist[y]}")
    print(dist[x - 1] + dist[y - 1])

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
nb = [[] for _ in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    nb[a].append((c, b))
    nb[b].append((c, a))
for x in nb:
    x.sort()

Q, K = map(int, input().split())
queries = []
for i in range(Q):
    x, y = map(int, input().split())
    queries.append((x - 1, y - 1))
K -= 1

dist = [10 ** 10] * N
visited = set()
h = [(0, K, -1)]
while h:
    d0, node, parent = heapq.heappop(h)
    if node in visited:
        continue
    visited.add(node)
    dist[node] = d0
    for d1, child in nb[node]:
        d = d0 + d1
        if child != parent and d < dist[child]:
            heapq.heappush(h, (d, child, node))

for x, y in queries:
    # print(f"{x}->K = {dist[x]}, K->{y} = {dist[y]}")
    print(dist[x] + dist[y])

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
nb = [[] for _ in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    nb[a].append((c, b))
    nb[b].append((c, a))
for x in nb:
    x.sort()

Q, K = map(int, input().split())
queries = []
for i in range(Q):
    x, y = map(int, input().split())
    queries.append((x - 1, y - 1))
K -= 1

dist = [10 ** 10] * N
h = [(0, K, -1)]
while h:
    d0, node, parent = heapq.heappop(h)
    if dist[node] <= d0:
        continue
    dist[node] = d0
    for d1, child in nb[node]:
        d = d0 + d1
        if d < dist[child]:
            heapq.heappush(h, (d, child, node))

for x, y in queries:
    # print(f"{x}->K = {dist[x]}, K->{y} = {dist[y]}")
    print(dist[x] + dist[y])

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n = int(input())
list_ABC = [ list(map(int,input().split(" "))) for i in range(n-1)]
q, k = map(int, input().split())
list_XY = [ list(map(int,input().split(" "))) for i in range(q)]

ma = [[0]*n for _ in range(n)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

a = csr_matrix(ma)
b = dijkstra(a, indices=0 , directed=False).astype(int)

for x, y in list_XY:
    print(b[x-1]+b[y-1])

Submission status: Wrong Answer

Solution code:
def dijkstra(s,n,w,cost):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

N = int(input())
cost = [[float("inf") for i in range(N)] for i in range(N)]
for _ in range(N-1):
    x,y,z = map(int,input().split())
    cost[x-1][y-1] = z
    cost[y-1][x-1] = z
Q, K = map(int, input().split())
result = dijkstra(K-1,N,N-1,cost)
for i in range(Q):
    x, y = map(int, input().split())
    print(i,abs(result[x-1]-result[K-1])+abs(result[y-1]+result[K-1]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append((c, b))
    edges[b].append((c, a))
INF = float('inf')


def bfs(init_v):
    dist = [INF]*n
    dist[init_v] = 0
    tasks = deque([(0, init_v)])
    while tasks:
        print(tasks)
        d, v = tasks.popleft()
        for d2, v2 in edges[v]:
            if dist[v2] <= dist[v]+d2:
                continue
            dist[v2] = dist[v]+d2
            tasks.append((dist[v2], v2))
    return dist


q, k = map(int, input().split())
dist = bfs(k-1)
for _ in range(q):
    x, y = map(lambda x: int(x)-1, input().split())
    print(dist[x]+dist[y])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n= int(input())
bd = [[] for _ in range(n)]
for i in range(n-1):
    a,b,c= map(int,input().split())
    bd[a-1].append((b-1,c))
    bd[b-1].append((a-1,c))
q,k= map(int,input().split())
passedf = [False] * n
cost = [0] * n
def dfs(curnode,addcost):
    for abr in bd[curnode]:
        if not passedf[abr[0]]:
            cost[abr[0]]=addcost+abr[1]
            passedf[abr[0]]=True
            dfs(abr[0],addcost+abr[1])
dfs(k-1,0)
for i in range(q):
    x,y= map(int,input().split())
    print(cost[x-1]+cost[y-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
hen = [list(map(int, input().split())) for _ in range(n-1)]
q,k = map(int, input().split())
point = [list(map(int, input().split())) for _ in range(q)]
result = [0]*n

def search(a):
    for i in range (0,len(hen)):
        if (hen[i][0] == a  or  hen[i][1] == a):
            return i
            break
    return 9999999999

def dfs(a):
    s = search(a)
    print(s)
    if (s != 9999999999):
        if (hen[s][0] == a):
            b = hen.pop(s)
            result[s] = result[a] + b[2]
            dfs(s)
dfs(k)
print(result)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heapify,heappop
INF = 10**10

n = int(input())

es=[[] for _ in range(n)] # es[i] = (頂点iの(隣接する頂点,コスト)の組)
d = [INF]*n # 頂点sからの最短距離

# 入力
for i in range(n-1):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))


def dijkstra(s):
    v = -1
    que = [(0,s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que, (d[e[0]], e[0])) 
q,k=map(int,input().split())
dijkstra(k-1)
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heapify,heappop
INF = 10**10

n = int(input())

cost = [[INF]*n for _ in range(n)] # cost[u][v] = (辺(u,v)のコスト, 存在しないときはINF)
es=[[] for _ in range(n)] # es[i] = (頂点iの(隣接する頂点,コスト)の組)
d = [INF]*n # 頂点sからの最短距離

# 入力
for i in range(n-1):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))
    cost[a][b], cost[b][a] = c, c


def dijkstra(s):
    v = -1
    que = [(0,s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que, (d[e[0]], e[0])) 
q,k=map(int,input().split())
dijkstra(k-1)
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heapify,heappop
INF = 10**10

n = int(input())

cost = [[INF]*n for _ in range(n)] # cost[u][v] = (辺(u,v)のコスト, 存在しないときはINF)
es=[[] for _ in range(n)] # es[i] = (頂点iの(隣接する頂点,コスト)の組)
d = [INF]*n # 頂点sからの最短距離

# 入力
for i in range(n-1):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))
    cost[a][b], cost[b][a] = c, c


def dijkstra(s):
    v = -1
    que = [(0,s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que, (d[e[0]], e[0])) 
q,k=map(int,input().split())
dijkstra(k-1)
print(d)
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Submission status: Wrong Answer

Solution code:
# V: 頂点数
# g[v] = {(w, cost)}:
#     頂点vから遷移可能な頂点(w)とそのコスト(cost)
# r: 始点の頂点

from heapq import heappush, heappop
INF = 10**10
def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
    return dist

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = [int(i)-1 for i in input().split()]
    c += 1
    G[a].append((b, c))
    G[b].append((a, c))

Q, K = [int(i) for i in input().split()]
K -= 1

d = dijkstra(N, G, K)
for _ in range(Q):
    x, y = [int(i)-1 for i in input().split()]
    print(d[x]+d[y])

Submission status: Wrong Answer

Solution code:
#多分重みつきunionfind木を実装すれば楽
class WeightedUnionFind():
    
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 親への重みを管理
        self.weight = [0] * (n+1)
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1            
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def diff(self, x, y):
        return abs(self.weight[x] - self.weight[y])

def main():
    N = int(input())
    tree = WeightedUnionFind(N)
    for _ in range(N-1):
        a,b,c = map(int,input().split())
        tree.union(a,b,c)
    Q,K = map(int,input().split())
    Ans = []
    for _ in range(Q):
        x,y = map(int,input().split())
        p = tree.find(x)
        ans = tree.diff(x,p)+2*tree.diff(p,K)+tree.diff(p,y)
        Ans.append(ans)
    for ans in Ans:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
n = int(input())
g = [[10**10 for __ in range(n)] for _ in range(n)]

for _ in range(n-1):
    a, b, c = map(int, input().split())
    g[a-1][b-1] = c
    g[b-1][a-1] = c


def dijkstra(s, n, edges):
    # edges[i][j] : the cost of i→j
    # import 'heap'
    d = [10**13] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


q, k = map(int, input().split())
d = dijkstra(k-1, n, g)

for _ in range(q):
    x, y = map(int, input().split())
    print(d[x-1]+d[y-1])

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
n = int(input())
g = [[] for _ in range(n)]

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


def dijkstra(s, n, edges):
    # edges[i][j] : the cost of i→j
    # import 'heap'
    d = [10**13] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in edges[u]:
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


q, k = map(int, input().split())
d = dijkstra(k-1, n, g)

for _ in range(q):
    x, y = map(int, input().split())
    print(d[x-1]+d[y-1])

Submission status: Wrong Answer

Solution code:
n = int(input())

tree = [[]*n for i in range(n)]
already = [[False]*n for i in range(n)]

for i in range(n-1):
  a, b, c = map(int, input().split())
  if a > b:
    a, b = b, a
  tree[a-1].append([b-1, c])
  tree[b-1].append([a-1, c])
  already[a-1][b-1] = True

q, k = map(int, input().split())

distance = [0]*n
not_yet = []
for value in tree[k-1]:
  not_yet.append([k-1] + value)

while not_yet:
  key = not_yet[-1]
  now, a, b = key[0], key[1], key[2]
  not_yet.pop()
  already[now][a] = False
  already[a][now] = False
  distance[a] = distance[now] + b
  for value in tree[a]:
    if already[a][value[0]] == True:
      not_yet.append([a]+value)

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

Submission status: Wrong Answer

Solution code:
def dijkstra(s, n, cost):
    d = [float("inf")] * (n+1)
    used = [False] * (n+1)
    d[s] = 0

    while True:
        v = -1
        for i in range(1, n+1):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        for j in range(1, n+1):
            d[j] = min(d[j], d[v] + cost[v][j])
    return d


n = int(input())
inf = 10**10
cost = [[inf]*(n+1) for _ in range(n+1)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    cost[a][b] = c
    cost[b][a] = c
q, k = map(int, input().split())
ans = dijkstra(k, n, cost)
for _ in range(q):
    x, y = map(int, input().split())
    print(ans[x] + ans[y])

Submission status: Wrong Answer

Solution code:
from collections import deque
import queue
class Dijkstra:
    def __init__(self,n):
        self.n = n
        self.lengths = [dict() for _ in range(n)]
        self.inf = 1000000000
    def register(self,v1,v2,l,multiple=True):
        self.lengths[v1][v2] = l
        if multiple:
            self.lengths[v2][v1] = l
    def solve(self,s1):
        d = [self.inf for _ in range(self.n)]
        d[s1] = 0
        paths = [None for _ in range(self.n)]
        paths[s1] = []
        Q = queue.PriorityQueue()
        Q.put((d[s1],s1))
        while not Q.empty():
            d1,v1 = Q.get()
            for v2,l in self.lengths[v1].items():
                val = d1 + l
                if val < d[v2]:
                    d[v2] = val
                    Q.put((val,v2))
                    paths[v2] = paths[v1] + [v1]
        return d, paths
N = int(input())
D = Dijkstra(N)
Edges = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    D.register(a,b,c)
Q,K = map(int,input().split())
C,_ = D.solve(K-1)
for i in range(Q):
    x,y = map(int,input().split())
    print(C[x-1]+C[y-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve(n, ABC, q, k, XY):
    graph = [[] for _ in range(n)]
    for a, b, c in ABC:
        graph[a - 1].append((b - 1, c))
        graph[b - 1].append((a - 1, c))

    q = deque(maxlen=n)
    q.append((k - 1, 0))
    used = {k - 1}
    l = [] * n
    while len(q) > 0:
        node, length = q.popleft()
        l[node] = length
        for next, next_length in graph[node]:
            if next in used:
                continue
            q.append((next, length + next_length))
            used.add(next)
    return l

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
G = [deque([]) for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append([b, c])
    G[b].append([a, c])
dist = [-1] * n

def dfs(v):
    cnt = 0
    stack = [[v, 0]]
    while stack:
        v = stack[-1]
        if len(G[v[0]]) > 0:
            w = G[v[0]].popleft()
            if dist[w[0]] == -1:
                dist[w[0]] = v[1] + w[1]
                stack.append(w)
        else: stack.pop()

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b,c = map(int,input().split())
    graph[a].append([b,c])
    graph[b].append([a,c])

def dfs(v):
    dist = [10 ** 12] * (n+1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        for w,cost in graph[v]:
            if dist[w] >= dist[v] + cost:
                dist[w] = dist[v] + cost
                stack.append(w)
    return dist
q,k = map(int,input().split())
distance = dfs(k)
for i in range(q):
    x,y = map(int,input().split())
    print(distance[x]+distance[y])

Submission status: Wrong Answer

Solution code:
import heapq
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append((b, c))
    g[b].append((a, c))

q, k = map(int, input().split())
k -= 1
hq = []
d = [1000000000000] * n
d[k] = 0
heapq.heappush(hq, (0, k))
while len(hq):
    dist, v = heapq.heappop(hq)
    if d[v] < dist:
        continue
    for e in g[v]:
        nv, l = e
        if d[nv] > d[v] + l:
            d[nv] = d[v] + l
            heapq.heappush(hq, (d[nv], nv))

for i in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(d[x] + d[y])

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  graph[a].append((b, c))
  graph[b].append((a, c))
q, k = map(int, input().split())
xy = []
for _ in range(q):
  x, y = map(int, input().split())
  xy.append((x, y))

l = [0]*(n+1)
def DFS(node, p_node, length):
  l[node] = length
  for i, j in graph[node]:
    try:
      if i==p_node:
        continue
    except:
      sys.exit(0)
    DFS(i, node, length+j)

DFS(k, -1, 0)
for x, y in xy:
  print(l[x]+l[y])

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  graph[a].append((b, c))
  graph[b].append((a, c))
q, k = map(int, input().split())
xy = []
for _ in range(q):
  x, y = map(int, input().split())
  xy.append((x, y))

l = [0]*(n+1)
def DFS(node, p_node, length):
  l[node] = length
  for i, j in graph[node]:
    if i==p_node:
      continue
    DFS(i, node, length+j)
try:
  DFS(k, -1, 0)
except:
  sys.exit(0)
for x, y in xy:
  print(l[x]+l[y])

Submission status: Wrong Answer

Solution code:
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  a-=1
  b-=1
  graph[a].append((b, c))
  graph[b].append((a, c))
q, k = map(int, input().split())
k-=1
seen = [False]*n
l = [0]*n

for _ in range(q):
  x, y = map(int, input().split())
  print(l[x-1]+l[y-1])

Submission status: Wrong Answer

Solution code:
from queue import Queue
NUM=9*(10**10)
N=int(input())
A=[0]*(N-1)
for i in range(N-1):
    A[i]=list(map(int,input().split()))
    A[i][0]-=1
    A[i][1]-=1
Q,K=map(int,input().split())
K-=1
Z=[0]*(Q)
for i in range(Q):
    Z[i]=list(map(int,input().split()))
    Z[i][0]-=1
    Z[i][1]-=1
MAP=[[NUM]*N for i in range(N)]
F=0
q = Queue()

for i in range(N-1):
    MAP[A[i][0]][A[i][1]]=A[i][2]
    MAP[A[i][1]][A[i][0]]=A[i][2]
F=0
for z in Z:
    q = Queue()
    if(MAP[z[0]][K]==NUM):
        for i in range(N):
            if(MAP[z[0]][i]!=NUM):
                q.put((MAP[z[0]][i],i))
    while not q.empty():
        T=q.get()
        if(MAP[T[1]][K]!=NUM):
            c=T[0]+MAP[T[1]][K]
            if MAP[z[0]][K] > c:
                MAP[z[0]][K]=c
                break
        for i in range(N):
            if(MAP[T[1]][i]!=NUM):
                q.put((T[0]+MAP[T[1]][i],i))
    
    q = Queue()
    if(MAP[z[1]][K]==NUM):
        for i in range(N):
            if(MAP[z[1]][i]!=NUM):
                q.put((MAP[z[1]][i],i))
    while not q.empty():
        T=q.get()
        if(MAP[T[1]][K]!=NUM):
            c=T[0]+MAP[T[1]][K]
            if MAP[z[1]][K] > c:
                MAP[z[1]][K]=c
                break
        for i in range(N):
            if(MAP[T[1]][i]!=NUM):
                q.put((T[0]+MAP[T[1]][i],i))

for z in Z:
    print(MAP[z[0]][K]+MAP[z[1]][K])

Submission status: Wrong Answer

Solution code:
from queue import Queue
NUM=9*(10**10)
N=int(input())
A=[0]*(N-1)
for i in range(N-1):
    A[i]=list(map(int,input().split()))
    A[i][0]-=1
    A[i][1]-=1
Q,K=map(int,input().split())
K-=1
Z=[0]*(Q)
for i in range(Q):
    Z[i]=list(map(int,input().split()))
    Z[i][0]-=1
    Z[i][1]-=1
MAP=[[NUM]*N for i in range(N)]
F=0
q = Queue()

for i in range(N-1):
    MAP[A[i][0]][A[i][1]]=A[i][2]
    MAP[A[i][1]][A[i][0]]=A[i][2]
F=0
for z in Z:
    q = Queue()
    if(MAP[z[0]][K]==NUM):
        for i in range(N):
            if(MAP[z[0]][i]!=NUM):
                q.put((MAP[z[0]][i],i))
    while not q.empty():
        T=q.get()
        if(MAP[T[1]][K]!=NUM):
            c=T[0]+MAP[T[1]][K]
            if MAP[z[0]][K] > c:
                MAP[z[0]][K]=c
                F=1
        for i in range(N):
            if(MAP[T[1]][i]!=NUM):
                q.put((T[0]+MAP[T[1]][i],i))
        if(F==1):
            F=0
            break
    
    q = Queue()
    if(MAP[z[1]][K]==NUM):
        for i in range(N):
            if(MAP[z[1]][i]!=NUM):
                q.put((MAP[z[1]][i],i))
    while not q.empty():
        T=q.get()
        if(MAP[T[1]][K]!=NUM):
            c=T[0]+MAP[T[1]][K]
            if MAP[z[1]][K] > c:
                MAP[z[1]][K]=c
                F=1
        for i in range(N):
            if(MAP[T[1]][i]!=NUM):
                q.put((T[0]+MAP[T[1]][i],i))
        if(F==1):
            F=0
            break

for z in Z:
    print(MAP[z[0]][K]+MAP[z[1]][K])