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: Accepted

Solution code:
N=int(input())
edges=[list(map(int,input().split())) for i in range(N-1)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
root=[[] for _ in range(N)]
for a,b,c in edges:
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))
d=[-1]*N
s=[K-1]
d[K-1]=0
while s:
        l=s.pop()

        for i,c in root[l]:
                if d[i]==-1:
                        d[i]=d[l]+c
                        s.append(i)
for i in range(Q):
        print(d[xy[i][0]-1]+d[xy[i][1]-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
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))
Q,K = map(int,input().split())
distance = [None] * (N+1)
def dfs(v1,d):
    distance[v1] = d
    for v2,dd in edge[v1]:
        if distance[v2] is not None:
            continue
        dfs(v2,d+dd)

dfs(K,0)

ans = [0] * Q
for i in range(Q):
    x,y = map(int,input().split())
    ans[i] = distance[x]+distance[y]
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
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))
Q,K = map(int,input().split())
distance = [None] * (N+1)
def dfs(v1,d):
    distance[v1] = d
    for v2,dd in edge[v1]:
        if distance[v2] is not None:
            continue
        dfs(v2,d+dd)

dfs(K,0)

ans = [0] * Q
for i in range(Q):
    x,y = map(int,input().split())
    ans[i] = distance[x]+distance[y]
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import heapq
import sys

input = sys.stdin.readline

def dijkstra(s, edge, N):
    d = [float('inf')] * N
    used = [True] * N
    d[s] = 0
    used[s] = False
    edgelist = []
    for a, b in edge[s]:
        heapq.heappush(edgelist, a * (10 ** 6) + b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)

        if not used[minedge%(10 ** 6)]:
            continue
        v = minedge % (10 ** 6)
        d[v] = minedge // (10 ** 6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, (e[0] + d[v]) * (10 ** 6) + e[1])
    return d

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



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
abc=[tuple(map(int,input().split())) for i in range(N-1)]
g=[set() for i in range(N)]
for a,b,c in abc:
  g[a-1].add((b-1,c))
  g[b-1].add((a-1,c))
memo=[-1]*N

Q,K=map(int,input().split())
import collections
q=collections.deque([(K-1,0)])
memo[K-1]=0
while(q):
  
  x,w = q.popleft()
  for a,b in g[x]:
    if memo[a]==-1:
      memo[a]=w+b
      q.append((a,w+b))
  
for i in range(Q):
  x,y=map(int,input().split())
  print(memo[x-1]+memo[y-1])

Submission status: Accepted

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: Accepted

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**20
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: Accepted

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**20
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: Accepted

Solution code:
import heapq
def dijkstra(n, edges, s):
    min_dist = [float('inf')] * n
    min_dist[s] = 0
    next_v = []
    heapq.heappush(next_v, (0, s))
    path = [-1] * n
    
    while True:
        if len(next_v) == 0: break
        d, v = heapq.heappop(next_v)
        
        for u, d in edges[v]:
            if min_dist[u] > min_dist[v] + d:
                min_dist[u] = min_dist[v] + d
                heapq.heappush(next_v, (min_dist[u], u))
                path[u] = v
                
    return min_dist, path

n = int(input())
edges = [[] for _ in range(n)]

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


q, k = map(int, input().split())
dist, _ = dijkstra(n, edges, k-1)

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

Submission status: Accepted

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

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

INF=10**9+1
distFromK=[-1 for i in range(n)]

# start from K
stack=[]
stack.append([K-1,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  d=node[1]
  parent=node[2]
  if distFromK[v]==-1:
    distFromK[v]=d
  else:
    distFromK[v]=min(distFromK[v],d)
  targets=dist[v]
  for child in targets:
    if child[0]==parent or child[0]==v:
      continue
    stack.append([child[0],d+child[1],v])

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

Submission status: Accepted

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):
    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
    return dest

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    E[a-1].append((b-1, c))
    E[b-1].append((a-1, c))
Q,K = map(int, input().split())
qlist = [[int(q) for q in input().split()] for _ in range(Q)]

q = deque()
q.append((K-1, 0))
d = [-1]*N
d[K-1] = 0
while q:
    temp = q.popleft()
    p = temp[0]
    r = temp[1]
    for t in E[p]:
        if d[t[0]] < 0:
            d[t[0]] = r+t[1]
            q.append((t[0], r+t[1]))
            
for i in range(Q):
    print(d[qlist[i][0]-1]+d[qlist[i][1]-1])

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    tmd = collections.defaultdict(list)
    cl = collections.defaultdict(int)
    for i in range(n-1):
        tma, tmb, tmc = list(map(int, readline().split()))
        tmd[tma-1] += [tmb-1]
        tmd[tmb-1] += [tma-1]
        cl[tma-1, tmb-1] = tmc
        cl[tmb-1, tma-1] = tmc
    q, k = list(map(int, readline().split()))

    ql = [[0, k-1]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    fq[k-1]
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fq:
                    ql.append([cost + cl[tmv, tmp], tmv])
                    fq[tmv] = cost + cl[tmv, tmp]
                elif cost + cl[tmv, tmp] < fq[tmv]:
                    fq[tmv] = cost + cl[tmv, tmp]
        else:
            break
    for i in range(q):
        x, y = list(map(int, readline().split()))
        print(fq[x-1] + fq[y-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
n = int(input())
#値の初期化
path = [None]*(n + 1)
adjacent_list = [[] for i in range(n+1)]

for i in range(n - 1):
    a, b, c = list(map(int,input().split()))
    adjacent_list[a].append([b,c])
    adjacent_list[b].append([a,c])
#ノード番号、そこまでの距離,検索済みの要素を受け取る。
def dfs(node_n ,distance,finished):
    #検索済みに追加
    finished.add(node_n)
    #そこまでの距離を代入。値の更新などは特にない（はず）
    path[node_n] = distance
    #対象ノードに対する隣接リストをforで回す
    for i in adjacent_list[node_n]:
        next = i[0]
        if next not in finished:
            #検索済みでなかった場合、そこまでのコストを追加し再帰
            dfs(next, distance + i[1],finished)

q,k = list(map(int, input().split()))
dfs(k, 0, set())
#各クエリへの返答
for i in range(q):
    s, g = list(map(int, input().split()))
    print(path[s] + path[g])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200000)

n = int(input())
# 値の初期化
path = [None]*(n + 1)
adjacent_list = [[] for i in range(n+1)]

for i in range(n - 1):
    a, b, c = list(map(int, input().split()))
    adjacent_list[a].append([b, c])
    adjacent_list[b].append([a, c])
# ノード番号、そこまでの距離,検索済みの要素を受け取る。


def dfs(node_n, distance, finished):
    # 検索済みに追加
    finished.add(node_n)
    # そこまでの距離を代入。値の更新などは特にない（はず）
    path[node_n] = distance
    # 対象ノードに対する隣接リストをforで回す
    for i in adjacent_list[node_n]:
        next = i[0]
        if next not in finished:
            # 検索済みでなかった場合、そこまでのコストを追加し再帰
            dfs(next, distance + i[1], finished)


q, k = list(map(int, input().split()))
dfs(k, 0, set())
# 各クエリへの返答
for i in range(q):
    s, g = list(map(int, input().split()))
    print(path[s] + path[g])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for a, b, c in LIR(n - 1):
    G[a - 1] += [(b - 1, c)]
    G[b - 1] += [(a - 1, c)]

q, k = LI()
dq = deque([k - 1])
dist = [-1] * n
dist[k - 1] = 0
while dq:
    u = dq.popleft()
    for v, c in G[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + c
            dq += [v]

for _ in range(q):
    x, y = LI()
    print(dist[x - 1] + dist[y - 1])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for a, b, c in LIR(n - 1):
    G[a - 1] += [(b - 1, c)]
    G[b - 1] += [(a - 1, c)]

q, k = LI()
dq = deque([k - 1])
dist = [-1] * n
dist[k - 1] = 0
while dq:
    u = dq.pop()
    for v, c in G[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + c
            dq += [v]

for _ in range(q):
    x, y = LI()
    print(dist[x - 1] + dist[y - 1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import collections


N = int(input())
graph = [[] for _ in range(N)]
# graph = collections.defaultdict(list)

for i in range(N-1):
    # print(i)
    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(' '))

dist = [-1 for _ in range(N)]
dist[K-1] = 0
stack = [K-1]
while len(stack) != 0:
    a = stack.pop()
    for b, c in graph[a]:
        if dist[b] == -1:
            dist[b] = dist[a] + c
            stack.append(b)


# def dfs(a):
#     for b, c in graph[a]:
#         if dist[b] == -1:
#             dist[b] = dist[a] + c
#             dfs(b)
# dfs(K-1)
# print(dist)


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

Submission status: Accepted

Solution code:
def BFS(K, edges, N):
  roots = [ [] for i in range(N)]
  for a, b, c in edges:
    roots[a-1] += [(b-1, c)]
    roots[b-1] += [(a-1, c)]
  dist = [-1] * N
  stack = []
  stack.append(K)
  dist[K] = 0
  while stack:
    label = stack.pop(-1)
    for i, c in roots[label]:
      if dist[i] == -1:
        dist[i] = dist[label] + c
        stack += [i]
  return dist

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)]

distance = BFS(K - 1, abc, N)
for x, y in xy:
  print(distance[x - 1] + distance[y - 1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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
con = [-1] * n
con[k] = 0
stack = [k]
while stack:
  cur = stack.pop()
  for i,j in g[cur]:
    if con[i] == -1:
      con[i] = con[cur] + j
      stack.append(i)
for i in range(q):
  x,y = map(int,input().split())
  x-=1;y-=1
  print(con[x]+con[y])

Submission status: Accepted

Solution code:
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
con = [-1] * n
con[k] = 0
stack = [k]
while stack:
  cur = stack.pop()
  for i,j in g[cur]:
    if con[i] == -1:
      con[i] = con[cur] + j
      stack.append(i)
for i in range(q):
  x,y = map(int,input().split())
  x-=1;y-=1
  print(con[x]+con[y])

Submission status: Accepted

Solution code:
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
con = [-1] * n
con[k] = 0
stack = [k]
while stack:
  cur = stack.pop()
  for i,j in g[cur]:
    if con[i] == -1:
      con[i] = con[cur] + j
      stack.append(i)
for i in range(q):
  x,y = map(int,input().split())
  x-=1;y-=1
  print(con[x]+con[y])

Submission status: Accepted

Solution code:
import sys
import numpy as np
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import defaultdict

N = int(input())
lines = readlines()
graph = defaultdict(list)
for line in lines[:N-1]:
  a,b,c = map(int,line.split())
  graph[a].append((b,c))
  graph[b].append((a,c))
Q, K = map(int,lines[N-1].split())
XY = np.array([line.split() for line in lines[N:]],np.int64)

def degreesOfSeparation(graph,start):
    if start not in graph:
        return -1
    visited = set()
    frontier = set()
    table = [0] * (len(graph) + 1)
    degrees = 0
    visited.add(start)
    frontier.add(start)
    while len(frontier) > 0:
        #print(frontier,":",degrees)
        #degrees += 1
        newfront = set()
        for g in frontier:
            for next in graph[g]:
                if next[0] not in visited:
                    visited.add(next[0])
                    newfront.add(next[0])
                    table[next[0]] += next[1] + table[g]
        frontier = newfront
    return table
table = degreesOfSeparation(graph,K)
for q in range(Q):
  print(table[XY[q][0]] + table[XY[q][1]])

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i 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])
q,k=map(int,input().split())
qu=deque([[k-1,0]])
v=[0]*n
d=[0]*n
while len(qu)>0:
    s=qu.popleft()
    v[s[0]]=1
    for j in g[s[0]]:
        if not v[j[0]]:
            v[j[0]]=1
            d[j[0]]=s[1]+j[1]
            qu+=[[j[0],d[j[0]]]]
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Submission status: Accepted

Solution code:
n=int(input())
ki=[[] for _ in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  ki[a-1].append([b-1,c])
  ki[b-1].append([a-1,c])
q,k=map(int,input().split())
s=[0]*n
from collections import deque
d=deque()
d.append(k-1)
while d:
  g=d.popleft()
  for i in ki[g]:
    if s[i[0]]:
      continue
    d.append(i[0])
    s[i[0]]=s[g]+i[1]
for i in range(q):
  x,y=map(int,input().split())
  print(s[x-1]+s[y-1])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)
n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))        
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
q,k=map(int,input().split())
List=[0 for i in range(q)]
search(k)
for i in range(q):
    x,y=map(int,input().split())
    List[i]=anslist[x-1]+anslist[y-1]
for j in List:
    print(j)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))        
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
q,k=map(int,input().split())
List=[0 for i in range(q)]
search(k)
for i in range(q):
    x,y=map(int,input().split())
    List[i]=anslist[x-1]+anslist[y-1]
for j in List:
    print(j)

Submission status: Accepted

Solution code:
n=int(input())
abc=[list(map(int,input().split())) for i in range(n-1)]
q,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(q)]
lst=[0]*(n+1)
data=[[] for i in range(n+1)]
flag=[0]*(n+1)
for u in abc:
    a,b,c=u
    data[a].append([b,c])
    data[b].append([a,c])
que=[k]
flag[k]=1
while que:
    h=que.pop()
    for u in data[h]:
        d,c=u
        if flag[d]==0:
            lst[d]=lst[h]+c
            que.append(d)
            flag[d]=1
for u in xy:
    x,y=u
    print(lst[x]+lst[y])

Submission status: Accepted

Solution code:
N = int(input())
E ={i:[] for i in range(N+1)}
for i in range(N-1):
  a,b,c = [int(x) for x in input().split()]
  E[a].append([b,c])
  E[b].append([a,c])
Q,K = [int(x) for x in input().split()]
cost= [0]*(N+1)
stk=[[K,-1,0]]
while stk:
  v,p,c = stk.pop()
  if cost[v]!=0:
    continue
  cost[v]=c
  for i,j in E[v]:
    if i!=p:
      stk.append([i,v,c+j])
for i in range(Q):
  a,b = [int(x) for x in input().split()]
  print(cost[a]+cost[b])

Submission status: Accepted

Solution code:
def BFS(N,start,roots):
    dist = [-1] * N
    stack = []
    stack.append(start)
    dist[start] = 0
    while stack:
        label = stack.pop(-1)
        for i, c in roots[label]:
            if dist[i] == -1:
                dist[i] = dist[label] + c
                stack += [i]
    return dist
############################################################
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N = I()
v = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = LI()
    v[a-1].append([b-1,c])
    v[b-1].append([a-1,c])
Q, K =LI()

#print(BFS(N,K-1,v))
W = BFS(N,K-1,v)
ansC = []
for i in range(Q):
    x, y = LI()
    ansC.append(W[x-1]+W[y-1])

for v in ansC:
    print(v)

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    tmd = collections.defaultdict(list)
    tmdc = collections.defaultdict(int)
    for i in range(n-1):
        tma, tmb, tmc = list(map(int, input().rstrip('\n').split()))
        tmd[tma-1] += [tmb-1]
        tmd[tmb-1] += [tma-1]
        tmdc[tma-1, tmb-1] = tmc
        tmdc[tmb-1, tma-1] = tmc

    q, k = list(map(int, input().rstrip('\n').split()))
    ql = [[0, k-1]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    fq[k-1]
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fq or cost + tmdc[tmp, tmv] < fq[tmv]:
                    ql.append([cost + tmdc[tmp, tmv], tmv])
                    fq[tmv] = cost + tmdc[tmp, tmv]
        else:
            break
    for i in range(q):
        x, y = list(map(int, input().rstrip('\n').split()))
        print(fq[x-1] + fq[y-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 6)


def main():
    N = int(readline())
    edge = [[] for _ in range(N + 1)]

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

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

    distance = [None] * (N + 1)


    def measure_distance(v, d):
        distance[v] = d
        for vv, dd in edge[v]:
            if distance[vv] is not None:
                continue
            measure_distance(vv, d + dd)


    measure_distance(K, 0)

    xy = map(int, read().split())
    for x, y in zip(xy, xy):
        print(distance[x] + distance[y])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# bellman_ford : O(V E)
# dijkstra : O(E log V), 負辺は無理
# warshall_floyd : O(V**3)
# deque

from collections import deque
import sys

input = sys.stdin.readline


def solve():
    inf = 10 ** 14 + 10

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

    q, v = map(int, input().split())
    v -= 1

    d = [inf] * n
    d[v] = 0

    dq = deque()
    for cost, to in e[v]:
        dq.append((cost, to, v))
        # (cost, to, parent)

    while dq:
        c, v, p = dq.popleft()
        if d[v] != inf:
            continue
        d[v] = d[p] + c
        for cost, to in e[v]:
            if to == p:
                continue
            dq.append((cost, to, v))
            
    for _ in range(q):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        print(d[x] + d[y])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# bellman_ford : O(V E)
# dijkstra : O(E log V), 負辺は無理
# warshall_floyd : O(V**3)

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def solve():
    inf = 10 ** 14 + 10

    def dfs(v: 'vertex_index, 0-indexed') -> None:
        for c, t in e[v]:
            if d[t] != inf:
                continue
            d[t] = d[v] + c
            dfs(t)

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

    q, v = map(int, input().split())
    v -= 1

    d = [inf] * n
    d[v] = 0

    dfs(v)

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# bellman_ford : O(V E)
# dijkstra : O(E log V), 負辺は無理
# warshall_floyd : O(V**3)

from collections import namedtuple
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def solve():
    inf = 10 ** 14 + 10

    Edge = namedtuple('Edge', 'cost to')

    def dfs(v: 'vertex_index, 0-indexed') -> None:
        for e_ in e[v]:
            if d[e_.to] != inf:
                continue
            d[e_.to] = d[v] + e_.cost
            dfs(e_.to)

    n = int(input())
    e = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        e[a].add(Edge(cost=c, to=b))
        e[b].add(Edge(cost=c, to=a))

    q, v = map(int, input().split())
    v -= 1

    d = [inf] * n
    d[v] = 0

    dfs(v)

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import namedtuple
from heapq import heappop, heappush
import sys

input = sys.stdin.readline


def solve():
    inf = 10 ** 14 + 10

    Edge = namedtuple('Edge', ('cost', 'to'))

    def dijkstra(s):
        used = [False] * n
        used[s] = True

        dist = [inf] * n
        dist[s] = 0

        h = []
        for e_ in e[s]:
            heappush(h, e_)

        while h:
            c, v = heappop(h)
            if used[v]:
                continue
            used[v] = True
            dist[v] = c
            for e_ in map(lambda x: (x.cost + dist[v], x.to), e[v]):
                heappush(h, e_)
        return dist

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

    q, v = map(int, input().split())
    v -= 1

    g = dijkstra(v)

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


if __name__ == '__main__':
    solve()

# warshall_floyd
# n大で無理

# inf = 10 ** 14 + 10
#
# n = int(input())
# g = [[inf] * n for _ in range(n)]
# for i in range(n):
#     g[i][i] = 0
# for _ in range(n - 1):
#     a, b, c = map(int, input().split())
#     a -= 1
#     b -= 1
#     g[a][b] = c
#     g[b][a] = c
#
# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             g[i][j] = min(g[i][j], g[i][k] + g[k][j])
#
# q, v = map(int, input().split())
# v -= 1
# for _ in range(q):
#     x, y = map(int, input().split())
#     x -= 1
#     y -= 1
#     print(g[x][v] + g[v][y])
#