Problem:


Score : 400 points

Problem Statement

You are given a tree with N vertices.

Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N-1 edges, where N is the number of its vertices.

The i-th edge (1≤i≤N-1) connects Vertices a_i and b_i, and has a length of c_i.

You are also given Q queries and an integer K. In the j-th query (1≤j≤Q):

find the length of the shortest path from Vertex x_j and Vertex y_j via Vertex K.

Constraints

3≤N≤10^5 

1≤a_i,b_i≤N (1≤i≤N-1) 

1≤c_i≤10^9 (1≤i≤N-1) 

The given graph is a tree.

1≤Q≤10^5 

1≤K≤N 

1≤x_j,y_j≤N (1≤j≤Q) 

x_j≠y_j (1≤j≤Q) 

x_j≠K,y_j≠K (1≤j≤Q) 

Input

Input is given from Standard Input in the following format:  

N  
a_1 b_1 c_1  
:  
a_{N-1} b_{N-1} c_{N-1}
Q K
x_1 y_1
:  
x_{Q} y_{Q}

Output

Print the responses to the queries in Q lines.

In the j-th line j(1≤j≤Q), print the response to the j-th query.

Sample Input 1

5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5

Sample Output 1

3
2
4

The shortest paths for the three queries are as follows:

Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3 

Query 2: Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2 

Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4 

Sample Input 2

7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7

Sample Output 2

5
14
22

The path for each query must pass Vertex K=2.

Sample Input 3

10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10

Sample Output 3

17000000000



Sample input:
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5


Sample output:
3
2
4

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

# 入力
N = int(input())
a, b, c = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if N else
    ((), ())
)
Q, K = map(int, input().split())
x, y = (
    zip(*(map(int, input().split()) for _ in range(Q))) if Q else
    ((), ())
)

# K から各頂点への最短距離を求める。
INF = 10**18

G = [{} for _ in range(N + 1)]
for u, v, w in zip(a, b, c):
    G[u][v] = w
    G[v][u] = w


def dijkstra(G, s):
    dp = [INF for _ in range(len(G))]
    q = []
    heappush(q, (0, s))
    while q:
        c, i = heappop(q)
        if dp[i] == INF:
            dp[i] = c
            for j, w in G[i].items():
                heappush(q, (c + w, j))
    return dp


dp = dijkstra(G, K)

# j 番目のクエリの解は dp[x_j] + dp[y_j] である
ans = '\n'.join(
    str(dp[i] + dp[j])
    for i, j in zip(x, y)
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1145141919)
N=int(input())
d=[-1 for _ in range(N+1)]
e=[[] for _ in range(N+1)]
for _ in range(N-1):
	a,b,c=map(int,input().split())
	e[a].append((b, c))
	e[b].append((a, c))
Q,K=map(int,input().split())
def dfs(now, dis):
	d[now] = dis
	for nxt,cos in e[now]:
		if d[nxt] == -1:
			dfs(nxt, dis+cos)
dfs(K, 0)
for _ in range(Q):
	x,y=map(int,input().split())
	print(d[x]+d[y])

Submission status: Accepted

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


def main():
    N = int(input())

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

    Q, K = map(int, input().split())
    xy = []
    for _ in range(Q):
        x, y = map(int, input().split())
        xy.append((x, y))

    ans = ref_pypy(N, abc, Q, K, xy)
    print(*ans, sep="\n")


def ref_pypy(N, abc, Q, K, xy):
    """https://atcoder.jp/contests/abc070/submissions/5331379"""
    L = [-1 for i in range(N+1)]
    L[K] = 0
    n = [[] for i in range(N+1)]
    for a, b, c in abc:
        n[a].append([b, c])
        n[b].append([a, c])

    def dfs(x):
        for i in n[x]:
            if L[i[0]] == -1:
                L[i[0]] = L[x]+i[1]
                dfs(i[0])

    dfs(K)

    ans = []
    for x, y in xy:
        ans.append(L[x] + L[y])

    return ans


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
N=int(input())
table=[[] for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    table[a].append((b,c))
    table[b].append((a,c))
Q,K=map(int,input().split())
query=[[int(i)-1 for i in input().split()] for i in range(Q)]
K=K-1
H=[]
visit=[10**18]*(N)
visit[K]=0
heappush(H,(0,K))
while H:
    co,pt=heappop(H)
    if co>visit[pt]:
        continue
    for x,c in table[pt]:
        if visit[x]>visit[pt]+c:
            visit[x]=visit[pt]+c
            heappush(H,(visit[x],x))
for a,b in query:
    print(visit[a]+visit[b])

Submission status: Accepted

Solution code:
import heapq

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

connect = [[] for _ in range(N)]
INFTY = 10**15
for a,b,c in abc:
    connect[a-1].append([b-1,c])
    connect[b-1].append([a-1,c])

cost = [[INFTY,False] for _  in range(N)]
cost[K-1][0] = 0
q = [(0,K-1)]
while q:
    _,i = heapq.heappop(q)
    if cost[i][1]:
        continue
    cost[i][1] = True
    ci0 = cost[i][0]
    for j,c in connect[i]:
        if cost[j][1]:
            continue
        tmp_cost = ci0+c
        if tmp_cost < cost[j][0]:
            cost[j][0] = tmp_cost
            heapq.heappush(q,(tmp_cost,j))

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
n = int(input())
li = [[] for i in range(n)]

for i in range(n-1):
  a,b,dist = map(int,input().split())
  li[a-1].append((b-1,dist))
  li[b-1].append((a-1,dist))

q,k = map(int,input().split())
tdp = [-1]*n
tdp[k-1] = 0

def dfs(x):
  for node in li[x]:
    if tdp[node[0]] == -1:
      tdp[node[0]] = tdp[x] + node[1]
      dfs(node[0])

dfs(k-1)
for i in range(q):
  a,b = map(int,input().split())
  print(tdp[a-1]+tdp[b-1])

Submission status: Accepted

Solution code:
from functools import reduce
from collections import deque
import math

def bfs(i,E,N):
    q = deque()
    q.append(i)
    d = [-1]*N
    d[i] = 0
    while q:
        next_node = q.popleft()
        for e in E[next_node]:
            if d[e[0]] == -1:
                d[e[0]] = d[next_node] + e[1]                
                q.append(e[0])
    return d
def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input())
    a = []
    b = []
    c = []
    for i in range(N-1):
        s1,s2,s3 = list(int(_) for _ in input().split())
        a.append(s1-1)
        b.append(s2-1)
        c.append(s3)
    Q,K = list(int(_) for _ in input().split())
    x = []
    y = []
    for i in range(Q):
        s1,s2 = list(int(_) for _ in input().split())
        x.append(s1-1)
        y.append(s2-1)
    
    e = [[] for i in range(N)]
    for i in range(N-1):
        e[a[i]].append((b[i],c[i]))
        e[b[i]].append((a[i],c[i]))

    d = bfs(K-1,e,N)

    for i in range(Q):        
        print(d[x[i]]+d[y[i]])
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
G = [[] for i in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append((b, c))
    G[b].append((a, c))
d = [0] * N


def dfs(u, p, k):
    d[u] = k
    for w, c in G[u]:
        if w == p:
            continue
        dfs(w, u, k + c)


Q, K = map(int, input().split())
dfs(K - 1, -1, 0)
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:
#!/usr/bin/env python3
import sys

inf = float('inf')

def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):
    adj = [[] for i in range(N)]
    for i in range(N-1):
        adj[a[i]].append((b[i], c[i]))
        adj[b[i]].append((a[i], c[i]))

    D = [inf for i in range(N)]
    prev = [None for i in range(N)]
    D[K] = 0
    Queue = [K]
    while len(Queue) > 0:
        u = Queue.pop()
        for v, w in adj[u]:
            if v == prev[u]:
                continue
            prev[v] = u
            D[v] = D[u] + w
            Queue.append(v)
    
    for i in range(Q):
        print(D[x[i]] + D[y[i]])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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))-1
        b[i] = int(next(tokens))-1
        c[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    K = int(next(tokens))-1  # type: int
    x = [int()] * (Q)  # type: "List[int]" 
    y = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        x[i] = int(next(tokens))-1
        y[i] = int(next(tokens))-1
    solve(N, a, b, c, Q, K, x, y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
edge = [{} for _ in range(N+1)]
dist = [-1]*(N+1)
for _ in range(N-1):
    a,b,c = map(int,input().split())
    edge[a][b] = c
    edge[b][a] = c
Q,K = map(int,input().split())
dist[K] = 0
dfs_stack = [K]
while dfs_stack:
    s = dfs_stack.pop()
    for t,t_dist in edge[s].items():
        if dist[t] == -1:
            dist[t] = dist[s] + t_dist
            dfs_stack.append(t)
for _ in range(Q):
    x,y = map(int,input().split())
    print(dist[x]+dist[y])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
inf = float('inf')

# (始点,隣接リスト)
def dijkstra(start,ad):
    global dist
    dist = [inf]*len(ad)
    dist[start] = 0
    pq = [(start,0)]
    while pq:
        v = heappop(pq)[0]
        for nv,nw in ad[v]:
            if dist[nv] > dist[v] + nw:
                dist[nv] = dist[v] + nw
                heappush(pq,(nv,dist[nv]))

N = int(input())
ad = [[] for _ in range(N)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    a -= 1; b -= 1
    ad[a].append((b,c))
    ad[b].append((a,c))
Q,K = map(int,input().split())
K -= 1
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]

dijkstra(K,ad)

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
inf = float('inf')

# import: from heapq import heappush,heappop
# distの初期化: dist = [inf]*n; dist[start] = 0
def dijkstra(ad,dist,n,start):
    pq = [(0,start)]
    while pq:
        w,v = heappop(pq)
        for nw,nv in ad[v]:
            if dist[nv] > dist[v] + nw:
                dist[nv] = dist[v] + nw
                heappush(pq,(dist[nv],nv))

N = int(input())

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

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

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

dist = [inf]*N
dist[K] = 0

dijkstra(ad,dist,N,K)

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

Submission status: Accepted

Solution code:
n = int(input())
edge = []
for _ in range(n-1):
    a,b,c = map(int,input().split())
    edge.append([a-1,b-1,c])
q, k = map(int,input().split())
querry = []
for _ in range(q):
    x,y = map(int,input().split())
    querry.append([x-1,y-1])
    

class Graph():
    def __init__(self,n,edge):
        self.n = n
        self.edge = edge
        self.ed_list = [[] for _ in range(n)]
        for a,b,c in edge:
            self.ed_list[a].append([b,c])
            self.ed_list[b].append([a,c])
    
    def dijkstra(self,start):
        INF = float('inf')
        cost = [INF]*self.n
        cost[start] = 0
        from heapq import heappop,heappush
        stack = [[0, start]]
        while stack:
            c, x = heappop(stack)
            for to,j in self.ed_list[x]:
                if cost[to] > j + c:
                    cost[to] = j + c
                    heappush(stack,[j + c, to])
        return cost

gp = Graph(n,edge)
cost = gp.dijkstra(k-1)
for i,j in querry:
    print(cost[i] + cost[j])

Submission status: Accepted

Solution code:
n = int(input())
edge = [list(map(int,input().split())) for _ in range(n-1)]
q, k = map(int,input().split())
querry = [list(map(int,input().split())) for _ in range(q)]
INF = float('inf')
from heapq import heappush,heappop
def dijkstra(n,edge,start):
    ed_list = [[] for _ in range(n)]
    for a,b,c in edge:
        ed_list[a-1].append([b-1,c])
        ed_list[b-1].append([a-1,c])
    cost = [INF]*n
    cost[start] = 0
    stack =[[0,start]]
    while stack:
        c, x = heappop(stack)
        for i,j in ed_list[x]:
            if cost[i] > c + j:
                cost[i] = c + j
                heappush(stack,[c + j, i])
    return cost
arr_cost = dijkstra(n,edge,k-1)
for i,j in querry:
    print(arr_cost[i-1] + arr_cost[j-1])

Submission status: Accepted

Solution code:
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

n=int(input())
d=[[]for _ in[0]*-~n]

for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})

def DIJKSTRA(point,d):
    cost      = [float("inf") for _ in range(len(d))]
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

q,k=map(int,input().split())
y=DIJKSTRA(k,d)

for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Submission status: Accepted

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

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

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

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


def dfs(n):
    for to, cost in T[n]:
        if dist[to] < 0:
            dist[to] = dist[n] + cost
            dfs(to)


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

Submission status: Accepted

Solution code:
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

d=defaultdict(list)
n=int(input())

for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})

def DIJKSTRA(point,d):
    cost      = {node:float("inf") for node in d.keys()}
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

q,k=map(int,input().split())
y=DIJKSTRA(k,d)

for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Submission status: Accepted

Solution code:
import sys
from collections import deque
inf=100000000000000000000
fastinput=sys.stdin.readline
N=int(fastinput())
path=[[] for hoge in range(N)]
for fuga in range(N-1):
    a,b,c=[int(hoge) for hoge in fastinput().split()]
    path[a-1].append([b-1,c])
    path[b-1].append([a-1,c])
Q,K=[int(hoge) for hoge in fastinput().split()]
stack=deque()
stack.append(K-1)
Kcost=[0]*N#あとあと初期化
went=[False]*N
went[K-1]=True
while stack:
    cur=stack.pop()
    curcost=Kcost[cur]
    for next,c in path[cur]:
        if c and not went[next]:
            went[next]=True
            Kcost[next]=curcost+c
            stack.append(next)
for q in range(Q):
    x,y=[int(hoge) for hoge in fastinput().split()]
    print(Kcost[x-1]+Kcost[y-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque
inf=100000000000000000000
fastinput=sys.stdin.readline
N=int(fastinput())
path=[deque() for hoge in range(N)]
for fuga in range(N-1):
    a,b,c=[int(hoge) for hoge in fastinput().split()]
    path[a-1].append([b-1,c])
    path[b-1].append([a-1,c])
Q,K=[int(hoge) for hoge in fastinput().split()]
stack=deque()
stack.append(K-1)
Kcost=[0]*N#あとあと初期化
went=[False]*N
went[K-1]=True
while stack:
    cur=stack.pop()
    curcost=Kcost[cur]
    for next,c in path[cur]:
        if c and not went[next]:
            went[next]=True
            Kcost[next]=curcost+c
            stack.append(next)
for q in range(Q):
    x,y=[int(hoge) for hoge in fastinput().split()]
    print(Kcost[x-1]+Kcost[y-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque
inf=100000000000000000000
fastinput=sys.stdin.readline
N=int(fastinput())
path=[[] for hoge in range(N)]
for fuga in range(N-1):
    a,b,c=[int(hoge) for hoge in fastinput().split()]
    path[a-1].append([b-1,c])
    path[b-1].append([a-1,c])
Q,K=[int(hoge) for hoge in fastinput().split()]
stack=deque()
stack.append(K-1)
Kcost=[0]*N#あとあと初期化
went=[False]*N
went[K-1]=True
while stack:
    cur=stack.pop()
    curcost=Kcost[cur]
    for next,c in path[cur]:
        if c and not went[next]:
            went[next]=True
            Kcost[next]=curcost+c
            stack.append(next)
for q in range(Q):
    x,y=[int(hoge) for hoge in fastinput().split()]
    print(Kcost[x-1]+Kcost[y-1])

Submission status: Accepted

Solution code:
N = int( input() )
# V[i][j][0]: vertex i からj番目に伸びる vertex の値
# V[i][j][1]: vertex i からj番目に伸びる vertex までの距離
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) )
Q, K = map( int, input().split() )

dist = [0]*N
q = [K-1]
while q:
    tmp = q.pop()
    for v in V[tmp]:
        if dist[v[0]] == 0:
            dist[v[0]] = dist[tmp] + v[1]
            q.append( v[0] )

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**6)

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

distance = [0] * n
e = [[] for _ in range(n)]
w = [[] for _ in range(n)]
for a, b, c in abc:
    e[a-1].append(b-1)
    e[b-1].append(a-1)
    w[a-1].append(c)
    w[b-1].append(c)

def dfs(v, par, dist):
    distance[v] = dist
    if len(e[v]) == 0:
        return True
    for i in range(len(e[v])):
        if e[v][i] == par:
            continue
        dfs(e[v][i], v, dist + w[v][i])

dfs(k-1, -1, 0)
for x, y in xy:
    print(distance[x-1] + distance[y-1])

Submission status: Accepted

Solution code:
import heapq

N = int(input())
d = [0] * N
INF = float('inf')

class Info:
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost
        
G = [[] for i in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1].append(Info(b - 1, c))
    G[b - 1].append(Info(a - 1, c))
    
def dijkstra(s):
    for i in range(N):
        d[i] = INF
    d[s] = 0
    h = []
    heapq.heappush(h, [0, s])
    
    while h != []:
        p = heapq.heappop(h)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e.to] > d[v] + e.cost:
                d[e.to] = d[v] + e.cost
                heapq.heappush(h, [d[e.to], e.to])

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

dijkstra(K - 1)

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

n = ni()

graph = [[] for _ in range(n)]

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

q,k = li()
k -= 1

query = []
for _ in range(q):
    x, y = li_()
    query.append((x, y))
    
dist = dijkstra(graph, n, k)
    
for qx, qy in query:
    print(dist[qx] + dist[qy])

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n=int(input())
    l=[0]*n
    d={}
    for i in range(n-1):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        if a in d:
            d[a].add((b,c))
        else:
            d[a]={(b,c)}
        if b in d:
            d[b].add((a,c))
        else:
            d[b]={(a,c)}
    q,k=map(int,input().split())
    k-=1
    p=deque([k])
    while len(p):
        w=p.popleft()
        for i in d[w]:
            if (l[i[0]]==0 and i[0]!=k) or (l[i[0]]!=0 and l[i[0]]>l[w]+i[1]):
                l[i[0]]=l[w]+i[1]
                p.append(i[0])

    for i in range(q):
        x,y=map(int,input().split())
        print(l[x-1]+l[y-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
l=[0]*n
d={}
for i in range(n-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    if a in d:
        d[a].add((b,c))
    else:
        d[a]={(b,c)}
    if b in d:
        d[b].add((a,c))
    else:
        d[b]={(a,c)}
q,k=map(int,input().split())
k-=1
p=deque([k])
while len(p):
    w=p.popleft()
    for i in d[w]:
        if (l[i[0]]==0 and i[0]!=k) or (l[i[0]]!=0 and l[i[0]]>l[w]+i[1]):
            l[i[0]]=l[w]+i[1]
            p.append(i[0])

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    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))

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

    k_dist = [0 for _ in range(N)]
    start = deque()
    start.append(K)
    while len(start) > 0:
        s = start.popleft()
        for dest, cost in d[s]:
            if k_dist[dest] > 0:
                continue

            k_dist[dest] = k_dist[s] + cost
            start.append(dest)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

def dfs(start, dest, pre, d):
    if d[start][dest] > 0:
        return d[start][dest]

    for i in range(len(d)):
        if d[start][i] > 0 and i != pre:
            c = dfs(i, dest, start, d)
            if c > 0:
                return d[start][i] + dfs(i, dest, start, d)

    return 0

def main():
    input = sys.stdin.readline
    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))

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

    k_dist = [0 for _ in range(N)]
    start = deque()
    start.append(K)
    while len(start) > 0:
        s = start.popleft()
        for dest, cost in d[s]:
            if k_dist[dest] > 0:
                continue

            k_dist[dest] = k_dist[s] + cost
            start.append(dest)

    for _ in range(Q):
        x, y = map(int, input().split())
        x, y = x - 1, y - 1

        print(int(k_dist[x] + k_dist[y]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
n=int(input())
s=[[]for i in range(n+1)]
g=[0]*(n+1)
h=[True]*(n+1)
for i in range(n-1):
    a,b,c=map(int,input().split())
    s[a].append([b,c])
    s[b].append([a,c])
def dfs(x):
    h[x]=False
    for i in s[x]:
        if h[i[0]]:
            g[i[0]]=g[x]+i[1]
            dfs(i[0])
q,k=map(int,input().split())
dfs(k)
for i in range(q):
    x,y=map(int,input().split())
    print(g[x]+g[y])

Submission status: Accepted

Solution code:
from queue import Queue


def distances(tree: list, treeSize: int, root: int)->list:
    dists = [0] * treeSize

    q = Queue()
    q.put((root, -1, 0))

    while not q.empty():
        v, prev, d2v = q.get()

        dists[v] = d2v
        for u, dv2u in tree[v]:
            if prev == u:
                continue
            q.put((u, v, d2v + dv2u))

    return dists


def transit_tree_path(
        N: int, edges: list, Q: int, K: int, queries: list)->list:
    tree = [[] for _ in range(N)]
    for u, v, c in edges:
        tree[u-1].append((v-1, c))
        tree[v-1].append((u-1, c))

    d = distances(tree, N, K-1)

    return [d[x-1]+d[y-1] for x, y in queries]


if __name__ == "__main__":
    N = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(N-1)]
    Q = 0
    Q, K = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    ans = transit_tree_path(N, edges, Q, K, queries)
    for a in ans:
        print(a)

Submission status: Accepted

Solution code:
N=int(input())
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for i in range(N-1):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c),}
    branch[b]|={(a,c),}
Q,K=map(int,input().split())
dist=[float('inf')]*(N+1)
dist[K]=0
check=deque([K])
while len(check)>0:
    now=check.popleft()
    for nex,c in branch[now]:
        if dist[nex]>dist[now]+c:
            dist[nex]=dist[now]+c
            check.append(nex)
for q in range(Q):
    x,y=map(int,input().split())
    print(dist[x]+dist[y])

Submission status: Accepted

Solution code:
from collections import deque
class edge:
    def __init__(self,to,cost):
        self.to=to
        self.cost=cost

N=int(input())
G=[list() for i in range(N)]
P=[False for i in range(N)]
A=[-100 for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    G[a-1].append(edge(b-1,c))
    G[b-1].append(edge(a-1,c)) #無向グラフならこれも



def solve(G,K,P):
    q=deque()
    q.append(K)
    while q:
        s=q.pop()
        for i in G[s]:
            if(P[i.to]):
                continue
            P[i.to]=True
            A[i.to]=A[s]+i.cost
            q.append(i.to)

Q,K=map(int,input().split())
A[K-1]=0
P[K-1]=True
solve(G,K-1,P)


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

Submission status: Accepted

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

INF = 10**9 * N
distance = [INF for _ in range(N+1)]
distance[K] = 0
settled = set()
h = [(0,K)]
while len(h) > 0:
    d,v = heapq.heappop(h)
    if v in settled:
        continue
    settled.add(v)
    distance[v] = d
    for (w,a) in edges[v]:
        if distance[v] + a < distance[w]:
            distance[w] = distance[v] + a
            heapq.heappush(h,(distance[w],w))

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
inf = float("inf")
road = [dict() for _ in range(n+1)]
for _ in range(n-1):
  a,b,c = map(int, input().split())
  road[a][b] = c
  road[b][a] = c
q,k = map(int, input().split())
dfs = [inf]*(n+1)
dfs[k] = 0
def dodfs(x):
  for i in road[x]:
    if dfs[i] == inf:
      dfs[i] = dfs[x] + road[x][i]
      dodfs(i)
  return   
dodfs(k)
for _ in range(q):
  x,y = map(int, input().split())
  print(dfs[x] + dfs[y])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

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

Q,K = map(int,input().split())
K -= 1
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]
dis = [0]*N

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

dfs()
for x,y in query:
    ans = dis[x] + dis[y]
    print(ans)

Submission status: Accepted

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

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

Q,K = map(int,input().split())
K -= 1
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]
dis = [0]*N

def bfs(sv=K):
    dq = deque()
    dq.append((sv,0,-1))
    while dq:
        v,d,pv = dq.pop()
        for nv,nd in ad[v]:
            if nv == pv:
                continue
            dis[nv] = d+nd
            dq.append((nv,d+nd,v))

bfs()
for x,y in query:
    ans = dis[x] + dis[y]
    print(ans)