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:
# ABC070D - Transit Tree Path
import sys

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


def dfs(v: int, d) -> None:
    dist[v] = d
    for u, c in G[v]:  # search vertices available from v recursively
        if dist[u] is None:
            dfs(u, d + c)


def main():
    global G, dist
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    Q, K = tuple(map(int, input().split()))
    X = tuple(tuple(map(int, input().split())) for _ in range(Q))
    G = [[] for _ in range(N + 1)]  # graph, N+1: 1-idx
    for v, u, c in E:  # construct a graph
        G[v] += [(u, c)]
        G[u] += [(v, c)]
    dist = [None] * (N + 1)  # distance from vertex K
    dist[K] = 0
    dfs(K, 0)
    ans = [dist[x] + dist[y] for x, y in X]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC070D - Transit Tree Path
import sys

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


def dfs(v: int, p: int) -> None:
    d = dist[v]
    for u, c in G[v]:  # search vertices available from v recursively
        if u != p:  # p: parent
            dist[u] += d + c  # dist(K, v) + dist(v, u) == d + c
            dfs(u, v)


def main():
    global G, dist
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    Q, K = tuple(map(int, input().split()))
    X = tuple(tuple(map(int, input().split())) for _ in range(Q))
    G = [[] for _ in range(N + 1)]  # graph, N+1: 1-idx
    for v, u, c in E:  # construct a graph
        G[v] += [(u, c)]
        G[u] += [(v, c)]
    dist = [0] * (N + 1)  # distance from vertex K
    dfs(K, -1)
    ans = [dist[x] + dist[y] for x, y in X]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC070D - Transit Tree Path
import sys

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


def dfs(v: int, p: int, G: "List[List[int]]", dist: "List[int]") -> None:
    d = dist[v]
    for u, c in G[v]:  # search vertices available from v recursively
        if u != p:  # p: parent
            dist[u] += d + c  # dist(K, v) + dist(v, u) == d + c
            dfs(u, v, G, dist)


def main():
    global G, dist
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    Q, K = tuple(map(int, input().split()))
    X = tuple(tuple(map(int, input().split())) for _ in range(Q))
    G = [[] for _ in range(N + 1)]  # graph, N+1: 1-idx
    for v, u, c in E:  # construct a graph
        G[v] += [(u, c)]
        G[u] += [(v, c)]
    dist = [0] * (N + 1)  # distance from vertex K to i
    dfs(K, -1, G, dist)
    ans = [dist[x] + dist[y] for x, y in X]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC070D - Transit Tree Path
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def dfs(v: int, p: int) -> None:
    d = dist[v]
    for u, c in G[v]:  # search vertices available from v recursively
        if u != p:  # p: parent
            dist[u] += d + c  # dist(K, v) + dist(v, u) == d + c
            dfs(u, v)


def main():
    global G, dist
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    Q, K = tuple(map(int, input().split()))
    X = tuple(tuple(map(int, input().split())) for _ in range(Q))
    G = [[] for _ in range(N + 1)]  # graph, N+1: 1-idx
    for v, u, c in E:  # construct a graph
        G[v] += [(u, c)]
        G[u] += [(v, c)]
    dist = [0] * (N + 1)  # distance from vertex K
    dfs(K, -1)
    ans = [dist[x] + dist[y] for x, y in X]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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


sol()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

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

visited = [-1] * N
def bfs(a, dist) :
    for b, c in v[a] :
        if visited[b] < 0 :
            visited[b] = dist + c
            bfs(b, dist + c)
          
Q, K = map(int, input().split())
visited[K-1] = 0
bfs(K-1, 0)
for _ in range(Q) :
    x, y = map(int, input().split())
    print(visited[x-1] + visited[y-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

import collections

def first_search(graph, root, depth_array):
    seen, queue = set([root]), collections.deque([[root, 0],])
    while queue:
        vertex, depth = queue.popleft()  # popleft: 幅優先探索  /  pop: 深さ優先探索
        depth_array[vertex] = depth
        for node, length in graph[vertex]:
            if node not in seen:
                seen.add(node)
                queue.append([node, depth+length])

def main(): 
    N = II()

    from collections import defaultdict
    tree = defaultdict(list)

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

    Q, K = LI()

    depth_array = [0 for _ in range(N+1)]
    # K を根とした木だと思って全点の depth を決める。
    first_search(tree, K, depth_array)


    for _ in range(Q):
        x,y = LI()
        print(depth_array[x]+depth_array[y])


main()

Submission status: Accepted

Solution code:
import heapq

INF = float("inf")

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

E = [[] for _ in range(N+1)]
for a,b,c in G:
	E[a].append((c,b))
	E[b].append((c,a))

# Kからの最短距離
# dijkstra_heap
D = [INF,] * (N+1)
visited = [0,] * (N+1)

D[K] = 0
visited[K] = 1
qE = []

for e in E[K]:
	heapq.heappush(qE, e)

while qE:
	# コストが小さい順に取り出す
	c, b = heapq.heappop(qE)
	if visited[b]:
		continue
	D[b] = c
	visited[b] = 1

	# 現在地b → 次のエッジを追加
	for nc, nb in E[b]:
		if not visited[nb]:
			heapq.heappush(qE, (D[b]+nc, nb))

for x, y in W:
	print(D[x]+D[y])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
N = int(input())
E = defaultdict(list)
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 dijkstra(K, E, N):
d = [float("inf")] * N
d[K - 1] = 0
q = []
heappush(q, (K - 1, 0))
while q:
    now, dist = heappop(q)
    if d[now] < dist:
        continue

    for nxt, w in E[now]:
        t = dist + w
        if t < d[nxt]:
            d[nxt] = t
            heappush(q, (nxt, t))
for _ in range(Q):
    t1, t2 = map(int, input().split())
    print(d[t1 - 1] + d[t2 - 1])

Submission status: Accepted

Solution code:
"""
最小共通祖先(LCA, lowest common ancestor)を求める
"""
class LCA_doubling:
    """
    parent: ダブリングテーブル
    depth: 元の深さ
    """
    def __init__(self,g,root): #g: graph 
        def dfs(v,p): #p: parent of v
            if p != -1: self.depth[v] = self.depth[p]+1
            for c,d in g[v]:
                if c == p: continue
                self.parent[0][c] = v
                self.dist[0][c] = d
                dfs(c,v)

        def doubling_make_table(N,logN,Table,Dist):
            for i in range(1,logN):
                for j, Tiij in enumerate(Table[i-1]):
                    if Tiij != -1:
                        Table[i][j] = Table[i-1][Tiij]
                        Dist[i][j] = Dist[i-1][j] + Dist[i-1][Tiij]

        N = len(g)
        self.logN = len(bin(N))-2
        self.parent = [[-1]*N for _ in range(self.logN)]
        self.dist   = [[0]*N for _ in range(self.logN)]
        self.depth = [0]*(N) #ノードの深さ
        dfs(root,-1) #root を根とする木と見て計算
        doubling_make_table(N, self.logN, self.parent, self.dist) #ダブリングのテープル構築


    def getLCA(self,u,v): #u,vのdistを返す
        if self.depth[u] > self.depth[v]: u,v = v,u #vが深い
        d = 0
        dd = self.depth[v] - self.depth[u]
        for k in range(self.logN-1,-1,-1):
            if (dd >> k) & 1:
                d += self.dist[k][v]
                v = self.parent[k][v]
        if u == v: return u, d;
        for k in range(self.logN-1,-1,-1):
            if self.parent[k][u] != self.parent[k][v]:
                d += self.dist[k][u]
                d += self.dist[k][v]
                u,v = self.parent[k][u], self.parent[k][v]
        return self.parent[0][u], d+self.dist[0][u]+self.dist[0][v];

    def getdepth(self,u): #uの深さを返す
        return self.depth[u]



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

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

LCA = LCA_doubling(g, root=0)
#print(LCA.parent)
#print(LCA.depth)
#print(LCA.dist)

"""
ABC070D

"""
q,k = [int(i) for i in readline().split()]
k -= 1
for _ in range(q):
    a,b = [int(i)-1 for i in readline().split()]
    
    u1,d1 = LCA.getLCA(a,k)
    u2,d2 = LCA.getLCA(b,k)
    print(d1+d2)

Submission status: Accepted

Solution code:
N = int(input())

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

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

D = [-1] * N
s = [(K - 1, 0)]
while s:
  v, c = s.pop()
  D[v] = c
  for vv, cc in G[v]:
    if D[vv] < 0:
      s.append((vv, cc + c))

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

Submission status: Accepted

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

N = int(input())

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

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

D = [-1] * N
s = [(K - 1, 0)]
while s:
  v, c = s.pop()
  D[v] = c
  for vv, cc in G[v]:
    if D[vv] < 0:
      s.append((vv, cc + c))

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

Submission status: Accepted

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

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

G = [[] * N for _ in range(N)]
for a, b, c in ABC:
  G[a - 1].append((b - 1, c))
  G[b - 1].append((a - 1, c))

D = [-1] * N
s = [(K - 1, 0)]
while s:
  v, c = s.pop()
  D[v] = c
  for vv, cc in G[v]:
    if D[vv] < 0:
      s.append((vv, cc + c))
  
for x, y in XY:
  print(D[x - 1] + D[y - 1])

Submission status: Accepted

Solution code:
N = int(input())
ABC = [list(map(int, input().split())) for _ in range(N - 1)]
Q, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(Q)]

G = [[] * N for _ in range(N)]
for a, b, c in ABC:
  G[a - 1].append((b - 1, c))
  G[b - 1].append((a - 1, c))

D = [-1] * N
s = [(K - 1, 0)]
while s:
  v, c = s.pop()
  D[v] = c
  for vv, cc in G[v]:
    if D[vv] < 0:
      s.append((vv, cc + c))
  
for x, y in XY:
  print(D[x - 1] + D[y - 1])

Submission status: Accepted

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

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

G = [[] * N for _ in range(N)]
for a, b, c in ABC:
  G[a - 1].append((b - 1, c))
  G[b - 1].append((a - 1, c))

D = [-1] * N

def dfs(v, d):
  D[v] = d
  for i, c in G[v]:
    if D[i] < 0:
      dfs(i, d + c)

dfs(K - 1, 0)

for x, y in XY:
  print(D[x - 1] + D[y - 1])

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

q = deque([K - 1])
while q:
  n = q.popleft()
  for i, c in G[n]:
    if D[i] < 0:
      q.append(i)
      D[i] = D[n] + c

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

Submission status: Accepted

Solution code:
from collections import deque

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

G = [[] * N for _ in range(N)]
for a, b, c in ABC:
  G[a - 1].append((b - 1, c))
  G[b - 1].append((a - 1, c))

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

q = deque()
q.append(K - 1)
while q:
  n = q.popleft()
  for i, c in G[n]:
    if D[i] < 0:
      q.append(i)
      D[i] = D[n] + c

for x, y in XY:
  print(D[x - 1] + D[y - 1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
n = int(input())
edges = [[] for _ in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append((b, c))
    edges[b].append((a, c))

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

visited = [0] * n
d = [0] * n
def dfs(v, c):
    for u, c2 in edges[v]:
        if visited[u] == 0:
            d[u] = c + c2
            visited[u] = 1
            dfs(u, c + c2)

visited[k] = 1
dfs(k, 0)

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

Submission status: Accepted

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

from collections import deque

N = int(input())

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

Q, K = map(int, input().split())
distance = [-1] * (N + 1)
distance[K] = 0
que = deque()
q_append = que.append
for i in graph[K]:
    q_append(i)

q_left = que.popleft
while len(que) != 0:
    for _ in range(len(que)):
        abc = q_left()
        if distance[abc[0]] == -1: #動き先の値がまだ決まっていないとき
            distance[abc[0]] = distance[abc[1]] + abc[2]
            for j in graph[abc[0]]:
                q_append(j)
# print (distance)

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

Submission status: Accepted

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

from collections import deque

N = int(input())

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

Q, K = map(int, input().split())
distance = [-1] * (N + 1)
distance[K] = 0
que = deque()
for i in graph[K]:
    que.append(i)

while len(que) != 0:
    for _ in range(len(que)):
        abc = que.popleft()
        if distance[abc[0]] == -1: #動き先の値がまだ決まっていないとき
            distance[abc[0]] = distance[abc[1]] + abc[2]
            for j in graph[abc[0]]:
                que.append(j)
# print (distance)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
from collections import deque
sys.setrecursionlimit(10**6)
INF = float("inf")


class Graph(object):
    """グラフを扱うオブジェクト
    """

    def __init__(self, N):
        self.N = N
        self.edges = defaultdict(list)
        pass

    def add_edges(self, from_, to_, weight):
        """必ず0インデックスで入力すること。
        """
        self.edges[from_].append([to_, weight])
        self.edges[to_].append([from_, weight])
        pass


def LCA_constract(g: Graph, root=0):
    """
    木gにおいて、頂点u, vのLCA(Lowest Common Ancestor)を求める
    g: 木。無向グラフとして与える。
    u, v:頂点
    root: 根
    元: https://tjkendev.github.io/procon-library/python/graph/lca-doubling.html
    """
    N = g.N
    LN = int(math.log2(g.N))

    ###
    # 各頂点の親 parと各頂点の深さdepthを求める
    ###
    par = [INF]*N
    depth = [INF]*N

    que = deque()
    que.append([root, 0, None])
    while len(que) > 0:
        curr, dep, pre = que.popleft()
        par[curr] = pre
        depth[curr] = dep
        for n, w in g.edges[curr]:
            if n != pre:
                que.append([n, dep+w, curr])

    ###
    # 祖先 ancの構築
    ###

    anc = [par]

    for i in range(LN):
        buf = [None]*N
        for j in range(N):
            if anc[i][j] == None:
                continue
            buf[j] = anc[i][anc[i][j]]
        anc.append(buf)
    return anc, depth


def LCA_query(anc, depth, u: int, v: int):
    ###
    # 共通祖先を求める
    ###
    N = len(depth)
    LN = int(math.log2(g.N))

    dd = depth[v] - depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd

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

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

    for k in range(LN-1, -1, -1):
        pu = anc[k][u]
        pv = anc[k][v]
        if pu != pv:
            u = pu
            v = pv

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


def solve(N: int,
          a: "List[int]",
          b: "List[int]",
          c: "List[int]",
          Q: int,
          K: int,
          x: "List[int]",
          y: "List[int]"):

    g = Graph(N)
    for aa, bb, cc in zip(a, b, c):
        g.add_edges(*[aa-1, bb-1, cc])

    anc, depth = LCA_constract(g, root=K-1)

    for i in range(Q):
        print(depth[x[i]-1]+depth[y[i]-1])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]"
    b = [int()] * (N-1)  # type: "List[int]"
    c = [int()] * (N-1)  # type: "List[int]"
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (Q)  # type: "List[int]"
    y = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, a, b, c, Q, K, x, y)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n = int(input())
edges = [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)]

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

dis = [-1] * n
dis[k-1] = 0
stack = [k-1]

while stack:
    label = stack.pop(-1)
    for i,c in roots[label]:
        if dis[i] == -1:
            dis[i] = dis[label] + c
            stack.append(i)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    N = int(input())
    links = [[] for i in range(N+1)]
    for i in range(N-1):
        a, b, c = map(int, input().split())
        links[a].append([b, c])
        links[b].append([a, c])
    # print(links)
    Q, K = map(int, input().split())

    check = [False] * (N+1)
    cost = [0] * (N+1)
    q = deque()
    q.append([K, 0])
    while len(q) > 0:
        node, now_cost = q.popleft()
        check[node] = True
        cost[node] = now_cost
        for n in links[node]:
            # print(n)
            if not check[n[0]]:
                q.append([n[0], now_cost + n[1]])
    
    for i in range(Q):
        x, y = map(int, input().split())
        print(cost[x] + cost[y])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC70 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,c = map(int,input().split())
    g[a-1].append((b-1,c))
    g[b-1].append((a-1,c))
q,k = map(int,input().split())
que = deque()
que.append(k-1)
dist = [-1]*n
dist[k-1] = 0
while que:
    v = que.popleft()
    for x,c in g[v]:
        if dist[x] == -1:
            dist[x] = dist[v] + c
            que.append(x)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC70 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(input())
abc = [list(map(int,input().split())) for _ in range(n-1)]
q,k = map(int,input().split())

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

que = deque()
que.append(k-1)
dist = [-1]*n
dist[k-1] = 0
while que:
    v = que.popleft()
    for x,c in g[v]:
        if dist[x] == -1:
            dist[x] = dist[v] + c
            que.append(x)

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

Submission status: Accepted

Solution code:
N = int(input())
way = [[] for _ in range(N+1)]
depth = [float("inf")]*(N+1)
for _ in range(N - 1):
    a,b,c = map(int, input().split())
    way[a].append((b, c))
    way[b].append((a, c))

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

stack = []
stack.append((K, 0))

while stack:
    now, d = stack.pop()
    depth[now] = d
    for i, j in way[now]:
        if depth[i] < d+j:
            continue
        stack.append((i, d+j))

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

Submission status: Accepted

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

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

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

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

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

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

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

########
    

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

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

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


 
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

if __name__ == "__main__":
    m()

Submission status: Accepted

Solution code:
import queue

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

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

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

if __name__ == "__main__":
    m()

Submission status: Accepted

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

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

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

Q, K = map(int, input().split())
K -= 1
dist = [-1] * N
already = set()
que = queue.Queue()
dist[K] = 0
que.put(K)
while not que.empty():
    now = que.get()
    out = E[now]
    for n, c in out:
        if dist[n] != -1:
            continue
        dist[n] = dist[now] + c        
        que.put(n)

res = ""
for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    res += str(dist[x] + dist[y]) + "\n"

print(res)

Submission status: Accepted

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

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

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

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

if __name__ == "__main__":
    m()

Submission status: Accepted

Solution code:
## abc070d: Transit Tree Path
import sys
from collections import deque
input = sys.stdin.readline

n = int(input())

T = [{} for _ in range(n)]
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    v1,v2 = v1-1,v2-1
    T[v1][v2] = d
    T[v2][v1] = d

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

depth = [-1]*n
que = deque()
que.append(k-1)
while que:
    p = que.popleft()
    if depth[p]<0: depth[p] = 0
    for c in T[p].keys():
        if depth[c]>=0: continue
        depth[c] = depth[p] + T[p][c]
        que.append(c)

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