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:
from heapq import heappush, heappop

def dijkstra(s):
    '''
    始点sから各頂点への最短距離を求める
    '''
    d = [float("inf")] * n
    d[s] = 0
    used = [False] * n
    used[s] = True
    edgelist = []

    for e in edge[s]:
        heappush(edgelist, e)

    while edgelist:
        cost, v = heappop(edgelist)
        if used[v]:
            continue
        d[v] = cost
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(edgelist, [e[0] + d[v], e[1]])

    return d


n = int(input())

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

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

dist = dijkstra(k-1)

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

for v in res:
    print(v)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N=int(input())
T=[[] for _ in range(N)]
for i in range(N-1):
  a,b,c=map(int, input().split())
  T[a-1].append((b-1,c))
  T[b-1].append((a-1,c))
Q,K=map(int, input().split())

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

def dfs(start, nown):
  to=T[start]
  for t in to:
    next_node,c=t
    if dist[next_node]!=-1:
      continue
    nextn=nown+c
    dist[next_node]=nextn
    dfs(next_node, nextn)

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

Submission status: Accepted

Solution code:
n=int(input())
es=[[] for _ in range(n)]

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

q,k=map(int,input().split())
k-=1
dist=[float('inf')]*n

dist[k]=0
stack=[k]
while stack:
    now=stack.pop()
    for e,w in es[now]:
        if dist[e]==float('inf'):
            dist[e]=dist[now]+w
            stack.append(e)

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

Submission status: Accepted

Solution code:
n=int(input())
es=[[] for _ in range(n)]

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

from heapq import heappush, heappop
def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance


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

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))

node=[{} for _ in range(n)]
d=deque()
ans=[None]*n
for pair in v:
    node[pair[0]][pair[1]]=pair[2]+1
    node[pair[1]][pair[0]]=pair[2]+1
q,k=map(int,input().split())
d.append(k-1)
res=[-1]*n
res[k-1]=0
while True:
    if not d:
        break
    a=d.pop()
    for x in node[a]:
        if res[x]==-1:
            res[x]=node[a][x]+res[a]
            d.append(x)
for i in range(q):
  x,y=map(int,input().split())
  print(res[x-1]+res[y-1])

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))

N= int(input())

#n:node s:start
dlines = defaultdict(set)
for i in range(N-1):
    x,y,cost = inpl()
    dlines[x].add((cost,y))
    dlines[y].add((cost,x))

Q,K = inpl()
query = []
for _ in range(Q):
    x2,y2 = inpl()
    query.append((x2,y2))


def dijkstra_heap(n,s,dlines):
    d = [10**20]*(n+1)
    used = [True]*(n+1)
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in dlines[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 dlines[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

res = dijkstra_heap(N,K,dlines)
for order in query:
    print(res[order[0]]+res[order[1]])

Submission status: Accepted

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

def dfs(st, depth=0):
    dist[st] = depth
    for to, c in tree[st]:
        if dist[to]>=0:
            continue
        dfs(to, depth+c)


N = int(input())
tree = [[] for _ in range(N)]
dist = [-1]*N

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

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

Submission status: Accepted

Solution code:
from heapq import heapify,heappush,heappop
n = int(input())
INF = float("inf")
adj = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    adj[a].append((b,c))
    adj[b].append((a,c))
H = []
heapify(H)
searched = [0]*n
q,k = map(int,input().split())
k-=1
d = [INF]*n
d[k] = 0
heappush(H, (0,k))
while H:
    f = heappop(H)
    u = f[-1]
    searched[u] = 1
    if d[u] < f[0]:
        continue
    for j in range(len(adj[u])):
        v = adj[u][j][0]
        if searched[v]:
            continue
        if d[v] > d[u]+adj[u][j][-1]:
            d[v] = d[u]+adj[u][j][-1]
            heappush(H,(d[v],v))
for _ in range(q):
    x,y = map(int,input().split())
    x,y = x-1,y-1
    print(d[x]+d[y])

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))
print(*result, sep='\n')

Submission status: Accepted

Solution code:
def solve():
    import heapq
    n = int(input())
    g = [[] for _ in range(n)]
    for _ 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))
    inf = 10**15
    dist = [inf] * n

    def dijkstra(s):
        q = []
        dist[s] = 0
        heapq.heappush(q, [0, s])
        while q:
            p, v = heapq.heappop(q)
            if dist[v] < p:
                continue
            for i, x in g[v]:
                if dist[i] > dist[v] + x:
                    dist[i] = dist[v] + x
                    heapq.heappush(q, [dist[i], i])

    m, k = map(int, input().split())
    k = k - 1
    dijkstra(k)
    for _ in range(m):
        e, f = map(int, input().split())
        res = dist[e - 1] + dist[f - 1]
        print(res)


solve()

Submission status: Accepted

Solution code:
def solve():
    from collections import deque
    n = int(input())
    g = [[] for _ in range(n)]
    for _ 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))
    dist = [0] * n

    def dfs(v, p=-1, d=0):
        q = deque()
        q.append((v, p, d))
        while q:
            v, p, d = q.pop()
            dist[v] = d
            for i, x in g[v]:
                if i == p:
                    continue
                q.append((i, v, d + x))

    m, k = map(int, input().split())
    k = k - 1
    dfs(k)
    for _ in range(m):
        e, f = map(int, input().split())
        res = dist[e - 1] + dist[f - 1]
        print(res)


solve()

Submission status: Accepted

Solution code:
import queue
n=int(input())
INF=10**18
e=[[] for _ in range(n+1)]
d=[INF]*(n+1)
for i in range(n-1):
  a,b,c=map(int,input().split())
  e[a].append((b,c))
  e[b].append((a,c))
q,k=map(int,input().split())
que=queue.Queue()
que.put(k)
d[k]=0
while not que.empty():
  x=que.get()
  for i,c in e[x]:
    if d[i]==INF:
      que.put(i)
      d[i]=d[x]+c
for _ in range(q):
  x,y=map(int,input().split())
  print(d[x]+d[y])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
weights = {}

roots = [[] for i in range(N)]
for i in range(N - 1):
    a, b, c = LI()
    a -= 1
    b -= 1
    roots[a].append(b)
    roots[b].append(a)
    weights[(a,b)] = c
    weights[(b,a)] = c

Q, K = LI()
K -= 1
xy = [0 for i in range(Q)]
for i in range(Q):
    x, y = LI()
    x -= 1
    y -= 1
    xy[i] = [x, y]
"""
xyzで全部の通りを見つけるとN ** 3で無理
なので今回は木構造に注目してBFS or DFSで解いたらいいのでは？
重みを単純にグラフに持つと10**5 ** 2になってしまうので注意
"""

visited = [-1 for i in range(N)]
queue = collections.deque()
queue.append(K)
visited[K] = 0

while len(queue)> 0:
    node = queue.popleft()
    cnt = visited[node]
    for n_node in roots[node]:
        if visited[n_node] == -1:
            visited[n_node] = cnt + weights[(node, n_node)]
            queue.append(n_node)

for x, y in xy:
    print(visited[x] + visited[y])

Submission status: Accepted

Solution code:
import sys
from collections import deque

N = int(sys.stdin.readline())

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

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

# Kを始点とする、各点までの距離
dist = [-1 for _ in range(N)]

visited = set()
q = deque([(K-1, 0)])
while q:
    p, c = q.popleft()
    if p in visited:
        continue
    dist[p] = c

    visited.add(p)
    for (next_p, next_c) in edges[p]:
        q.append((next_p, c + next_c))
# print(dist)

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

Submission status: Accepted

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	graph = [[] for _ in range(n)]
	for _ in range(n-1):
		a, b, d = tin()
		graph[a-1].append((b-1, d))
		graph[b-1].append((a-1, d))
	#s = input()
	q, k = tin()
	dist = [-1]*n
	dist[k-1] = 0
	qu=queue.Queue()
	qu.put(k-1)
	while not qu.empty():
		pos = qu.get()
		for v, d in graph[pos]:
			if dist[v] == -1:
				dist[v] = dist[pos] + d
				qu.put(v)
	
	for _ in range(q):
		f, t = tin()
		print(dist[f-1] + dist[t-1])
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
d = [-1 for i in range(n)]
e = [[] for i in range(n)]
for i 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())
def dfs(cur, par, di):
    d[cur] = di
    for i in e[cur]:
        if d[i[0]] == -1:
            if i == par:
                continue
            dfs(i[0], cur, di + i[1])
dfs(k - 1, -1, 0)
for i in range(q):
    x, y = map(int, input().split())
    print(d[x - 1] + d[y - 1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

N = int(input())
adj = [[] for _ in range(N)]
rtree = [None] * N

def dfs(v,parent,dist):
    rtree[v] = dist
    for u, c in adj[v]:
        if u == parent:
            continue
        dfs(u,v,dist+c)

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

    # Kを頂点とする根付き木を作成する
    dfs(K-1,-1,0)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)
# N = 5
# ARR = [
#     [1, 2, 1],
#     [1, 3, 1],
#     [2, 4, 1],
#     [3, 5, 1]
# ]
#
# Q, K = 3, 1
#
# BRR = [
#     [2, 4],
#     [2, 3],
#     [4, 5],
# ]
#
#

N = int(input())

ARR = [list(map(int,input().split())) for i in range(N-1)]

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

BRR = [list(map(int,input().split())) for i in range(Q)]



def prepare(arr, n):
    links = [[] for i in range(n)]
    depth = [0 for i in range(n)]
    for i in range(n - 1):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1
        dist = arr[i][2]

        links[startNode].append((endNode, dist))
        links[endNode].append((startNode, dist))

    return links, depth


def dfs(currentNode, parrentNode=-1, dist=0):
    childNodes = links[currentNode]
    depths[currentNode] = dist
    for (childNode, childDistance) in childNodes:
        if childNode == parrentNode:
            continue

        dfs(childNode, currentNode, dist + childDistance)


links, depths = prepare(ARR, N)

dfs(K - 1)

for i in range(Q):
    p1 = BRR[i][0] - 1
    p2 = BRR[i][1] - 1

    d1 = depths[p1]
    d2 = depths[p2]

    print(d1 + d2)

Submission status: Accepted

Solution code:
from collections import deque
#
# N = 5
# ARR = [
#     [1, 2, 1],
#     [1, 3, 1],
#     [2, 4, 1],
#     [3, 5, 1]
# ]
#
# Q, K = 3, 1
#
# BRR = [
#     [2, 4],
#     [2, 3],
#     [4, 5],
# ]
#
#
# N = 7
# ARR = [
#     [1, 2, 1],
#     [1, 3, 3],
#     [1, 4, 5],
#     [1, 5, 7],
#     [1, 6, 9],
#     [1, 7, 11],
# ]
#
# Q, K = 3, 2
#
# BRR = [
#     [1, 3],
#     [4, 5],
#     [6, 7],
# ]
#
#
# N = 10
# ARR = [
#     [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]
# ]
#
# Q, K = 1, 1
#
# BRR = [
#     [9, 10]
# ]


N = int(input())

ARR = [list(map(int,input().split())) for i in range(N-1)]

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

BRR = [list(map(int,input().split())) for i in range(Q)]


def prepare(n, arr):
    links = {}
    nodeStatus = {}
    distances = {}
    finalDistance = {}
    for i in range(1, N + 1):
        nodeStatus.__setitem__(i, False)
        finalDistance.__setitem__(i, 0)

    for i in range(len(arr)):
        tmp = arr[i]
        startNode = tmp[0]
        endNode = tmp[1]
        distance = tmp[2]
        distances.__setitem__((startNode, endNode), distance)
        distances.__setitem__((endNode, startNode), distance)
        if links.get(startNode) == None:
            links.__setitem__(startNode, [endNode])
        else:
            tmpChild = links.get(startNode)
            tmpChild.append(endNode)
            links.__setitem__(startNode, tmpChild)

        if links.get(endNode) == None:
            links.__setitem__(endNode, [startNode])
        else:
            tmpChild = links.get(endNode)
            tmpChild.append(startNode)
            links.setdefault(endNode, tmpChild)
    return links, nodeStatus, distances, finalDistance


def bfs(startNode):
    q = deque()

    q.append((startNode, 0))

    while len(q):
        currentNode, dist = q.popleft()
        finalDistance.__setitem__(currentNode, dist)
        nodeStatus.__setitem__(currentNode, True)

        childNodes = links.get(currentNode)

        for childNode in childNodes:
            if nodeStatus.get(childNode) == False:
                q.append((childNode, dist + distances.get((currentNode, childNode))))


links, nodeStatus, distances, finalDistance = prepare(N, ARR)

# print(links)
# print(nodeStatus)
# print(distances)
# print(finalDistance)


bfs(K)
for i in range(Q):
    dist1 = finalDistance[BRR[i][0]]
    dist2 = finalDistance[BRR[i][1]]
    print(dist1 + dist2)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
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())

# 前処理
dist = [-1] * n

def dfs(st, depth=0):
    dist[st] = depth
    for to, c in g[st]:
        if dist[to] >= 0: continue
        dfs(to, depth+c)

dfs(k-1, 0)

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

Submission status: Accepted

Solution code:
import heapq

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

Q, K = map(int, input().split())
memo = [float('inf')]*(N+1)
memo[K] = 0
h = [(0,K)]
while h:
  t = heapq.heappop(h)
  if t[0] > memo[t[1]]:
    continue
  for k in dic[t[1]]:
    if memo[k[0]] > t[0] + k[1]:
      memo[k[0]] = t[0] + k[1]
      heapq.heappush(h, (memo[k[0]], k[0]))
      
for _ in range(Q):
  x, y = map(int, input().split())
  print(memo[x]+memo[y])

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
e=[[] for _ in range(n+1)]
dist=[-1]*(n+1)
for i in range(n-1):
    a,b,c=map(int,input().split())
    e[a].append((b,c))
    e[b].append((a,c))
q,k=map(int,input().split())
a=deque()
a.append((k,0))
while a:
    x,d=a.popleft()
    dist[x]=d
    for j,nc in e[x]:
        if dist[j]!=-1:
            continue
        else:
            a.append((j,d+nc))
ans=[]
for i in range(q):
    x,y=map(int,input().split())
    ans.append(dist[x]+dist[y])
print(*ans,sep="\n")

Submission status: Accepted

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

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

r = 0
dist = [0]*N

prv = [None]*N
depth = [0]*N

def dfs(v):
    for u in G[v]:
        if dist[u] > 0 or u ==r: continue
        dist[u] = dist[v] + length[(v, u)]
        depth[u] = depth[v] + 1
        prv[u] = v
        dfs(u)

dfs(r)

# N: 頂点数
# G[v]: 頂点vの子頂点 (親頂点は含まない)
#
# - construct
# prv[u] = v: 頂点uの一つ上の祖先頂点v
# - lca
# kprv[k][u] = v: 頂点uの2^k個上の祖先頂点v
# depth[u]: 頂点uの深さ (根頂点は0)

LV = (N-1).bit_length()
def construct(prv):
    kprv = [prv]
    S = prv
    for k in range(LV):
        T = [0]*N
        for i in range(N):
            if S[i] is None:
                continue
            T[i] = S[S[i]]
        kprv.append(T)
        S = T
    return kprv

def lca(u, v, kprv, depth):
    dd = depth[v] - depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd

    # assert depth[u] <= depth[v]
    for k in range(LV+1):
        if dd & 1:
            v = kprv[k][v]
        dd >>= 1

    # assert depth[u] == depth[v]
    if u == v:
        return u

    for k in range(LV-1, -1, -1):
        pu = kprv[k][u]; pv = kprv[k][v]
        if pu != pv:
            u = pu; v = pv

    # assert kprv[0][u] == kprv[0][v]
    return kprv[0][u]

kprv = construct(prv)

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

ans = []
for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    xr = lca(x, K, kprv, depth)
    yr = lca(y, K, kprv, depth)
    a = dist[x] + dist[K] - dist[xr]*2 + dist[y] + dist[K] - dist[yr]*2
    ans.append(a)

print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import heapq
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1].append([c, b - 1])
    G[b - 1].append([c, a - 1])
Q, K = map(int, input().split())

def dijkstra(s, N, G):
    d = [float('inf')] * N
    d[s] = 0
    hq = [[0, s]]
    heapq.heapify(hq)
    while len(hq) > 0:
        v, i = heapq.heappop(hq)
        if d[i] < v:
            continue
        for c, j in G[i]:
            if d[j] > d[i] + c:
                d[j] = d[i] + c
                heapq.heappush(hq, [d[j], j])
    return d

D = dijkstra(K - 1, N, G)

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

for d in dist:
    print(d)

Submission status: Accepted

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

INF = 10 ** 18

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for e in G[v]:
            if dist[e.end] > dist[v] + e.cost:
                dist[e.end] = dist[v] + e.cost
                heapq.heappush(h, (dist[e.end], e.end))
    return dist


n = int(input())
es = [[] for i in range(n)]

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

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

d = dijkstra(n, es, k)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
edge=[[] for i in range(n)]
for i in range(n-1):
    x,y,z=map(int,input().split())
    edge[x-1].append([y-1,z])
    edge[y-1].append([x-1,z])
q,k=map(int,input().split())
dist=[-1]*n
def dfs(node,d):
    dist[node]=d
    for i in edge[node]:
        if dist[i[0]]==-1:
            dfs(i[0],d+i[1])
dfs(k-1,0)
for i in range(q):
    x,y=map(int,input().split())
    print(dist[x-1]+dist[y-1])

Submission status: Accepted

Solution code:
import sys
import heapq

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


INF = 10**18


def dijkstra(N, s0, edge):

    d = [INF] * N  # 始点からの距離
    used = [False] * N  # 探索済みリスト
    edgelist = [(0, s0)]  # 始点はコスト0で初期化
    heapq.heapify(edgelist)  # ヒープにpush

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in edge[v]:
            if d[e[1]] <= (e[0] + d[v]) or used[e[1]]:
                continue
            heapq.heappush(edgelist, [e[0] + d[v], e[1]])
    return d


def main():
    N = in_n()

    edge = [[]for _ in range(N)]
    for i in range(N - 1):
        a, b, c = in_nn()
        a, b = a - 1, b - 1
        edge[a].append((c, b))
        edge[b].append((c, a))

    Q, K = in_nn()
    d = dijkstra(N, K - 1, edge)

    ans = []
    for i in range(Q):
        x, y = in_nn()
        x, y = x - 1, y - 1
        ans.append(d[x] + d[y])

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# ダイクストラ法
# 重み付きグラフ関係により最短経路のリストを作る
# 有向グラフで優先度付きキューで探索

from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')

def dijkstra(s,n,g):
    seen = [False]*n
    cost = [INF]*n
    cost[s] = 0 #スタートはコスト0
    next_q = [(0,s)]
    heapify(next_q)
    while len(next_q)>0:
        c, i = heappop(next_q)
        if cost[i] < c:
            continue
        for nedge, ncost in g[i]:
            nc = cost[i]+ncost
            if cost[nedge]>nc:
                cost[nedge] = nc
                heappush(next_q,(nc, nedge))
    return cost

def main():
    N = int(input())
    graph_F = [[] for _ in range(N)]
#    graph_R = [[] for _ in range(N)]
    #リストの作成
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        graph_F[a].append((b,c))
        graph_F[b].append((a,c))
#        graph_R[b].append((a,c))

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

if __name__ == '__main__':
    main()

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))
print(*result, sep='\n')

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))
#print(*result, sep='\n')

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))
print(*result, sep='\n')

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))
#print(*result, sep='\n')

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(*result, sep='\n')
#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(*result, sep='\n')
print('\n'.join(str(v) for v in result))