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:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()
    adj = [[] for _ in range(n)]

    for _ in range(n-1):
        a, b, dist = mi()
        a -= 1
        b -= 1
        adj[a].append((b, dist))
        adj[b].append((a, dist))
    
    q, k = mi()
    k -= 1
    query = [lmi_0() for _ in range(q)]

    dist_from_k = [0] * n    
    visited = [False] * n
    def bfs_queue_traverse(start):
        queue = deque()    # ind, dist
        queue.append([start, 0])
        while queue:
            current, dist = queue.popleft()
            if not visited[current]:
                visited[current] = True
                dist_from_k[current] = dist
                for v, next_dist in adj[current]:
                    if not visited[v]:
                        queue.append((v, dist + next_dist))
    
    bfs_queue_traverse(k)
    for x, y in query:
        print(dist_from_k[x] + dist_from_k[y])



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
abc = [LIST() for _ in range(N-1)]

graph = defaultdict(list)
for a, b, c in abc:
	graph[a-1].append((b-1, c))
	graph[b-1].append((a-1, c))

Q, K = MAP()
xy = [LIST() for _ in range(Q)]

dist = [-1]*N
dist[K-1] = 0

def dfs(node):
	for to, cost in graph[node]:
		if dist[to] == -1:
			dist[to] = dist[node] + cost
			dfs(to)

dfs(K-1)
#print(dist)

for x, y in xy:
	print(dist[x-1] + dist[y-1])

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
abc = [LIST() for _ in range(N-1)]

graph = defaultdict(list)
for a, b, c in abc:
	graph[a-1].append((b-1, c))
	graph[b-1].append((a-1, c))

Q, K = MAP()
xy = [LIST() for _ in range(Q)]

dist = [-1]*N
dist[K-1] = 0

def dfs(node):
	for to, cost in graph[node]:
		if dist[to] != -1:
			continue
		dist[to] = dist[node] + cost
		dfs(to)

dfs(K-1)
#print(dist)

for x, y in xy:
	print(dist[x-1] + dist[y-1])

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
abc = [LIST() for _ in range(N-1)]
Q, K = MAP()
xy = [LIST() for _ in range(Q)]

connection = [[] for _ in range(N)]
for a, b, c in abc:
	connection[a-1].append((b-1, c))
	connection[b-1].append((a-1, c))

#print(connection)

step = [-1]*N

def DFS(N):
	for X, C in connection[N]:
		if step[X] == -1:
			step[X] = step[N] + C
			DFS(X)

step[K-1] = 0
DFS(K-1)

#print(step)

for x, y in xy:
	print(step[x-1] + step[y-1])

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
abc = [LIST() for _ in range(N-1)]
Q, K = MAP()
xy = [LIST() for _ in range(Q)]

connection = [[] for _ in range(N)]
for a, b, c in abc:
	connection[a-1].append((b-1, c))
	connection[b-1].append((a-1, c))

#print(connection)

step = [-1]*N
step[K-1] = 0
q = deque([K-1])

while q:
	p = q.pop()
	for X, C in connection[p]:
		if step[X] == -1:
			step[X] = step[p] + C
			q.append(X)

#print(step)

for x, y in xy:
	print(step[x-1] + step[y-1])

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
abc = [LIST() for _ in range(N-1)]
Q, K = MAP()
xy = [LIST() for _ in range(Q)]

connection = [[] for _ in range(N)]
for a, b, c in abc:
	connection[a-1].append((b-1, c))
	connection[b-1].append((a-1, c))

#print(connection)

step = [-1]*N
step[K-1] = 0
q = deque([K-1])

while q:
	p = q.popleft()
	for X, C in connection[p]:
		if step[X] == -1:
			step[X] = step[p] + C
			q.append(X)

#print(step)

for x, y in xy:
	print(step[x-1] + step[y-1])

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
ABC = [LIST() for _ in range(N-1)]
Q, K = MAP()
xy = [LIST() for _ in range(Q)]

connection = [[] for _ in range(N)]

for i in range(N-1):
	connection[ABC[i][0]-1].append((ABC[i][1]-1, ABC[i][2]))
	connection[ABC[i][1]-1].append((ABC[i][0]-1, ABC[i][2]))

#print(connection)

step = [-1]*N
step[K-1] = 0

q = deque([K-1])


while q:
	N = q.popleft()
	for x, C in connection[N]:
		#print(x, C)
		if step[x] == -1:
			step[x] = step[N] + C
			#print(step)
			q.append(x)


#print(step)

for x, y in xy:
	print(step[x-1] + step[y-1])

Submission status: Accepted

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

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

d = [float('inf')] * (N + 1)
d[K] = 0
q = [K]
while q:
    i = q.pop()
    for j, c in links[i]:
        if d[i] + c < d[j]:
            d[j] = d[i] + c
            q.append(j)

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
print('\n'.join(str(v) for v in result))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

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

d = [float('inf')] * (N + 1)
d[K] = 0
#prev = [None] * (N + 1)
q = [(0, K)]
while q:
    _, u = heappop(q)
    for v, c in links[u]:
        alt = d[u] + c
        if d[v] > alt:
            d[v] = alt
            #prev[v] = u
            heappush(q, (alt, v))

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
print('\n'.join(str(v) for v in result))

Submission status: Accepted

Solution code:
from collections import deque

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

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

d = [float('inf')] * (N + 1)
d[K] = 0
q = deque([K])
while q:
    i = q.popleft()
    di = d[i]
    for j, c in links[i]:
        if di + c < d[j]:
            d[j] = di + c
            q.append(j)

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
print('\n'.join(str(v) for v in result))

Submission status: Accepted

Solution code:
from collections import deque

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

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

d = [float('inf')] * (N + 1)
d[K] = 0
q = deque([K])
while q:
    i = q.popleft()
    for j, c in links[i]:
        if d[i] + c < d[j]:
            d[j] = d[i] + c
            q.append(j)

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
print('\n'.join(str(v) for v in result))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

N = int(input())
costs = {}
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    costs.setdefault(a, {})
    costs[a][b] = c
    costs.setdefault(b, {})
    costs[b][a] = c

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

d = [float('inf')] * (N + 1)
d[K] = 0
#prev = [None] * (N + 1)
q = [(0, K)]
while q:
    _, u = heappop(q)
    for v in costs[u]:
        alt = d[u] + costs[u][v]
        if d[v] > alt:
            d[v] = alt
            #prev[v] = u
            heappush(q, (alt, v))

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
print('\n'.join(str(v) for v in result))

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

gr = { i:[] for i in range(N+1)}

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

sta = deque([K])
dis = [10**10 for i in range(N+1)]
dis[K] = 0
sumi = [-1 for i in range(N+1)]

while len(sta) >= 1:
  a = sta.pop()
  sumi[a] += 1
  
  for j in gr[a]:
    if sumi[ j[0] ] != -1:
      continue
    else:
      sta.append(j[0])
      dis[j[0]] = dis[a] + j[1]
    
for i in range(Q):
  x,y = map(int,input().split())
  
  print(int(dis[x] + dis[y] ))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())

g = [[] for _ in range(N+1)]

for i 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())

cost = [-1] * (N+1)
cost[K] = 0
temp = [K]
while temp:
    p = temp.pop()
    for q in g[p]:
        if cost[q[0]] == -1:
            cost[q[0]] = cost[p] + q[1]
            temp.append(q[0])

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
def solve():
    N = int(input())
    G = defaultdict(list)

    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
    visited = [False] * N
    q = deque()
    q.append((K,0))
    visited[K] = True
    depth = [0] * N
    depth[K] = 0
    while len(q) > 0:
        now, d = q.popleft()
        for next,distance in G[now]:
            if not visited[next]:
                q.append((next,d+distance))
                visited[next] = True
                depth[next] = d+distance
        
    ans = []
    for i in range(Q):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        ans.append(depth[x] + depth[y])
    
    print(*ans,sep='\n')

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

N = int(input())
G = [[] for _ in range(N)]

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

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

def dfs(v, pv=-1, d=0):
  dist[v] = d
  for nv, nd in G[v]:
    if nv == pv:
      continue
    dfs(nv, v, d+nd)

dist = [0]*N
dfs(K-1)

for x, y in query:
  x, y = x-1, y-1
  print(dist[x] + dist[y])

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

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

L = [-1] * (N + 1)


def w(k):
    que = deque()
    L[k] = 0
    que.append((k, -1))
    while que:
        n, p = que.popleft()
        for nn, nv in edges[n]:
            if nn == p: continue
            L[nn] = L[n] + nv
            que.append((nn, n))


def main():
    q, k = [int(_) for _ in input().split()]
    w(k)
    for i in range(q):
        a, b = [int(_) for _ in input().split()]
        print(L[a] + L[b])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from queue import deque

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

q, k = map(int, input().split())
stack = deque([(0, k)])
costs = [0] * (n + 1)
visited = set()
while stack:
    c, p = stack.popleft()
    costs[p] = c
    visited.add(p)
    stack.extend((c + c2, p2) for c2, p2 in edges[p] if p2 not in visited)

ans = []
for _ in range(q):
    x, y = map(int, input().split())
    ans.append(costs[x] + costs[y])
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import heapq
import sys


def dijkstra(n, paths, root):
	total_cost = [10 ** 9] * (n + 1)
	total_cost[root] = 0

	not_checked = set(range(1, n + 1))
	checked = set()
	cur_node = root
	h = []

	while not_checked:
		checked.add(cur_node)
		not_checked -= {cur_node}

		for next_node, cost in paths[cur_node]:
			if next_node in not_checked:
				heapq.heappush(h, (total_cost[cur_node] + cost, next_node))

		if not_checked:
			cost, next_node = heapq.heappop(h)

			while next_node in checked:
				cost, next_node = heapq.heappop(h)

			cur_node = next_node
			total_cost[cur_node] = cost

	return total_cost
		

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

	n = int(readline().rstrip())

	path = []
	for _ in range(n + 1):
		path.append([])

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

	

	q, k = map(int, readline().rstrip().split())

	cost_from_k = dijkstra(n, path, k)

	for _ in range(q):
		x, y = map(int, readline().rstrip().split())
		print(cost_from_k[x] + cost_from_k[y])


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = 10**15

def dijkstra(s, edges):
    n = len(edges)
    que = []
    d = [INF] * n
    prev = [-1] * n
    d[s] = 0
    heappush(que, (0, s))

    while len(que) > 0:
        (c, v) = heappop(que)
        if d[v] < c:
            continue
        for (cc, w) in edges[v]:
            if d[w] > d[v] + cc:
                d[w] = d[v] + cc
                prev[w] = v
                heappush(que, (d[w], w))

    return d, prev

n = int(input())
edge = [[] for i in range(n)]
for i in range(n-1):
    ai, bi, ci = map(int, input().split())
    ai, bi = ai-1, bi-1
    edge[ai].append((ci, bi))
    edge[bi].append((ci, ai))

q, k = map(int, input().split())
x, y = [], []
for i in range(q):
    xi, yi = map(int, input().split())
    xi, yi = xi-1, yi-1
    x.append(xi)
    y.append(yi)

dist, prev = dijkstra(k-1, edge)

for i in range(q):
    print(dist[x[i]]+dist[y[i]])

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n=int(input())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  l[a-1].append([b-1,c])
  l[b-1].append([a-1,c])
ans=[-1]*n
q,k=map(int,input().split())
ans[k-1]=0
d=deque([k-1])
while d:
  now=d.pop()
  for x in l[now]:
    a,b=x
    if ans[a]<0:
      ans[a]=ans[now]+b
      d.appendleft(a)
for i in range(q):
  a,b=map(int,input().split())
  print(ans[a-1]+ans[b-1])

Submission status: Accepted

Solution code:
n=int(input())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  l[a-1].append([b-1,c])
  l[b-1].append([a-1,c])
ans=[-1]*n
q,k=map(int,input().split())
ans[k-1]=0
from collections import deque
d=deque([k-1])
while d:
  now=d.pop()
  for x in l[now]:
    a,b=x
    if ans[a]<0:
      ans[a]=ans[now]+b
      d.appendleft(a)
for i in range(q):
  a,b=map(int,input().split())
  print(ans[a-1]+ans[b-1])

Submission status: Accepted

Solution code:
n=int(input())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  l[a-1].append([b-1,c])
  l[b-1].append([a-1,c])
ans=[-1]*n
q,k=map(int,input().split())
ans[k-1]=0
from collections import deque
d=deque([k-1])
while d:
  now=d.pop()
  for x in l[now]:
    a,b=x
    if ans[a]<0:
      ans[a]=ans[now]+b
      d.append(a)
for i in range(q):
  a,b=map(int,input().split())
  print(ans[a-1]+ans[b-1])

Submission status: Accepted

Solution code:
# D - Transit Tree Path
# https://atcoder.jp/contests/abc070/tasks/abc070_d

from heapq import heappop, heappush

INF = float("inf")

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)]
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child, child_d in G[v]:
            if dist[child] > dist[v] + child_d:
                dist[child] = dist[v] + child_d
                heappush(hq, (dist[child], child))
    return dist

n = int(input())
edge = [list(map(int, input().split())) for _ in range(n - 1)]
graph = [[] for _ in range(n)]

for a, b, c in edge:
    graph[a - 1].append((b - 1, c))
    graph[b - 1].append((a - 1, c))

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

d = dijkstra(n, graph, k - 1)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque
N = int(input())
w = defaultdict(int)
edge = [[] for _ in range(N + 1)]

for _ in range(N - 1):
    a, b, c = map(int, input().split())
    w[str(a) + "_" + str(b)] = c
    w[str(b) + "_" + str(a)] = c
    edge[a].append(b)
    edge[b].append(a)

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

root = K
done = [True for _ in range(N + 1)]
done[root] = False
d = [0 for _ in range(N + 1)]
q = deque([root])

while q:
    parent = q.pop()
    for child in edge[parent]:
        if done[child]:
            key = str(parent) + "_" + str(child)
            done[child] = False
            d[child] = d[parent] + w[key]
            q.append(child)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


# Kから順に探索して、Kからの距離を求める
def dfs(v, parent=-1, distance=0):
    # Kから現在の位置までの距離を記録する
    sum_distance[v] = distance
    for i, j in tree[v]:
        if i == parent:
            continue
        dfs(i, v, distance+j)


N = int(input())

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

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

# 事前に各頂点から頂点Kまでの距離を求める
sum_distance = [0]*N
dfs(K-1)

# クエリを処理する。xからKまでとyからKまでの距離の合計を求める
for _ in range(Q):
    x, y = map(int, input().split())
    print(sum_distance[x-1]+sum_distance[y-1])

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
tree=[[] for i in range(n+1)]
for i in range(n-1):
    a,b,c=mp()
    tree[a].append((b,c))
    tree[b].append((a,c))
q,k=mp()
dist=[-1]*(n+1)
dist[k]=0
deq=deque()
deq.append(k)

while len(deq):
    p=deq.popleft()
    for x,y in tree[p]:
        if dist[x]==-1:
            dist[x]=dist[p]+y
            deq.append(x)
for i in range(q):
    xi,yi=mp()
    print(dist[xi]+dist[yi])

Submission status: Accepted

Solution code:
from collections import deque


class UnionFindWeighted:
    """ポテンシャル付きUnionFind"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.weight = [0] * n
        self.cnt = n
        self.INF = 10 ** 18

    def root(self, x):
        """頂点xの根を求める"""
        if self.parent[x] < 0:
            return x
        rt = self.root(self.parent[x])
        self.weight[x] += self.weight[self.parent[x]]
        self.parent[x] = rt
        return rt

    def merge(self, x, y, weight):
        """頂点xを含む集合と頂点y含む集合を結合する
        weight: 頂点yに対する頂点xのポテンシャル(頂点xの方がweight高い)
        """
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y:
            return
        if self.parent[root_x] < self.parent[root_y]:
            self.parent[root_x] += self.parent[root_y]
            self.parent[root_y] = root_x
            self.weight[root_y] = -weight + self.weight[x] - self.weight[y]
        else:
            self.parent[root_y] += self.parent[root_x]
            self.parent[root_x] = root_y
            self.weight[root_x] = weight - self.weight[x] + self.weight[y]
        self.cnt -= 1

    def is_same(self, x, y):
        """頂点x, yが同じ集合に属するかどうかを返す"""
        return self.root(x) == self.root(y)

    def diff(self, x, y):
        """頂点yに対する頂点xのポテンシャルを求める
        ただし、頂点x,y間にポテンシャルが定義されていない場合は INF を返す
        """
        if not self.is_same(x, y):
            return self.INF
        return self.weight[x] - self.weight[y]

    def get_size(self, x):
        """頂点xを含む集合の要素数を返す"""
        return -self.parent[self.root(x)]

    def get_cnt(self):
        """集合の個数を返す"""
        return self.cnt


n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
qq, k = map(int, input().split())
query = [list(map(int, input().split())) for i in range(qq)]
k -= 1

tree = [[] for i in range(n)]
for a, b, cost in info:
    a -= 1
    b -= 1
    tree[a].append((b, cost))
    tree[b].append((a, cost))

uf = UnionFindWeighted(n)
root = k
par = {root: -1}
q = deque([root])
while q:
    v = q.pop()
    for nxt_v, cost in tree[v]:
        if nxt_v in par:
            continue
        else:
            par[nxt_v] = v
            uf.merge(nxt_v, par[nxt_v], cost)
            q.append(nxt_v)

for a, b in query:
    a -= 1
    b -= 1
    print(uf.diff(a, k) + uf.diff(b, k))