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:
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=[[10**5]*N for i in range(N)]
MAP2=[[10**5]*N for i in range(N)]

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]

def cal(x1,x2,c,o,f,T):
    M=MAP
    M2=MAP2
    global K
    if(f==0):
        if(x1==x2 and MAP2[o][x2]>c):
            MAP2[o][x2]=c
            return 0
        if(MAP2[o][x2]<c):
            return 0
    if(f==1):
        if(x1==K):
            f=0
            T=[0,1,2,3,4]
        if(MAP2[o][x2]<c):
            return 0

    for i in T:
        if MAP[x1][i] != 10**5:
            if MAP[x1][i] == 10**5:
                k=0
            else:
                k=MAP[x1][i]
            T1=T[:]
            T1.remove(i)
            cal(i,x2,c+k,o,f,T1)

    return 0

T=[i for i in range(N)]
for i in Z:
    T1=T[:]
    T1.remove(i[0])
    cal(i[0],i[1],0,i[0],1,T1)

for i in Z:
    print(MAP2[i[0]][i[1]])
#print()

Submission status: Wrong Answer

Solution code:
from collections import deque

N=int(input())

R=[[] for i in range(N)]

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

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

for i in range(Q):
    x,y=map(int,input().split())
    q=deque([[x-1,0,0]])
    ans=10**14
    chk=[0]*N
    while q:
        n,d,f=q.popleft()
        if n==K-1:
            if f:continue
            else:f=1
        if f:
            chk[n]=1
        for i,c in R[n]:
            if i==y-1:
                if f:
                    temp=c+d
                    ans=min(ans,temp)
            elif chk[i]==1:continue
            else:
                q.append([i,c+d,f])
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000) 
N=int(input())
Branch=[[] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  Branch[a-1].append([b-1,c])
  Branch[b-1].append([a-1,c])
Q,K=map(int,input().split())
DistK=[float("Inf") for i in range(N)]
flag = [0 for i in range(N)]

def dfs(s,dist):
  DistK[s]=dist
  flag[s]=1
  
  for i in range(len(Branch[s])):
    if flag[Branch[s][i][0]]==0:
      dfs(Branch[s][i][0],dist+Branch[s][i][1])
      
  return 1
dfs(K-1,0)
print(DistK)
for i in range(Q):
  x,y = map(int,input().split())
  print(DistK[x-1]+DistK[y-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
d = [[float("inf")]*n for _ in range(n)]
for i in range(n):
  d[i][i] = 0
for _ in range(n-1):
  a, b, c = map(int, input().split())
  d[a-1][b-1] = c
  d[b-1][a-1] = c
for i in range(n):
  for j in range(n):
    for k in range(n):
      d[i][j] = min(d[i][j], d[i][k] + d[k][j])
q, k = map(int, input().split())
for _ in range(q):
  x, y = map(int, input().split())
  print(d[x-1][k-1] + d[k-1][y-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
d = [[float("inf")]*n for _ in range(n)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  d[a-1][b-1] = c
  d[b-1][a-1] = c
for i in range(n):
  for j in range(n):
    for k in range(n):
      d[i][j] = min(d[i][j], d[i][k] + d[k][j])
q, k = map(int, input().split())
for _ in range(q):
  x, y = map(int, input().split())
  print(d[x-1][k-1] + d[k-1][y-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n - 1)]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

from heapq import heappop, heappush

def main():
    cost = [[] for _ in range(n)]
    for i in range(n - 1):
        a = abc[i][0] - 1
        b = abc[i][1] - 1
        c = abc[i][2]
        cost[a].append((b, c))
        cost[b].append((a, c))

    print(cost)

    start = K - 1
    d = [float('inf') for i in range(n)] # 最短距離
    d[start] = 0

    q = [] # min-heap, (距離, 頂点)
    heappush(q, (d[start], start))
    while q:
        du, u = heappop(q) # 最短距離とその頂点
        if d[u] < du:
            continue
        for v, weight in cost[u]:
            alt = du + weight
            if d[v] > alt:
                d[v] = alt
                heappush(q, (alt, v))

    for goal1, goal2 in xy:
        print(d[goal1 - 1] + d[goal2 - 1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[[] for i in range(n+1)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  l[a].append([b,c])
  l[b].append([a,c])
q,k=map(int,input().split())
from heapq import heappush,heappop
inf=10**10
def dijkstra(s):
  q=[(0,s)]
  dist=[inf]*(n+1)
  dist[s]=0
  while q:
    c,v=heappop(q)#cは始点からvまでのコスト vは頂点
    if dist[v]<c:
      continue
    for i in l[v]:
      t=i[0]
      cost=i[1]
      if dist[v]+cost<dist[t]:
        dist[t]=dist[v]+cost
        heappush(q,[dist[t],t])
  return dist
d=dijkstra(k)
for i in range(q):
  x,y=map(int,input().split())
  print(d[x]+d[y])

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    edge[a].append([b, c])
    edge[b].append([a, c])


def BFS(x, y):
    visited = [False for _ in range(N+1)]
    next_N = [False for _ in range(N+1)]
    INF = float('inf')
    dest = [INF for _ in range(N+1)]
    d = deque()
    visited[x] = True
    dest[x] = 0
    for B, C in edge[x]:
        d.append([B, C])
        next_N[B] = True
        dest[B] = dest[x] + C
    while d:
        now = d.popleft()
        visited[now[0]] = True
        for B, C in edge[now[0]]:
            if visited[B] == False and next_N[B] == False:
                d.append([B, C])
                next_N[B] = True
                dest[B] = dest[now[0]] + C
    print(dest)
    return dest[y]

Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]
for X, Y in xy:
    print(BFS(X, K) + BFS(K, Y))

Submission status: Wrong Answer

Solution code:
import sys
import collections
from functools import lru_cache

ts = collections.defaultdict(list)
tc = collections.defaultdict(int)


@lru_cache(maxsize=None)
def func(start, end):
    ql = [[0, start]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    mc = 10 ** 10
    while True:
        if len(ql) != 0:
            cost, p = ql.popleft()
            if p == end:
                mc = min(mc, cost)
            else:
                for v in ts[p]:
                    if v not in fq:
                        ql.append([cost+tc[p, v], v])
                        fq[v]
        else:
            return mc


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    for i in range(n-1):
        ta, te, tcost = list(map(int, input().rstrip('\n').split()))
        ts[ta - 1] += [te - 1]
        ts[te - 1] += [ta - 1]
        tc[ta-1, te-1] = tcost
        tc[te-1, ta-1] = tcost

    q, k = list(map(int, input().rstrip('\n').split()))
    for i in range(q):
        x, y = list(map(int, input().rstrip('\n').split()))
        print(func(x-1, k-1) + func(k-1, y-1))


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
# ABC070e
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            # if i == j:
            #    cost[i][j] = 0
            cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])
# print(cost)
Q, K = map(int, input().split())
for _ in range(Q):
    x, y = map(int, input().split())
    print(cost[x-1][K-1]+cost[K-1][y-1])

Submission status: Wrong Answer

Solution code:
from collections import *
from heapq import*
import sys
input=sys.stdin.readline
d=defaultdict(list)
n=int(input())
 
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})
 
def DIJKSTRA(point,d):
    cost      = {node:1e12 for node in d.keys()}
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost
 
q,k=map(int,input().split())
y=DIJKSTRA(k,d)
 
for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
l=[[0,0,0] for _ in range(n-1)]
for i in range(n-1):
    l[i][0],l[i][1],l[i][2]=map(int,input().split())
l.sort()
q,k=map(int,input().split())
r=[[0,0] for _ in range(q)]
for i in range(q):
    r[i][0],r[i][1]=map(int,input().split())
c=[0]*n
for i in range(n-1):
    if l[i][0]==k:
        c[l[i][1]-1]=l[i][2]
    elif l[i][1]==k:
        c[l[i][0]-1]=l[i][2]

for _ in range(500):
    for i in range(n-1):
        if c[l[i][0]-1]!=0 and c[l[i][1]-1]==0:
            c[l[i][1]-1]+=c[l[i][0]-1]+l[i][2]
        if c[l[i][1]-1]!=0 and c[l[i][0]-1]==0:
            c[l[i][0]-1]+=c[l[i][1]-1]+l[i][2]
#print(c)
for i in range(q):
    print(c[r[i][0]-1]+c[r[i][1]-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
l=[[0,0,0] for _ in range(n-1)]
for i in range(n-1):
    l[i][0],l[i][1],l[i][2]=map(int,input().split())
l.sort()
q,k=map(int,input().split())
r=[[0,0] for _ in range(q)]
for i in range(q):
    r[i][0],r[i][1]=map(int,input().split())
c=[0]*n
for i in range(n-1):
    if l[i][0]==k:
        c[l[i][1]-1]=l[i][2]
    elif l[i][1]==k:
        c[l[i][0]-1]=l[i][2]

for _ in range(100):
    for i in range(n-1):
        if c[l[i][0]-1]!=0 and c[l[i][1]-1]==0:
            c[l[i][1]-1]+=c[l[i][0]-1]+l[i][2]
        if c[l[i][1]-1]!=0 and c[l[i][0]-1]==0:
            c[l[i][0]-1]+=c[l[i][1]-1]+l[i][2]
#print(c)
for i in range(q):
    print(c[r[i][0]-1]+c[r[i][1]-1])

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[[0,0,0] for _ in range(n-1)]
for i in range(n-1):
    l[i][0],l[i][1],l[i][2]=map(int,input().split())
l.sort()
q,k=map(int,input().split())
r=[[0,0] for _ in range(q)]
for i in range(q):
    r[i][0],r[i][1]=map(int,input().split())
c=[0]*n
for i in range(n-1):
    if l[i][0]==k:
        c[l[i][1]-1]=l[i][2]
    elif l[i][1]==k:
        c[l[i][0]-1]=l[i][2]


for i in range(n-1):
    if c[l[i][1]-1]==0:
        c[l[i][1]-1]+=c[l[i][0]-1]+l[i][2]
    elif c[l[i][0]-1]==0:
        c[l[i][0]-1]+=c[l[i][1]-1]+l[i][2]
#print(c)
for i in range(q):
    print(c[r[i][0]-1]+c[r[i][1]-1])

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[[0,0,0] for _ in range(n-1)]
for i in range(n-1):
    l[i][0],l[i][1],l[i][2]=map(int,input().split())
l.sort()
q,k=map(int,input().split())
r=[[0,0] for _ in range(q)]
for i in range(q):
    r[i][0],r[i][1]=map(int,input().split())
c=[0]*n
for i in range(n-1):
    if l[i][0]==k:
        c[l[i][1]-1]=l[i][2]
    elif l[i][1]==k:
        c[l[i][0]-1]=l[i][2]
for i in range(n-1):
    if l[i][0]!=k and l[i][1]!=k:
        if c[l[i][1]-1]==0:
            c[l[i][1]-1]+=c[l[i][0]-1]+l[i][2]
        elif c[l[i][0]-1]==0:
            c[l[i][0]-1]+=c[l[i][1]-1]+l[i][2]
for i in range(n-1):
    if l[i][0]!=k and l[i][1]!=k:
        if c[l[i][1]-1]==0:
            c[l[i][1]-1]+=c[l[i][0]-1]+l[i][2]
        elif c[l[i][0]-1]==0:
            c[l[i][0]-1]+=c[l[i][1]-1]+l[i][2]
#print(c)
for i in range(q):
    print(c[r[i][0]-1]+c[r[i][1]-1])

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[[0,0,0] for _ in range(n-1)]
for i in range(n-1):
    l[i][0],l[i][1],l[i][2]=map(int,input().split())
l.sort()
q,k=map(int,input().split())
r=[[0,0] for _ in range(q)]
for i in range(q):
    r[i][0],r[i][1]=map(int,input().split())
#print(l,r)
c=[0]*n
for i in range(n-1):
    if l[i][0]==k:
        c[l[i][1]-1]=l[i][2]
    elif l[i][1]==k:
        c[l[i][0]-1]=l[i][2]
for i in range(n-1):
    if l[i][0]!=k and l[i][1]!=k:
        if c[l[i][1]-1]==0:
            c[l[i][1]-1]+=c[l[i][0]-1]+l[i][2]
        elif c[l[i][0]-1]==0:
            c[l[i][0]-1]+=c[l[i][1]-1]+l[i][2]
for i in range(q):
    print(c[r[i][0]-1]+c[r[i][1]-1])

Submission status: Wrong Answer

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

# 頂点 s からの最短距離を求める (存在しないときはinf) O(|w|log|n|)
# n: 頂点数, w: 辺の数, cost[u][v]: 辺uvのコスト (cost が dict の場合 cost[(u,v)] など適宜)
# 前提条件: u < v
def dijkstra(s,n,w,cost):
    d = [float("inf")] * n # s からの距離
    d[s] = 0
    used = [False] * n # 使用済みの頂点か
    
    while True:
        v = -1
        # 未使用の頂点のうち、最小の距離のものを探す
        for i in range(n):
            if used[i]:
                continue
            if v == -1 or d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
               
        for j in range(n):
            e = (min(v,j), max(v,j))
            c = cost[e] if e in cost else float("inf")
            # cost が list のときは普通に c = cost[v][j] などとする
            d[j] = min(d[j], d[v] + c)
    return d

def main():
    N = int(input())
    E = dict()
    for _ in range(N-1):
        a,b,c = map(int, input().split())
        E[(a-1,b-1)] = c
    Q,K = map(int, input().split())
    D = dijkstra(K-1, N, N-1, E)
    for _ in range(Q):
        x,y = map(int, input().split())
        print(D[x-1] + D[y-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

import sys 
input = sys.stdin.readline
from collections import deque
def solve():
  n = int(input())
  d = [[]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1].append((b-1,c))
    d[b-1].append((a-1,c))
  q,k = (int(i) for i in input().split())
  #kからの距離を計算する
  d2 = [10**10]*n
  visit = [0]*n
  query = deque([(k-1,0)]) #始点、距離
  while query:
    place,dist = query.pop()
    if visit[place] >= 2:
      continue
    else:
      visit[place] += 1
      d2[place] = min(dist,d2[place])
      for i in range(len(d[place])):
        np,nc = d[place][i]
        if not visit[np] >= 2:
          query.append((np,nc+dist))
  for i in range(q):
    x,y = (int(i) for i in input().split())
    print(int(d2[x-1] + d2[y-1]))

solve()

Submission status: Wrong Answer

Solution code:

import sys 
input = sys.stdin.readline
from collections import deque
def solve():
  n = int(input())
  d = [[]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1].append((b-1,c))
    d[b-1].append((a-1,c))
  q,k = (int(i) for i in input().split())
  #kからの距離を計算する
  d2 = [10**10]*n
  visit = [False]*n
  query = deque([(k-1,0)]) #始点、距離
  while query:
    place,dist = query.pop()
    if visit[place]:
      continue
    else:
      visit[place] = True
      d2[place] = min(dist,d2[place])
      for i in range(len(d[place])):
        np,nc = d[place][i]
        if not visit[np]:
          query.append((np,nc+dist))
  for i in range(q):
    x,y = (int(i) for i in input().split())
    print(int(d2[x-1] + d2[y-1]))

solve()

Submission status: Wrong Answer

Solution code:

import sys 
input = sys.stdin.readline
from collections import deque
def solve():
  n = int(input())
  d = [[]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1].append((b-1,c))
    d[b-1].append((a-1,c))
  q,k = (int(i) for i in input().split())
  #kからの距離を計算する
  d2 = [10**10]*n
  visit = [False]*n
  query = deque([(k-1,0)]) #始点、距離
  while query:
    place,dist = query.pop()
    if visit[place]:
      continue
    else:
      visit[place] = True
      d2[place] = min(dist,d2[place])
      for i in range(len(d[place])):
        np,nc = d[place][i]
        query.append((np,nc+dist))

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

solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]
for _ in range(N-1):
    v, c, p = iter(queue.pop(0))
    shortest_path[v] = c
    queue += [[u, T[v][u] + c, v] for u in T[v].keys() if u != p]

Submission status: Wrong Answer

Solution code:
N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]

for _ in range(Q):
    x, y = map(int, input().split())
    while len(queue) > 0 and (shortest_path[x] != 0 or shortest_path[y] != 0):
        v = queue.pop(0)
        shortest_path[v[0]] = v[1]
        queue += [[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]]
    print(shortest_path[x] + shortest_path[y])

Submission status: Wrong Answer

Solution code:
N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]

for _ in range(N-1):
    v = queue.pop(0)
    shortest_path[v[0]] = v[1]
    queue += [[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]]

Submission status: Wrong Answer

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

class Heapq:
    def __init__(self, que=[], asc=True):
        if not asc:
            que = [-a for a in que]
        self.__que = que
        heapq.heapify(self.__que)
        self.__sign = 1 if asc else -1

    def pop(self):
        return heapq.heappop(self.__que) * self.__sign

    def push(self, value):
        heapq.heappush(self.__que, value * self.__sign)

    def pushpop(self, value):
        return heapq.heappushpop(self.__que, value * self.__sign) * self.__sign

    def top(self):
        return self.__que[0] * self.__sign

    def size(self):
        return len(self.__que)


def sol():
    N = int(input())
    edges = [[] for _ in range(N)]

    for _ in range(N - 1):
        fr, to, cost = map(int, input().split())
        fr -= 1
        to -= 1
        edges[fr].append((to, cost))
        edges[to].append((fr, cost))

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

    minDist = [float('inf')] * N
    que = Heapq([])
    que.push((K, 0))

    while que.size():
        dist, now = que.pop()

        if minDist[now] < dist:
            continue
        minDist[now] = dist

        for to, cost in edges[now]:
            if minDist[to] > dist + cost:
                que.push((dist + cost, to))

    for _ in range(Q):
        fr, to = map(int, input().split())
        print(minDist[fr - 1] + minDist[to - 1])


sol()

Submission status: Wrong Answer

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########
    

def main():
    N = i_inpl()
    G = defaultdict(dict)
    for _ in range(N-1):
        ai, bi, ci = l_inpl()
        ai, bi = ai-1, bi-1
        G[ai][bi] = ci
    
    Q, K = l_inpl()
    K = K-1
    qlist = [l_inpl() for _ in range(Q)]

    cost = [INF] * N
    cost[K] = 0

    # dfs
    queue = deque([K])
    while queue:
        s = queue.pop()
        for t in G[s]:
            if cost[t] > cost[s] + G[s][t]:
                cost[t] = cost[s] + G[s][t]
                queue.append(t)
    
    for xi, yi in qlist:
        print(cost[xi-1]+cost[yi-1])


 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import queue

N = int(input())
E = {n: set() for n in range(N)}

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

def m():
    Q, K = map(int, input().split())
    K -= 1
    dist = [-1] * N
    already = set()
    que = queue.Queue()
    dist[K] = 0
    que.put(K)
    while not que.empty():
        now = que.get()
        out = E[now]
        for n, c in out:
            if dist[n] != -1:
                continue
            dist[n] = dist[now] + c        
            que.put(n)
    
    res = ""
    for _ in range(Q):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        res += str(dist[x] + dist[y]) + "\n"
    
    print(res)

Submission status: Wrong Answer

Solution code:
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=[int(v)-1 for v in input().split()]
    c+=1
    G[a-1].append((b-1,c))
    G[b-1].append((a-1,c))
q,k=[int(v) for v in input().split()]
k=k-1
stack=[k]
dis=[-1]*n
dis[k]=0
while stack!=[]:
    now=stack.pop()
    d=dis[now]
    for i in G[now]:
        if dis[i[0]]==-1:
            dis[i[0]]=d+i[1]
            stack.append(i[0])
for i in range(q):
    x,y=[int(v)-1 for v in input().split()]
    print(dis[x]+dis[y])

Submission status: Wrong Answer

Solution code:
def solve(n_query, q_query, k):
    for a, b, c in n_query:
        unite(a, b, c)
        if a == k:
            is_via_root[b] = 0
        if b == k:
            is_via_root[a] = 0

    ans = []
    for x, y in q_query:
        if x == k:
            x_to_k = 0
        # x-root-k
        elif is_via_root[x]:
            x_to_k = weight(x) + weight(k)
        # x-k-root
        else:
            x_to_k = abs(diff(x, k))
        if y == k:
            k_to_y = 0
        # y-root-k
        elif is_via_root[y]:
            k_to_y = weight(k) + weight(y)
        # y-k-root
        else:
            k_to_y = abs(diff(k, y))

        ans.append(x_to_k + k_to_y)
#        print("{0}->{1}: {2} |{3}->{4}: {5}".format(x, k, x_to_k, k, y, k_to_y))

    return ans


def unite(x, y, w):
    w += diff_weight[x]-diff_weight[y]
    rt_x = find(x)
    rt_y = find(y)
#    print("rt_x: {0} | rt_y: {1} | par[rt_x]: {2} | par[rt_y]: {3} | w: {4}".format(
#        rt_x, rt_y, par[rt_x], par[rt_y], w))

    if rt_x == rt_y:
        return
    if rank[rt_x] >= rank[rt_y]:
        par[rt_y] = rt_x
        diff_weight[rt_y] = w
        if rank[rt_x] == rank[rt_y]:
            rank[rt_x] += 1
    else:
        par[rt_x] = rt_y
        diff_weight[rt_x] = -w


def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        diff_weight[x] += diff_weight[par[x]]
        par[x] = px
        return px


def weight(x):
    find(x)
    return diff_weight[x]


def is_same(x, y):
    return find(x) == find(y)


def diff(x, y):
    return weight(y)-weight(x)


if __name__ == '__main__':
    n = int(input())
    par, rank = [-1]*(n+1), [0]*(n+1)
    diff_weight = [0]*(n+1)
    is_via_root = [1]*(n+1)
    n_query = []
    q_query = []

    for _ in range(n-1):
        a, b, c = map(int, input().split())
        n_query.append((a, b, c))
    q, k = map(int, input().split())
    for _ in range(q):
        x, y = map(int, input().split())
        q_query.append((x, y))

    ans = solve(n_query, q_query, k)
    for a in ans:
        print(a)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

N = int(input())
edges = [list(map(int, input().split())) for _ in range(N - 1)]
Q, K = map(int, input().split())

INF = 10 ** 9 + 7

dp = [INF] * (N + 1)
visited = [False] * (N + 1)
pq = []

# Initialization
dp[K] = 0
heappush(pq, (0, K))

while pq:
    cost, u = heappop(pq)
    visited[u] = True

    if dp[u] < cost:
        continue
    
    for v, w, c in edges:
        if v != u and w != u:
            continue
            
        node = w if v == u else v
        if visited[node]:
            continue
            
        if dp[node] > dp[u] + c:
            dp[node] = dp[u] + c
            heappush(pq, (dp[node], node))

for _ in range(Q):
    x, y = map(int, input().split())
    print(dp[x] + dp[y])

Submission status: Wrong Answer

Solution code:
from scipy.sparse import csc_matrix
import sys
input = sys.stdin.readline

N = int(input())
ABC = [[int(x) for x in input().split()] for _ in range(N-1)]
row,col,val = zip(*ABC)

edge = csc_matrix((val,(row,col)),(N+1,N+1))

Submission status: Wrong Answer

Solution code:
n = int(input())
g = {}
for i in range(1,n+1):
    g[i] = []
for _ in range(n-1):
    a,b,c = map(int,input().split())
    g[a].append([b,c])
    g[b].append([a,c])
Q,k = map(int,input().split())
q = [list(map(int,input().split())) for _ in range(Q)]
from collections import deque
queue = deque(g[k])
shortest = [0]*(n+1)
while queue:
    a,c = queue.popleft()
    shortest[a] = c
    for v in g[a]:
        if shortest[v[0]]==0:
            queue.appendleft([v[0],v[1]+c])
for x,y in q:
    print(shortest[x]+shortest[y])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    N = int(input())
    
    tree = defaultdict(lambda: [])
    d = [[0 for _ in range(N)] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        a, b = a - 1, b - 1
        
        d[a][b] = c
        d[b][a] = c

        for s in tree[a]:
            d[s][b] = d[s][a] + c
            d[b][s] = d[a][s] + c

        for s in tree[b]:
            d[s][a] = d[s][b] + c
            d[a][s] = d[b][s] + c

        tree[a].append(b)
        tree[b].append(a)

    Q, K = map(int, input().split())
    for _ in range(Q):
        x, y = map(int, input().split())
        x, y = x - 1, y - 1

        print(int(d[x][K-1] + d[K-1][y]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

q, k = map(int, input().split())
dist[k-1] = 0
for _ in range(n-2):
  for a, b, c in abclist:
    if dist[a] == -1 and dist[b] == -1:
      continue
    elif dist[a] == -1:
      dist[a] = dist[b] + c
    elif dist[b] == -1:
      dist[b] = dist[a] + c
    else:
      if dist[a] > dist[b] + c:
        dist[a] = dist[b] + c
      if dist[b] > dist[a] + c:
        dist[b] = dist[a] + c

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

Submission status: Wrong Answer

Solution code:
import collections as c
 
d=c.defaultdict(list)
n=int(input())
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
 
def DFS(point,d,cost,TFlist): #入力と同じindex系
    for s in d[point]:
        try:
            p=s[0]
            c=s[1]+cost[point]
            if TFlist[p-1]:
                continue
            cost[p]+=c
            TFlist[p-1]=1
            DFS(p,d,cost,TFlist)
        except:
            continue
 
cost=[None]+[0 for i in range(n)]
q,k=map(int,input().split())
TFlist=[0 for i in range(n)]
TFlist[k-1]=1
DFS(k,d,cost,TFlist)
 
for t in range(q):
    a,b=map(int,input().split())
    print(cost[a]+cost[b])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
abc = [[int(j) for j in input().split()] for _ in range(N-1)]
Q,K = map(int, input().split())
xy = [ [int(j) for j in input().split()] for _ in range(Q)]

inf = float("inf")
con = [ [] for _ in range(N+1)]
cost = [ [inf] * (N+1) for _ in range(N+1)]

for i in range(N-1):
    a,b,c = abc[i]
    con[a].append(b)
    con[b].append(a)
    cost[a][b] = c
    cost[b][a] = c

def dfs(a,b, par):
    if cost[a][b] != inf:
        return cost[a][b]
    if len(list(filter(lambda x: x!=par, con[a]))) == 0:
        return inf

    cst = inf
    idx= -1
    for e,ch in enumerate(con[a]):
        if ch == par:
            continue
        if cst > cost[a][ch] + dfs(ch,b,a):
            cst = cost[a][ch] + dfs(ch,b,a)
            idx = e
        # cst = min(cst, cost[a][ch] + dfs(ch, b, a))
    if idx != -1:
        cost[a][b] = cst
        cost[b][a] = cst
    return cst

for i in range(Q):
    x,y = xy[i]
    print(dfs(x,K,None) + dfs(K,y,None))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(1000000)
d=defaultdict(list)

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

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

# Kを中心とした距離を求める
dists=[None]*(N+1)
isused=[False]*(N+1)
dists[K]=0
isused[K]=True

def dfs(n):
    for i,j in d[n]:
        if isused[i]:continue
        isused[i]=True
        print(i,j)
        dists[i]=dists[n]+j
        dfs(i)

dfs(K)
for _ in range(Q):
    x,y=map(int,input().split())
    print(dists[x]+dists[y])