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 collections import deque

n = int(input())
d = {i: [] for i in range(1, n+1)}
for _ in range(n-1):
    a, b, c = map(int, input().split())
    d[a].append((b, c))
    d[b].append((a, c))
q, k = map(int, input().split())
D = [-1] * (n + 1)
D[k] = 0
que = deque([k])
while que:
    t = que.popleft()
    dist = D[t]
    for l, c in d[t]:
        if D[l] < 0:
            D[l] = dist + c
            que.append(l)
for _ in range(q):
    x, y = map(int, input().split())
    print(D[x] + D[y])

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(1000000)
    n, *rem = map(int, open(0).read().split())
    t = 3 * (n - 1)
    abc = rem[:t]
    q, k = rem[t], rem[t + 1]
    xy = rem[t + 2:]

    dist = defaultdict(dict)
    for a, b, c in zip(*[iter(abc)] * 3):
        dist[a].update({b: c})
        dist[b].update({a: c})

    vis = [False] * (n + 1)
    cost = [0] * (n + 1)
    vis[k] = True

    def dfs(a, b):
        if vis[b]:
            return
        vis[b] = True
        cost[b] = cost[a] + dist[a][b]
        a = b
        for b in dist[a].keys():
            dfs(a, b)

    for b in dist[k].keys():
        dfs(k, b)

    tmp = []
    for x, y in zip(*[iter(xy)] * 2):
        tmp.append(cost[x] + cost[y])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(1000000)
    n, *rem = map(int, open(0).read().split())
    t = 3 * (n - 1)
    abc = rem[:t]
    q, k = rem[t], rem[t + 1]
    xy = rem[t + 2:]

    m = [[] for _ in range(n + 1)]
    dist = defaultdict(dict)
    for a, b, c in zip(*[iter(abc)] * 3):
        m[a].append(b)
        m[b].append(a)

        dist[a].update({b: c})
        dist[b].update({a: c})

    vis = [False] * (n + 1)
    cost = [0] * (n + 1)
    vis[k] = True

    def dfs(frm, to):
        if vis[to]:
            return
        vis[to] = True
        cost[to] = cost[frm] + dist[frm][to]
        frm = to
        for to in m[frm]:
            dfs(frm, to)

    frm = k
    for to in m[frm]:
        dfs(frm, to)

    tmp = []
    for x, y in zip(*[iter(xy)] * 2):
        tmp.append(cost[x] + cost[y])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

from heapq import heappush, heappop
INF = 10 ** 18
def dijkstra(s, n): # (始点, ノード数)
    dist = [INF] * n
    hq = [(0, s)] # (distance, node)
    dist[s] = 0
    seen = [False] * n # ノードが確定済みかどうか
    while hq:
        v = heappop(hq)[1] # ノードを pop する
        seen[v] = True
        for to, cost in tree[v]: # ノード v に隣接しているノードに対して
            if seen[to] == False and dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(hq, (dist[to], to))
    return dist

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

from heapq import heappop, heappush
def dijkstra(E,s,n,inf=float('inf')):
    d = [inf]*n
    d[s] = 0
    q = []
    heappush(q,(0,s))
    while q:
        du,u = heappop(q)
        if d[u] < du:
            continue
        for v,dist in E[u]:
            dnew = du + dist
            if d[v] > dnew:
                d[v] = dnew
                heappush(q,(dnew,v))
    return d

N = I()
a,b,c = LIR(N-1,3)
Q,K = LI()
x,y = LIR(Q,2)

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

d = dijkstra(E,K-1,N,inf=10**9*(N-1)+1)

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

from heapq import heappop, heappush
def dijkstra(E,s,n):
    d = [float('inf')]*n
    d[s] = 0
    q = []
    heappush(q,(0,s))
    while q:
        du,u = heappop(q)
        if d[u] < du:
            continue
        for v,weight in E[u].items():
            dnew = du + weight
            if d[v] > dnew:
                d[v] = dnew
                heappush(q,(dnew,v))
    return d

N = I()
a,b,c = LIR(N-1,3)
Q,K = LI()
x,y = LIR(Q,2)

E = [dict() for _ in range(N)]
for i in range(N-1):
    E[a[i]-1][b[i]-1] = c[i]
    E[b[i]-1][a[i]-1] = c[i]

d = dijkstra(E,K-1,N)

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

Submission status: Accepted

Solution code:
def dijkstra_list(graph, startidx):
    # 頂点数
    n_nodes = len(graph)
    
    # 各頂点の情報
    nodes = []
    for i in range(n_nodes):
        nodes.append([
            float("inf"), # cost
            None,         # from
            False,        # 確定したか？
            i             # 自分自身の頂点番号(0-indexed)、nodesのindexと一致するはず
        ])

    # 優先度付きキューの準備
    import heapq
    priority_queue = []
    heapq.heapify(priority_queue)

    # 初期化
    nodes[startidx][0] = 0
    nodes[startidx][1] = None
    nodes[startidx][2] = True

    # 始点から到達できるnodeを優先度付きキューに入れる
    for dst, cost in graph[startidx]:
        if nodes[dst][0] > nodes[startidx][0]+cost:
            nodes[dst][0] = nodes[startidx][0]+cost
            nodes[dst][1] = startidx
            heapq.heappush(priority_queue, nodes[dst])
    
    # heapqから一つ取り出し（最小コストの未確定頂点が取り出される）確定させた上で、
    # 新たに確定した点から行ける頂点をキューに入れる
    # これをすべての点が確定するまで繰り返す
    n_done = 1
    while priority_queue:
        if n_done == n_nodes:
            break

        node = heapq.heappop(priority_queue)
        if node[2]: # 確定済みであれば次の頂点を取り出す
            continue
        
        node[2] = True
        n_done += 1

        for dst, cost in graph[node[3]]:
            if nodes[dst][0] > nodes[node[3]][0]+cost:
                nodes[dst][0] = nodes[node[3]][0]+cost
                nodes[dst][1] = node[3]
                heapq.heappush(priority_queue, nodes[dst])

    costs = [node[0] for node in nodes]
    froms = [node[1] for node in nodes]
    return  costs, froms

def resolve():
    N = int(input())
    adjs = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = list(map(int, input().split()))
        adjs[a-1].append([b-1, c])
        adjs[b-1].append([a-1, c])
    Q, K = list(map(int, input().split()))
    queries = [list(map(int, input().split())) for _ in range(Q)]
    costs, _ = dijkstra_list(adjs, K-1)
    for q in queries:
        print(costs[q[0]-1]+costs[q[1]-1])


if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

n=int(input())

tree=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=nii()
  a-=1
  b-=1
  tree[a].append([b,c])
  tree[b].append([a,c])

q,k=nii()
k-=1

dist=[-1 for i in range(n)]
dist[k]=0

que=deque()
que.append(k)

while que:
  x=que.popleft()
  for tb,tc in tree[x]:
    if dist[tb]==-1:
      que.append(tb)
      dist[tb]=dist[x]+tc

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(200000)

def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):
    edges = [[] for _ in range(N+1)]
    for aa, bb, cc in zip(a, b, c):
        edges[aa].append((bb, cc))
        edges[bb].append((aa, cc))
    costs = [None] * (N + 1)
    def dfs(n, cost):
        if costs[n] is not None:
            return
        costs[n] = cost
        for nn, cc in edges[n]:
            dfs(nn, cost+cc)
    dfs(K, 0)
    for xx, yy in zip(x, y):
        print(costs[xx]+costs[yy])
    return

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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)

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
def input():
    return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    G = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        G[a].append([b, c])
        G[b].append([a, c])
    q, k = list(map(int, input().split()))
    k -= 1
    stack = deque([k, ])
    ans = [-1] * n
    ans[k] = 0
    while stack:
        x = stack.popleft()
        for (dx, l) in G[x]:
            if ans[dx] == -1:
                ans[dx] = ans[x] + l
                stack.appendleft(dx)
    for _ in range(q):
        x, y = list(map(lambda x: int(x) - 1, input().split()))
        print(ans[x] + ans[y])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# dijkstra -- START --
def dijkstra(n,s,edge):
  d=[inf]*n
  used=[False]*n
  d[s]=0
  used[s]=True
  pq=[]
  for e in edge[s]:
    heapq.heappush(pq,e)
  while pq:
    c,v=heapq.heappop(pq)
    if used[v]:
      continue
    d[v]=c
    used[v]=True
    for nc,nv in edge[v]:
      if not used[nv]:
        nd=nc+c
        if d[nv]>nd:
          heapq.heappush(pq,(nd,nv))
  return d
# dijkstra --- END ---

def main():
  n=I()
  e=[[] for _ in range(n)]
  for _ in range(n-1):
    a,b,c=LI()
    a-=1
    b-=1
    e[a].append((c,b))
    e[b].append((c,a))

  q,k=LI()
  d=dijkstra(n,k-1,e)

  ans=[]
  for _ in range(q):
    x,y=LI()
    x-=1
    y-=1
    dist=d[x]+d[y]
    ans.append(dist)

  for x in ans:
    print(x)

main()
# print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque

N = int(input())

neighbor = defaultdict(dict)

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

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

dp = [-1] * N

d = deque()
d.append((K, 0, -1))

while d:
    i, cost, parent = d.pop()

    dp[i] = cost

    for j, c in neighbor[i].items():
        if j != parent:
            d.append((j, cost+c, i))

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

Submission status: Accepted

Solution code:
def main():
    import sys

    def I():
        return int(sys.stdin.readline().rstrip())

    def S():
        return sys.stdin.readline().rstrip()

    N = I()
    G = [[] for i in range(N + 1)]

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

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

    from collections import deque

    distance = [-1] * (N + 1)  # arrive[i] = 頂点Kからの最短距離
    distance[K] = 0

    q = deque([K])
    while q:
        a = q.pop()
        for b, c in G[a]:
            if distance[b] != -1:
                continue
            distance[b] = distance[a] + c
            q.appendleft(b)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def S(): return sys.stdin.readline().rstrip()

N = I()
G = [[] for i in range(N+1)]

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

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

from collections import deque

distance = [-1]*(N+1)  # arrive[i] = 頂点Kからの最短距離
distance[K] = 0

q = deque([K])
while q:
    a = q.pop()
    for b,c in G[a]:
        if distance[b] != -1:
            continue
        distance[b] = distance[a] + c
        q.appendleft(b)

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

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def S(): return sys.stdin.readline().rstrip()

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

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

from collections import deque

distance = [-1]*(N+1)  # arrive[i] = 頂点Kからの最短距離
distance[K] = 0

q = deque([K])
while q:
    a = q.pop()
    for b,c in G[a]:
        if distance[b] != -1:
            continue
        distance[b] = distance[a] + c
        q.appendleft(b)

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

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
route = [[] for i in range(n+1)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    route[a].append((b,c))
    route[b].append((a,c))
q,k = map(int,input().split())
ans = [-1 for i in range(n+1)]
ans[k] = 0
d = deque()
d.append((k,0))
while d:
    now,cost = d.popleft()
    for i , j in route[now]:
        if ans[i] == -1:
            ans[i] = cost+j
            d.append((i,cost+j))
for i in range(q):
    x,y = map(int,input().split())
    print(ans[x]+ans[y])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n=int(input())
edges=[[] for i in range(n)]
for i in range(n-1):
    a,s,d=map(int,input().split())
    edges[a-1].append((s-1,d));edges[s-1].append((a-1,d))
q,k=map(int,input().split())
cost=[0]*n
from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
for to,cos in edges[k-1]:
    dq.append((k-1,to))
    cost[to]=cos
while dq:
    par,now=dq.popleft()
    
    for to,c in edges[now]:
        if to!=par:
            cost[to]=cost[now]+c
            dq.append((now,to))

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

Submission status: Accepted

Solution code:
n=int(input())
edges=[[] for i in range(n)]
for i in range(n-1):
    a,s,d=map(int,input().split())
    edges[a-1].append((s-1,d));edges[s-1].append((a-1,d))
q,k=map(int,input().split())
cost=[0]*n
from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
for to,cos in edges[k-1]:
    dq.append((k-1,to))
    cost[to]=cos
while dq:
    par,now=dq.popleft()
    
    for to,c in edges[now]:
        if to!=par:
            cost[to]=cost[now]+c
            dq.append((now,to))

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N = int(input())
a = [[] for i in range(N)]
for i in range(N-1):
  A, B, C = map(int, input().split())
  a[A-1].append([B-1, C])
  a[B-1].append([A-1, C])
dist = [-1]*N
Q, K = map(int, input().split())
dist[K-1] = 0

def dfs(now):
  for i, dis_e in a[now]:
    if dist[i] == -1:
      dist[i] = dist[now] + dis_e
      dfs(i)

def main():
  dfs(K-1)
  ans = []
  for i in range(Q):
    x, y = map(int, input().split())
    ans.append(dist[x-1]+dist[y-1])
  print(*ans, sep = "\n")

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N = int(input())
a = [[] for i in range(N)]
for i in range(N-1):
  A, B, C = map(int, input().split())
  a[A-1].append([B-1, C])
  a[B-1].append([A-1, C])
dist = [-1]*N
Q, K = map(int, input().split())
dist[K-1] = 0

def dfs(now):
  for i, dis_e in a[now]:
    if dist[i] == -1:
      dist[i] = dist[now] + dis_e
      dfs(i)

def main():
  dfs(K-1)
  ans = []
  for i in range(Q):
    x, y = map(int, input().split())
    print(dist[x-1]+dist[y-1])
  #print(*ans, sep = "\n")

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import heapq

n = int(input())

g = [[] for _ in range(n)]
for i 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())

dis = [float("inf")] * n
dis[k-1] = 0
pq = [(0, k-1)]
while pq:
    d, node = heapq.heappop(pq)
    if d > dis[node]: continue

    for nxt, cost in g[node]:
        if d + cost < dis[nxt]:
            dis[nxt] = d + cost
            heapq.heappush(pq, (dis[nxt], nxt))

ans = []
for i in range(q):
    x, y = map(int, input().split())

    ans.append(dis[x-1]+dis[y-1])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)


def dfs(node, dis, adj_list):

    for next, d in adj_list[node]:
        if dis[next] == float("inf"):
            dis[next] = dis[node] + d
            dfs(next, dis, adj_list)

    return


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


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

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

k -= 1
dis = [float("inf")] * n
dis[k] = 0
dfs(k, dis, adj_list)

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

Submission status: Accepted

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

n = int(input())
edges = [[] for _ in range(n)]
costs = [-1]*n
def dfs(current):

    for nex, cost in edges[current]:
        if costs[nex] != -1:
            continue
        costs[nex] = costs[current] + cost
        dfs(nex)

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
costs[k] = 0
dfs(k)

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

for ans in res:
    print(ans)

Submission status: Accepted

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

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

def dfs(v):
    for u, du in to[v]:
        if dist_k[u] != -1:
            continue
        dist_k[u] = dist_k[v] + du
        dfs(u)
dfs(k)
dist_xky = [0] * q
for i in range(q):
    x, y = map(int, input().split())
    dist_xky[i] = dist_k[x] + dist_k[y]
print(*dist_xky, sep='\n')

Submission status: Accepted

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

def main():
	N = int(input())
	edge = [[] for _ in range(N)]
	for _ in range(N-1):
		a,b,d = map(int,input().split())
		edge[a-1].append((b-1,d))
		edge[b-1].append((a-1,d))
	
	Q,K = map(int,input().split())
	dist = [-1]*N
	dist[(K-1)] = 0
	q = [(0,K-1)]
	heapq.heapify(q)
	while q:
		_,now = heapq.heappop(q)
		for fol,d in edge[now]:
			if dist[fol] == -1:
				dist[fol] = dist[now]+d
				heapq.heappush(q,(dist[fol],fol))
	
	for _ in range(Q):
		a,b = map(int,input().split())
		print(dist[a-1]+dist[b-1])
	
if __name__ == "__main__":
	main()

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

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

Q,K = IL()
d = [-1 for i in range(N)]
d[K-1] = 0
q = deque([K-1])
while q:
  u = q.pop()
  for v,c in graph[u]:
    if d[v] < 0:
      d[v] = d[u]+c
      q.append(v)
for _ in range(Q):
  x,y = IL()
  print(d[x-1]+d[y-1])

Submission status: Accepted

Solution code:
from collections import deque
import sys

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


N = int(input())

G = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b, c = [int(_) for _ in input().split()]
    G[a].append((b, c))
    G[b].append((a, c))
Q, K = [int(_) for _ in input().split()]

# make tree
G2 = [10 ** 12] * (N + 1)

G2[K] = 0


def f():
    que = deque()
    que.append((K, 0))
    while que:
        v, p = que.pop()
        for nv, nc in G[v]:
            if nv == p: continue
            G2[nv] = G2[v] + nc
            que.append((nv, v))


f()

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

Submission status: Accepted

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10 ** 9)

N = int(input())

G = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b, c = [int(_) for _ in input().split()]
    G[a].append((b, c))
    G[b].append((a, c))
Q, K = [int(_) for _ in input().split()]

# make tree
G2 = [10 ** 12] * (N + 1)

G2[K] = 0


def f():
    que = deque()
    que.append((K, 0))
    while que:
        v, p = que.pop()
        for nv, nc in G[v]:
            if nv == p: continue
            G2[nv] = G2[v] + nc
            que.append((nv, v))


f()

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

Submission status: Accepted

Solution code:
N = int(input())
from heapq import heapify, heappush, heappop

inf = float("inf")
def dijkstra(graph, start):  # graphは隣接リスト(繋がっている先, コスト)
    vsize = len(graph)
    dist = [inf] * vsize
    seen = [False] * vsize
    prev = [None] * vsize
    pq = []
    heapify(pq)

    dist[start] = 0
    heappush(pq, (0, start))  # heapではtuple[0]で比較されるのでこの順番で追加する
    while pq:
        cost, u = heappop(pq)
        seen[u] = True
        if dist[u] < cost:
            continue
        for v, w in graph[u]:
            temp_cost = dist[u] + w
            if not seen[v] and temp_cost < dist[v]:
                dist[v] = temp_cost
                prev[v] = u
                heappush(pq, (dist[v], v))
    return dist
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))
Q, K = map(int, input().split())
shortest_path_K = dijkstra(graph, K-1)
for _ in range(Q):
    x, y = map(int, input().split())
    print(shortest_path_K[x-1]+shortest_path_K[y-1])

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    n = int(input())
    v = [[0]+[]*(n+1) for i in range(n+1)]
    for i in range(n-1):
        a,b,c = map(int,input().split())
        v[a].append([b,c])
        v[b].append([a,c])

    q,k = map(int,input().split())
    l = [k]
    while l:
        now = l.pop()
        for i in v[now][1:]:
            if v[i[0]][0] == 0:
                v[i[0]][0] = i[1]+v[now][0]
                l.append(i[0])

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    n = int(input())
    v = [[0]+[]*(n+1) for i in range(n+1)]
    for i in range(n-1):
        a,b,c = map(int,input().split())
        v[a].append([b,c])
        v[b].append([a,c])

    q,k = map(int,input().split())
    l = [k]
    while l:
        now = l.pop()
        for i in v[now][1:]:
            if v[i[0]][0] == 0:
                v[i[0]][0] = i[1]+v[now][0]
                l.append(i[0])

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

q,k = map(int,input().split())
l = [k]
while l:
    now = l.pop()
    for i in v[now][1:]:
        if v[i[0]][0] == 0:
            v[i[0]][0] = i[1]+v[now][0]
            l.append(i[0])

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

Submission status: Accepted

Solution code:
n = int(input())
v = [[0]+[]*(n+1) for i in range(n+1)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    v[a].append([b,c])
    v[b].append([a,c])

q,k = map(int,input().split())
l = [k]
while l:
    now = l.pop()
    for i in v[now][1:]:
        if v[i[0]][0] == 0:
            v[i[0]][0] = i[1]+v[now][0]
            l.append(i[0])
            
for i in range(q):
    x,y = map(int,input().split())
    print(v[x][0]+v[y][0])