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:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dfs(N, nodes, src):
    """ DFS(木、スタック、重みあり) """

    stack = [(src, -1, 0)]
    dist = [INF] * N
    while stack:
        u, prev, c1 = stack.pop()
        dist[u] = c1
        for v, c2 in nodes[u]:
            if v != prev:
                stack.append((v, u, c1+c2))
    return dist

N = INT()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = MAP()
    a -= 1; b -= 1
    nodes[a].append((b, c))
    nodes[b].append((a, c))

Q, K = MAP()
K -= 1
res = dfs(N, nodes, K)
ans = []
for i in range(Q):
    x, y = MAP()
    x -= 1; y -= 1
    ans.append(str(res[x] + res[y]))
print('\n'.join(ans))

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dfs(N, nodes, src):
    """ DFS(木、スタック、重みあり) """

    stack = [(src, -1, 0)]
    dist = [INF] * N
    while stack:
        u, prev, c1 = stack.pop()
        dist[u] = c1
        for v, c2 in nodes[u]:
            if v != prev:
                stack.append((v, u, c1+c2))
    return dist

N = INT()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = MAP()
    a -= 1; b -= 1
    nodes[a].append((b, c))
    nodes[b].append((a, c))

Q, K = MAP()
K -= 1
res = dfs(N, nodes, K)
for i in range(Q):
    x, y = MAP()
    x -= 1; y -= 1
    ans = res[x] + res[y]
    print(ans)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dijkstra(N: int, nodes: list, src: int) -> list:
    """ ダイクストラ高速化版(頂点数, 隣接リスト(0-indexed), 始点) """
    from heapq import heappush, heappop

    # 頂点[ある始点からの最短距離]
    res = [INF] * N
    # スタート位置
    que = [src]
    res[src] = 0
    # キューが空になるまで
    while len(que) != 0:
        # 距離*N + 現在のノード
        cur = heappop(que)
        # 距離とノードに分ける
        dist = cur // N
        cur %= N
        # 出発ノードcurの到着ノードでループ
        for nxt, cost in nodes[cur]:
            # 今回の経路のが短い時
            if dist + cost < res[nxt]:
                res[nxt] = dist + cost
                # 距離*N+ノード番号 の形でキューに詰める
                heappush(que, (dist+cost)*N+nxt)
    # ノードsrcからの最短距離リストを返却
    return res

N = INT()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = MAP()
    a -= 1; b -= 1
    nodes[a].append((b, c))
    nodes[b].append((a, c))

Q, K = MAP()
K -= 1
res = dijkstra(N, nodes, K)
for i in range(Q):
    x, y = MAP()
    x -= 1; y -= 1
    ans = res[x] + res[y]
    print(ans)

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

graph = [[] for _ in range(N + 1)]
for A, B, C in ABC:
  graph[A].append((B, C))
  graph[B].append((A, C))
#print("graph:", graph)

INF = 10 ** 15
stack = [K]
depth = [INF] * (N + 1)
depth[K] = 0

while stack:
  a = stack.pop()
  for b, d in graph[a]:
    if depth[b] > depth[a] + d:
      depth[b] = depth[a] + d
      stack.append(b)
#print(depth[1:])

for X, Y in XY:
  print(depth[X] + depth[Y])

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	N = INT()
	G = [[] for _ in range(N)]
	for _ in range(N-1):
		a, b, c = MAP()
		a -= 1
		b -= 1
		G[a].append([b, c])
		G[b].append([a, c])
	
	Q, K = MAP()
	queue = deque()
	queue.append(K-1)
	dist = [-1] * N
	dist[K-1] = 0
	while queue:
		v = queue.popleft()
		for nv in G[v]:
			edge, distance = nv
			if dist[edge] != -1: continue
			dist[edge] = dist[v] + distance
			queue.append(edge)
	
	# print(dist)
	for _ in range(Q):
		a, b = MAP()
		print(dist[a-1]+dist[b-1])

if __name__ == '__main__':
	main()

Submission status: Accepted

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

cnt, K = map(int, input().split())
K -= 1
Q = deque([(K, 0)])
Dist = [0]*N
check = [0]*N
while Q:
    n, d = Q.popleft()
    check[n] = 1
    Dist[n] = d
    for v, e in D[n]:
        if check[v]:
            continue
        else:
            Q.append((v, d+e))

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

Submission status: Accepted

Solution code:
import sys

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

q, k = map(int, sys.stdin.readline().split())
xy = zip(*[map(int, sys.stdin.read().split())] * 2)

def dfs(v):
    dist = [None] * (n + 1)
    stack = [(v, 0)]
    while stack:
        x, d = stack.pop()
        dist[x] = d
        for y, dd in g[x]:
            if dist[y] is None:
                stack.append((y, d + dd))
    return dist

def main():
    dist_k = dfs(k)
    
    for x, y in xy:
        yield dist_k[x] + dist_k[y]

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int, input().split(' '))) for i in range(n-1)]
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
Q,K = map(int, input().split(' '))
root = K
d = 0
stack = [root]
order = []
for a,b,e in ab:
    graph[a].append(b)
    graph[b].append(a)
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        stack.append(y)
dist = [0 for i in range(n+1)]
for a,b,e in ab:
    if parent[a] == b:
        dist[a] = e
    else:
        dist[b] = e
visited = [0 for i in range(n+1)]
visited[root] = 1
ans = [0 for i in range(n+1)]
for i in order:
    if i == root:
        continue
    ans[i] += dist[i]
    if visited[parent[i]] == 1:
        ans[i] += ans[parent[i]]
        visited[i] = 1
for i in range(Q):
    s,t = map(int, input().split(' '))
    print(ans[s]+ans[t])

Submission status: Accepted

Solution code:
from collections import deque


def main():
    n = int(input())
    tree = AdjacentListGraph([Vertex() for _ in range(n)])
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        tree.add_edge(a - 1, b - 1, c)
        tree.add_edge(b - 1, a - 1, c)
    q, k = map(int, input().split())
    distances = distances_from(tree, k - 1)
    # print(distances)
    answers = []
    for _ in range(q):
        x, y = map(int, input().split())
        answers.append(distances[x - 1] + distances[y - 1])
    print("\n".join(map(str, answers)))


def distances_from(
    graph: "Graph", from_: int, break_if=lambda node: False
) -> "List[int]":
    distances = [None for _ in range(graph.size)]
    distances[from_] = 0
    queue = deque([from_])
    while queue:
        node = queue.popleft()
        if break_if(node):
            break
        curDist = distances[node]
        for edge in graph.edges_from(node):
            if distances[edge.to] is not None:
                continue
            delta = edge.weight if edge.weight else 0
            distances[edge.to] = curDist + delta
            queue.append(edge.to)
    return distances


class Vertex:
    def __init__(self, data=None):
        self.data = data
        self.edges = []

    def add_edge(self, to, weight=None):
        self.edges.append(Edge(to, weight))

    def remove_edge(self, to: int) -> bool:
        for i, edge in enumerate(self.edges):
            if edge.to == to:
                del self.edges[i]
                return True
        return False


class Edge:
    def __init__(self, to, weight=None):
        self.to = to
        self.weight = weight


class AdjacentListGraph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.size = len(vertices)

    def get_weight(self, from_: int, to: int):
        for edge in self.vertices[from_].edges:
            if edge.to == to:
                return edge.weight
        return None

    def edges_from(self, from_: int):
        return self.vertices[from_].edges

    def add_edge(self, from_: int, to: int, weight=None) -> bool:
        return self.vertices[from_].add_edge(to, weight)

    def remove_edge(self, from_: int, to: int) -> bool:
        return self.vertices[from_].remove_edge(to)

    def is_adjacent(self, from_: int, to: int) -> bool:
        return to in {edge.to for edge in self.edges_from(from_)}


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    n = int(input())
    tree = AdjacentListGraph([Vertex() for _ in range(n)])
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        tree.add_edge(a - 1, b - 1, c)
        tree.add_edge(b - 1, a - 1, c)
    q, k = map(int, input().split())
    distances = distances_from(tree, k - 1)
    # print(distances)
    answers = []
    for _ in range(q):
        x, y = map(int, input().split())
        answers.append(distances[x - 1] + distances[y - 1])
    print("\n".join(map(str, answers)))


def distances_from(
    graph: "Graph", from_: int, break_if=lambda node: False
) -> "List[int]":
    distances = [None for _ in range(graph.size)]
    distances[from_] = 0
    queue = deque([from_])
    while queue:
        node = queue.popleft()
        if break_if(node):
            break
        curDist = distances[node]
        for edge in graph.edges_from(node):
            if distances[edge.to] is not None:
                continue
            delta = edge.weight if edge.weight else 0
            distances[edge.to] = curDist + delta
            queue.append(edge.to)
    return distances


class Vertex:
    __slots__ = ("data", "edges")

    def __init__(self, data=None):
        self.data = data
        self.edges = set()

    def add_edge(self, to, weight=None):
        self.edges.add(Edge(to, weight))

    def remove_edge(self, to: int) -> bool:
        for i, edge in enumerate(self.edges):
            if edge.to == to:
                del self.edges[i]
                return True
        return False


class Edge:
    __slots__ = ("to", "weight")

    def __init__(self, to, weight=None):
        self.to = to
        self.weight = weight

    def __hash__(self) -> int:
        return hash(self.to)

class AdjacentListGraph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.size = len(vertices)

    def get_weight(self, from_: int, to: int):
        for edge in self.vertices[from_].edges:
            if edge.to == to:
                return edge.weight
        return None

    def edges_from(self, from_: int):
        return self.vertices[from_].edges

    def add_edge(self, from_: int, to: int, weight=None) -> bool:
        return self.vertices[from_].add_edge(to, weight)

    def remove_edge(self, from_: int, to: int) -> bool:
        return self.vertices[from_].remove_edge(to)

    def is_adjacent(self, from_: int, to: int) -> bool:
        return to in {edge.to for edge in self.edges_from(from_)}


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    n = int(input())
    tree = AdjacentListGraph([Vertex() for _ in range(n)])
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        tree.add_edge(a - 1, b - 1, c)
        tree.add_edge(b - 1, a - 1, c)
    q, k = map(int, input().split())
    distances = distances_from(tree, k - 1)
    # print(distances)
    answers = []
    for _ in range(q):
        x, y = map(int, input().split())
        answers.append(distances[x - 1] + distances[y - 1])
    print("\n".join(map(str, answers)))


def distances_from(
    graph: "Graph", from_: int, break_if=lambda node: False
) -> "List[int]":
    distances = [None for _ in range(graph.size)]
    distances[from_] = 0
    queue = deque([from_])
    while queue:
        node = queue.popleft()
        if break_if(node):
            break
        curDist = distances[node]
        for edge in graph.edges_from(node):
            if distances[edge.to] is not None:
                continue
            delta = edge.weight if edge.weight else 0
            distances[edge.to] = curDist + delta
            queue.append(edge.to)
    return distances


class Vertex:
    __slots__ = ("data", "edges")

    def __init__(self, data=None):
        self.data = data
        self.edges = []

    def add_edge(self, to, weight=None):
        self.edges.append(Edge(to, weight))

    def remove_edge(self, to: int) -> bool:
        for i, edge in enumerate(self.edges):
            if edge.to == to:
                del self.edges[i]
                return True
        return False


class Edge:
    __slots__ = ("to", "weight")

    def __init__(self, to, weight=None):
        self.to = to
        self.weight = weight


class AdjacentListGraph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.size = len(vertices)

    def get_weight(self, from_: int, to: int):
        for edge in self.vertices[from_].edges:
            if edge.to == to:
                return edge.weight
        return None

    def edges_from(self, from_: int):
        return self.vertices[from_].edges

    def add_edge(self, from_: int, to: int, weight=None) -> bool:
        return self.vertices[from_].add_edge(to, weight)

    def remove_edge(self, from_: int, to: int) -> bool:
        return self.vertices[from_].remove_edge(to)

    def is_adjacent(self, from_: int, to: int) -> bool:
        return to in {edge.to for edge in self.edges_from(from_)}


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
N=int(input())
Branch=[[] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  Branch[a-1].append([b-1,c])
  Branch[b-1].append([a-1,c])
Q,K=map(int,input().split())
Dist=[float("Inf") for i in range(N)]
flag = [0 for i in range(N)]

que=collections.deque()
que.append(K-1)
Dist[K-1]=0
while len(que):
  u=que.pop()
  for i,j in Branch[u]:
    if Dist[i]==float("Inf"):
      Dist[i]=Dist[u]+j
      que.append(i)

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(1000000)
N = int(input())
graph = [[] for _ in range(N+1)]
for i in range(1, N):
    tmpa, tmpb, tmpc = map(int, input().split())
    graph[tmpa].append((tmpb, tmpc))
    graph[tmpb].append((tmpa, tmpc))

Q, K = map(int, input().split())
question = [[] for _ in range(Q+1)]
for i in range(1, Q+1):
    question[i] = list(map(int, input().split()))

#print(graph)
#print(question)
seen = [False] * (N+1)
dist = [0] * (N+1)
#Kからdfs
def dfs(here, seen, kyori):
    seen[here] = True
    dist[here] = kyori
    #print(f"here:{here} kyori:{kyori}")
    for node in graph[here]:
        nextkyori = kyori
        if not seen[node[0]]:
            nextkyori += node[1]
            dfs(node[0], seen, nextkyori)

dfs(K, seen, 0)
for quest in question[1:]:
    print(dist[quest[0]] + dist[quest[1]])

Submission status: Accepted

Solution code:
N = int(input())
tl = [[] for _ in range(N+1)]
d = {}
for _ in range(N-1):
    a, b, c = map(int, input().split())
    tl[a].append(b)
    tl[b].append(a)
    d[(a, b)] = c
    d[(b, a)] = c
Q, K = map(int, input().split())
seen = [False]*(N+1)
stack = [K]
seen[K] = True
while len(stack):
    n = stack.pop()
    for v in tl[n]:
        if not seen[v]:
            stack.append(v)
            seen[v] = True
            if n != K:
                d[(K, v)] = d[(K, n)]+d[(n, v)]
for _ in range(Q):
    x, y = map(int, input().split())
    print(d[(K, x)]+d[(K, y)])

Submission status: Accepted

Solution code:
N = int(input())
neig = [[] for _ in range(N)]

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

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

S, D = [(K - 1, K - 1)], [0] * N
while len(S) > 0:
    p, pp = S.pop()
    for c, d in neig[p]:
        if not c == pp:
            D[c] = D[p] + d
            S.append((c, p))

for _ 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**9)

n = int(input())

from collections import defaultdict
d = defaultdict(list)

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

global dist
dist = [-1 for _ in range(n)]
def dfs(l, pos):
    dist[pos] = l
    for to, c in d[pos]:
        if dist[to] == -1:
            dfs(l+c,to)

dfs(0, k-1)

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

Submission status: Accepted

Solution code:
from collections import deque

N=int(input())
adj=[[] for i in range(N+1)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    adj[a].append((b,c))
    adj[b].append((a,c))
# print(adj)
Q,K=map(int,input().split())
d=[-1 for i in range(N+1)]
q=deque()
q.append(K);d[K]=0
while q:
    u=q.popleft()
    for v,c in adj[u]:
        if d[v]==-1:
            d[v]=d[u]+c
            q.append(v)
# print(d)
for i in range(Q):
    x,y=map(int,input().split())
    print(d[x]+d[y])

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
g = [[] for i in range(n)]
cc = dict()
for i in range(n-1):
    a,b,c = inpl()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    cc[(a,b)] = c
    cc[(b,a)] = c
q,k = inpl()
k -= 1
cost = [INF] * n
cost[k] = 0
def dfs(node,c):
    for next in g[node]:
        if cost[next] == INF:
            cost[next] = c + cc[(node,next)]
            dfs(next,cost[next])

dfs(k,0)
res = [0] * q
for i in range(q):
    x,y = inpl()
    x -= 1
    y -= 1
    res[i] = cost[x] + cost[y]
for z in res:
    print(z)

Submission status: Accepted

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

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

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

queue = [K-1]
dist = [None]*N
dist[K-1] = 0
while queue:
  queue_new = []
  for q in queue:
    for e in E[q]:
      if dist[e[0]] is not None: continue
      dist[e[0]] = dist[q] + e[1]
      queue_new.append(e[0])
  queue = queue_new

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n=int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=map(int,input().split())
        a-=1
        b-=1
        graph[a].append((b,w))
        graph[b].append((a,w))
    graph = tuple(graph)
    q,k = map(int,input().split())
    que = deque([k-1])
    dis = [-1 for _ in range(n)]
    dis[k-1]=0
    while que:
        i = que.pop()
        for j in range(len(graph[i])):
            go = graph[i][j][0]
            d = graph[i][j][1]
            if dis[go]==-1:
                dis[go] = dis[i] + d
                que.append(go)
    for _ in range(q):
        x,y = map(int,input().split())
        print( dis[x-1] + dis[y-1] ) 

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    to=defaultdict(list)
    n=int(input())
    for _ in range(n-1):
        a,b,c=MI()
        a,b=a-1,b-1
        to[a].append([b,c])
        to[b].append([a, c])
    q,k=MI()
    k-=1
    dist=[-1]*n
    hp=[]
    heappush(hp,[0,k])
    while hp:
        d,u=heappop(hp)
        if dist[u]!=-1:continue
        dist[u]=d
        for v,c in to[u]:
            if dist[v]!=-1:continue
            heappush(hp,[d+c,v])
    for _ in range(q):
        u,v=MI1()
        print(dist[u]+dist[v])

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    X[a-1].append((b-1, c))
    X[b-1].append((a-1, c))

P = [-1] * N
DE = [0] * N
F = [0] * N
Q = [0]
while Q:
    i = Q.pop()
    for a, d in X[i][::-1]:
        if a != P[i]:
            P[a] = i
            DE[a] = DE[i] + 1
            F[a] = F[i] + d
            X[a].remove((i, d))
            Q.append(a)
KK = 17
D = [[P[i] for i in range(N)]] + [[-1]*N for _ in range(KK - 1)]
for k in range(1, KK):
    for i in range(N):
        a = D[k-1][i]
        if a > 0:
            D[k][i] = D[k-1][a]

def lca(u, v):
    if DE[u] < DE[v]:
        u, v = v, u
    while DE[u] > DE[v]:
        d = DE[u] - DE[v]
        dd = d.bit_length() - 1
        u = D[dd][u]
    if u == v:
        return u
    for i in range(KK)[::-1]:
        if D[i][u] != D[i][v]:
            u = D[i][u]
            v = D[i][v]
    return D[0][u]

def dist(u, v):
    w = lca(u, v)
    return F[u] + F[v] - F[w] * 2

T, K = map(int, input().split())
K -= 1
for _ in range(T):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    print(dist(a, K) + dist(b, K))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

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

    for i in range(N-1):
        if matrix.get(a[i]) == None:
            matrix[a[i]] = [(b[i],c[i])]
        else:
            matrix[a[i]].append((b[i],c[i]))

        if matrix.get(b[i]) == None:
            matrix[b[i]] = [(a[i],c[i])]
        else:
            matrix[b[i]].append((a[i],c[i]))

    # i = NodeKからnodeiまでの距離
    distance_via_K = [-1]*(N+1)

    queue = deque()
    ## K を頂点として見る
    queue.append((K,0))

    while queue:
        q,cur_distance = queue.pop()
        distance_via_K[q] = cur_distance

        for node,distance in matrix[q]:
            if distance_via_K[node] == -1:
                queue.append((node,cur_distance+distance))

    for j in range(Q):
        print(distance_via_K[x[j]]+distance_via_K[y[j]])

    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:
from collections import deque
N = int(input())
graph = [[] for _ in range(N)]
ditstant = [float('inf')]*N
visited = [False]*N
tmp = {}
for _ in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    tmp[a, b] = c
    tmp[b, a] = c
Q, K = map(int, input().split())
K -= 1
ditstant[K] = 0  # Kの地点は0にする
visited[K] = True
q = deque([K])
while len(q):
    v = q.popleft()
    for e in graph[v]:
        if visited[e]:
            continue
        visited[e] = True
        ditstant[e] = min(ditstant[e], ditstant[v]+tmp[v, e])
        q.append(e)
for _ in range(Q):
    x, y = map(lambda x: int(x)-1, input().split())
    print(ditstant[x] + ditstant[y])

Submission status: Accepted

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

n = int(input())
l = [[] for _ in range(n)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  l[a-1].append((b-1, c))
  l[b-1].append((a-1, c))
q, k = map(int, input().split())
dist = [-1]*n
dist[k-1] = 0
def dfs(v):
  for nv, c in l[v]:
    if dist[nv] == -1:
      dist[nv] = dist[v]+c
      dfs(nv)
dfs(k-1)
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(10**7)

n = int(input())
l = [[] for _ in range(n)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  l[a-1].append([b-1, c])
  l[b-1].append([a-1, c])
q, k = map(int, input().split())
dist = [-1]*n
dist[k-1] = 0
def dfs(v):
  for nv, c in l[v]:
    if dist[nv] == -1:
      dist[nv] = dist[v]+c
      dfs(nv)
dfs(k-1)
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(10000000)

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

graph = [[]*N for _ in range(N)]

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

Q, K = map(int, sys.stdin.buffer.readline().split())
dist_K = [-1]*N

def cal_dist_K(u = K-1, current_dist = 0):
    dist_K[u] = current_dist
    for v,c in graph[u]:
        if dist_K[v] == -1:
            cal_dist_K(v, current_dist + c)

cal_dist_K()

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

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