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:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""



import heapq

def dijkstra():
    #n:辺数,w:スタート一
    #n,w = map(int,input().split())
    n = onem()
    edge = [[] for i in range(n)]
    dg = 10**7
    # edge[i]:[コスト]
    for i in range(n-1):
        x,y,z = map(int,input().split())
        x -= 1
        y -= 1
        edge[x].append(z*dg + y)
        edge[y].append(z*dg + x)
    q,w = m()
    s = w-1
    d = [-1]*n
    d[s] = 0

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

        

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        v,c = minedge%dg,minedge//dg
        if d[v] >= 0:
            continue
        d[v] = c
        for e in edge[v]:
            vNext = e%dg
            if d[vNext]:
                heapq.heappush(edgelist, (e//dg+d[v])*dg + vNext)

    

    for i in range(q):
        x,y = m()
        print(d[x-1]+d[y-1])


def warshall_floyd(n,d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

dijkstra()

Submission status: Accepted

Solution code:
## ダイクストラ法
#O(ElogV)
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

################################
# n,w = map(int,input().split()) #n:頂点数　w:辺の数
#
# edge = [[] for i in range(n)]
# #edge[i] : iから出る道の[重み,行先]の配列
# for i in range(w):
#     x,y,z = map(int,input().split())
#     edge[x].append([z,y])
#     edge[y].append([z,x])
# print(dijkstra_heap(0))
##

n = int(input())

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(n-1):
    x,y,z = map(int,input().split())
    x-=1
    y-=1
    edge[x].append([z,y])
    edge[y].append([z,x])

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

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


# input
# 7 10
# 0 1 2
# 0 2 5
# 1 2 4
# 2 3 2
# 1 3 6
# 1 4 10
# 3 5 1
# 4 5 3
# 4 6 5
# 5 6 9
# output
# [0, 2, 5, 7, 11, 8, 16]

######################################################################

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
inf = float("inf")
tree = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])
q, k = map(int, input().split())

depth = [inf] * (n+1)
visited = [False] * (n+1)
depth[k] = 0
queue = deque([k])
while queue:
    now = queue.popleft()
    visited[now] = True
    for i, v in tree[now]:
        if visited[i]:
            pass
        else:
            queue.append(i)
            depth[i] = min(depth[i], depth[now] + v)
for _ in range(q):
    x, y = map(int, input().split())
    ans = depth[x] + depth[y]
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
inf = float("inf")
tree = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])
q, k = map(int, input().split())

depth = [inf] * (n+1)
visited = [False] * (n+1)
depth[k] = 0
stack = [k]
while stack:
    now = stack.pop()
    visited[now] = True
    for i, v in tree[now]:
        if visited[i]:
            pass
        else:
            stack.append(i)
            depth[i] = min(depth[i], depth[now] + v)
for _ in range(q):
    x, y = map(int, input().split())
    ans = depth[x] + depth[y]
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline()[:-1]

from collections import defaultdict

sys.setrecursionlimit(10 ** 7)


def dfs(v, parent, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to == parent:
            continue
        dfs(to, v, d + cost)


depth = defaultdict(int)
tree = defaultdict(set)
n = int(input())
for i in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].add((b, c))
    tree[b].add((a, c))

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

# k からの距離をすべて求める
dfs(k, -1, 0)
for i in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    # (k - x の距離) + (k - y の距離)
    print(depth[x] + depth[y])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline()[:-1]

from collections import defaultdict

sys.setrecursionlimit(10 ** 7)


def dfs(v, parent, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to == parent:
            continue
        dfs(to, v, d + cost)


depth = defaultdict(int)
tree = defaultdict(list)
n = int(input())
for i 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 -= 1

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

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


def dfs(v, parent, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to == parent:
            continue
        dfs(to, v, d + cost)


depth = defaultdict(int)
tree = defaultdict(list)
n = int(input())
for i 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 -= 1

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

Submission status: Accepted

Solution code:
n = int(input())
abc=[]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    abc.append(tmp)
q,k = map(int, input().split())
que = []
for i in range(q):
    tmp = list(map(int,input().split()))
    que.append(tmp)

link = [[] for _ in range(n)]
for tmp in abc:
    link[tmp[0]-1].append([tmp[1]-1,tmp[2]])
    link[tmp[1]-1].append([tmp[0]-1,tmp[2]])

dist=[-1]*n

from collections import deque
Q = deque()
Q.append([k-1,0])

while Q:
    now,now_d=Q.popleft()

    for nxt in link[now]:
        if dist[nxt[0]]!=-1:
            continue
        nxt_d =nxt[1] + now_d
        dist[nxt[0]]=nxt_d
        Q.append([nxt[0],nxt_d])

for tmp in que:
    print(dist[tmp[0]-1] + dist[tmp[1]-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = int(input())
Edges = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    Edges[a].append((b,c))
    Edges[b].append((a,c))
D = [float('inf') for i in range(N)]
def dfs(v,p,d):
    D[v] = d
    for e1,e2 in Edges[v]:
        if e1 != p:
            dfs(e1,v,d+e2)
Q,K = map(int,input().split())
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:
from collections import defaultdict, deque

N = int(input())
neighbors = defaultdict(list)
for i in range(N - 1):
    ai, bi, ci = map(int, input().split())
    ai -= 1
    bi -= 1
    neighbors[ai].append((bi, ci))
    neighbors[bi].append((ai, ci))
Q, K = map(int, input().split())
K -= 1
queries = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(Q)]

queue = deque([K])
d = [0] * N
while len(queue) > 0:
    v = queue.pop()
    for child, ci in neighbors[v]:
        if child == K or d[child] != 0:
            continue
        d[child] = d[v] + ci
        queue.append(child)

for xi, yi in queries:
    print(d[xi] + d[yi])

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d
import sys
input = sys.stdin.readline
n =int(input())

edge = [[] for i in range(n)]
#edge[i] : [weght,to]
for i in range(n-1):
    a, b, c = map(int,input().split())
    a, b = a-1, b-1
    edge[a].append([c,b])
    edge[b].append([c,a]) 
q, k = map(int, input().split())
k = k-1
d = dijkstra_heap(k)
for i 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:
from collections import deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N-1)]
Q,K=map(int,input().split())
B=[list(map(int,input().split())) for i in range(Q)]
C=[[]for i in range(N)]
for a,b,c in A:
  a-=1
  b-=1
  C[a].append((b,c))
  C[b].append((a,c))
  
Q=[-1 for i in range(N)]
Q[K-1]=0
que=deque()
que.append(K-1)
while que:
  x=que.popleft()
  for i,j in C[x]:
    if Q[i]==-1:
      que.append(i)
      Q[i]=Q[x]+j
for x,y in B:
  print(Q[x-1]+Q[y-1])

Submission status: Accepted

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


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

for _ in range(n-1):
    _from, to, dist = map(int, input().split())
    edges[_from-1].append([to-1, dist])
    edges[to-1].append([_from-1, dist])

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

distance_from_k_to = [10**7] * n
distance_from_k_to[k] = 0

todo = []
while edges[k]:
    to, dist = edges[k].pop()
    todo.append([to, dist])

while todo:
    node, dist = todo.pop()
    if distance_from_k_to[node] != 10**7:  # if node has been seen
        continue

    distance_from_k_to[node] = dist
    while edges[node]:
        to, add_dist = edges[node].pop()
        todo.append([to, dist+add_dist])

for _ in range(q):
    start, goal = map(int, input().split())
    start, goal = start-1, goal-1
    ans = distance_from_k_to[start] + distance_from_k_to[goal]
    print(ans)

Submission status: Accepted

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

for _ in range(n-1):
    _from, to, dist = map(int, input().split())
    edges[_from-1].append([to-1, dist])
    edges[to-1].append([_from-1, dist])

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

distance_from_k_to = [10**7] * n
distance_from_k_to[k] = 0

todo = []
while edges[k]:
    to, dist = edges[k].pop()
    todo.append([to, dist])

while todo:
    node, dist = todo.pop()
    if distance_from_k_to[node] != 10**7:  # if node has been seen
        continue

    distance_from_k_to[node] = dist
    while edges[node]:
        to, add_dist = edges[node].pop()
        todo.append([to, dist+add_dist])

for _ in range(q):
    start, goal = map(int, input().split())
    start, goal = start-1, goal-1
    ans = distance_from_k_to[start] + distance_from_k_to[goal]
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
p = [deque([]) for _ in range(N)]

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

Q, K = [int(x) for x in input().strip().split()]

c = [-1] * N
f = [False] * N

def search(cp, cost):
    f[cp-1] = True
    for np, cos in p[cp-1]:
        if f[np-1]:
            continue
        c[np-1] = cost + cos
        f[np-1] = True
        search(np, cost + cos)

search(K, 0)
for q in range(Q):
    x, y = [int(x) for x in input().strip().split()]
    print(c[x-1]+c[y-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
n=int(input())
edges=[[] for i in range(n)]
for i 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())
depth=[0]*n
def dfs(child,parent,d):
  if edges[child]==parent:
    return
  depth[child]=d
  for newchild,distance in edges[child]:
    if newchild==parent:
      continue
    dfs(newchild,child,d+distance)
  return
dfs(k-1,-1,0)
for i in range(q):
  x,y=map(int,input().split())
  x-=1
  y-=1
  ans=depth[x]+depth[y]
  print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e15)


def bfs(s, g, N, G):

    return 0


def main():
    # sys.stdin = open("Sample.txt")
    N = Scanner.int()
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b, c = Scanner.map_int()
        a -= 1
        b -= 1
        G[a].append((b, c))
        G[b].append((a, c))
    Q, K = Scanner.map_int()
    K -= 1
    length = [0] * N
    q = []
    q.append(K)
    while q != []:
        i = q.pop()
        for n in G[i]:
            if length[n[0]] != 0:
                continue
            length[n[0]] = length[i] + n[1]
            q.append(n[0])
    query = Scanner.int_list_list(Q)
    for q in query:
        print(length[q[0] - 1] + length[q[1] - 1])
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist): #キューから値が無くなるまで
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)

################################
############input###############
################################
n = int(readline()) #n:頂点数　w:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(n-1):
    x,y,z = map(int,readline().split()) #始点,終点,重み(重みがないなら全部1に固定すること)
    x,y = x-1,y-1 #zero indexedされていないならこれやること
    edge[x].append([z,y])
    edge[y].append([z,x]) #こっちもつけると無向グラフ

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

fromk = dijkstra_heap(k-1)



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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
N = int(input())
dic = defaultdict(list)
for i in range(N-1):
  a, b, c = map(int, input().split())
  dic[a-1] += [(b-1,c)]
  dic[b-1] += [(a-1,c)]
Q, K = map(int, input().split())
deq = deque([(K-1,0)])
dist = [-1]*N
while deq:
  p, d = deq.popleft()
  for e, dd in dic[p]:
    if dist[e]==-1:
      dist[e] = d + dd
      deq += [(e,d+dd)]
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

input = sys.stdin.readline

d = []
ABC = []

sys.setrecursionlimit(10 ** 8)


def solve(i, dis):
    global d
    global ABC
    d[i] = dis

    for n, c in ABC[i]:
        if d[n] == -1:
            solve(n, dis + c)


def main():
    N = int(input())
    global ABC
    ABC = [[] for _ in range(N + 1)]
    global d
    d = [-1] * (N + 2)
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        ABC[a - 1].append([b - 1, c])
        ABC[b - 1].append([a - 1, c])

    Q, K = [int(x) for x in input().split()]

    solve(K - 1, 0)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def dfs(v: int, p: int = -1, s: int = 0):
    dist[v] = s
    for i, j in t[v]:
        if i == p:
            continue
        dfs(i, v, s + j)

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

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

dist = [0]*n

dfs(k)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

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

depth = [0 for _ in range(n)]
def dfs(v, p = -1, d = 0):
  depth[v] = d
  for i, j in abc[v]:
    if i == p:
      continue
    dfs(i, v, d+j)
dfs(k)


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

Submission status: Accepted

Solution code:
from collections import deque
def bfs(s):
	que = deque([])
	que.append(s-1)
	while que:
		v = que[0]
		que.popleft()
		for b, c in d[v]:
			if l[b] == 0:
				l[b] = l[v] + c
				que.append(b)
n = int(input())
l = [0 for i in range(n)]
d = [[] for i in range(n)]
for i in range(n-1):
	a, b, c = map(int, input().split())
	d[a-1].append((b-1,c))
	d[b-1].append((a-1,c))
q, k = map(int ,input().split())
bfs(k)
#print (l)
for i in range(q):
	x, y = map(int, input().split())
	print (l[x-1]+l[y-1])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from collections import defaultdict, deque
    N = int(input())
    G = [[] for i in range(N)]
    cost = defaultdict(int)
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        cost[a-1, b-1] = c
        cost[b-1, a-1] = c
    Q, K = (int(i) for i in input().split())
    dist = [-1 for _ in range(len(G))]

    def bfs(s):
        que = deque()
        dist[s] = 0
        que.append(s)
        while que:
            u = que.popleft()
            for v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = dist[u] + cost[v, u]
                que.append(v)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
g = [[] for x 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())
d = [-1] * (N+1)
d[K] = 0
r = deque()

r.append(K)
while len(r) > 0:
  i = r.popleft()
  for v in g[i]:
    if(d[v[0]] == -1):
      d[v[0]] = d[i] + v[1]
      r.append(v[0])

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

Submission status: Accepted

Solution code:
N= int(input())
abc = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = list(map(int,input().split()))
    a -= 1
    b -= 1
    abc[a].append((b,c))
    abc[b].append((a,c))
    
def dijkstra(node,start,abc):
    import heapq
    d = [float('inf') for i in range(N)]
    d[start] = 0
    d2 = [(0,start)]
    heapq.heapify(d2)
    while d2:
        c,v = heapq.heappop(d2)
        if d[v] < c:
            continue
        for t,cost in abc[v]:
            if d[v] + cost < d[t]:
                d[t] = d[v] + cost
                heapq.heappush(d2,(d[t],t))
    return d

Q,K = list(map(int,input().split()))
graph = dijkstra(N,K-1,abc)
for i in range(Q):
    x,y = list(map(int,input().split()))
    x -= 1
    y -= 1
    print(graph[x]+graph[y])

Submission status: Accepted

Solution code:
from collections import deque

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

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

    return [l[x - 1] + l[y - 1] for x, y in XY]

_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)]
print(*solve(_n, _ABC, _q, _k, _XY), sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
tree=[[] for _ in range(n)]
for i 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())
dis=[-1 for i in range(n)]
dis[k-1]=0
que=deque()
que.append(k-1)
while que:
  x=que.popleft()
  for i,c in tree[x]:
    if dis[i]==-1:
      que.append(i)
      dis[i]=dis[x]+c
for i in range(q):
  x,y=map(int,input().split())
  print(dis[x-1]+dis[y-1])

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    T = [[] for _ in range(N+1)]
    searched = [False]*(N+1)
    for _ in range(N-1):
        a,b,c = map(int, input().split())
        T[a].append((b,c))
        T[b].append((a,c))
        
    Q,K = map(int, input().split())
    distance = [10**9]*(N+1)
    distance[K] = 0
    
    # K から始める
    queue = [K]
    while queue:
        dom = queue.pop()
        if searched[dom]:
            continue
        searched[dom] = True
        for cod, d in T[dom]:
            if searched[cod]:
                continue
            queue.append(cod)
            distance[cod] = distance[dom]+d
            
        # print(dom, distance)
        
    # print(distance)
    
    for _ in range(Q):
        x,y = map(int, input().split())
        print(distance[x]+distance[y])
        
solve()

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

def log(*args):
    print(*args, file=sys.stderr)


n = int(input())
lines = sys.stdin.readlines()
edges = [ [] for _ in range(n+1) ]
for i in range(n-1):
    e = tuple(map(int, lines[i].split(" ")))
    log(e)
    edges[e[0]].append((e[1],e[2]))
    edges[e[1]].append((e[0],e[2]))

q,k = map(int, lines[n-1].split(" "))

ddd = [0] * (n+1)


que = deque()
que.append(k)
def bfs(x):
    for y, d in edges[x]:
        if ddd[y]:
            continue
        ddd[y] = ddd[x] + d
        que.append(y)


while que:
    bfs(que.pop())

for i in range(n, n+q):
    x, y = map(int, lines[i].split(" "))
    log(x,y)
    print(ddd[x] + ddd[y])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())

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

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

dist = [0] * (N + 1)


def dfs(v, p, d):
    dist[v] = d

    for n, dd in edges[v]:
        if n == p:
            continue
        dfs(n, v, d + dd)


dfs(K, -1, 0)

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