Problem:


Score : 400 points

Problem Statement

You are given a tree with N vertices.

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

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

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

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

Constraints

3≤N≤10^5 

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

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

The given graph is a tree.

1≤Q≤10^5 

1≤K≤N 

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

x_j≠y_j (1≤j≤Q) 

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

Input

Input is given from Standard Input in the following format:  

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

Output

Print the responses to the queries in Q lines.

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

Sample Input 1

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

Sample Output 1

3
2
4

The shortest paths for the three queries are as follows:

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

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

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

Sample Input 2

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

Sample Output 2

5
14
22

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

Sample Input 3

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

Sample Output 3

17000000000



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


Sample output:
3
2
4

Submission status: Accepted

Solution code:
import sys
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.popleft()
        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)

Submission status: Accepted

Solution code:
import heapq


class Dijkstra:
    """ダイクストラ法を行う.0-index"""

    def __init__(self, graph, start_point, goal_point=None):
        """Intialization.

        :param graph:List[Dict[int, int]]
        :param start_point: start index
        :param goal_point: goal index
        """
        node_num = len(graph)
        self.graph = graph
        self.start_point = start_point
        self.goal_point = goal_point
        self.dist = [float("inf") for _ in range(node_num)]
        self.prev = [float("inf") for _ in range(node_num)]

    def run(self):
        self.dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            # priority queueから最短距離の点をとりだす.
            prev_cost, src = heapq.heappop(heap_q)

            if self.dist[src] < prev_cost:
                continue

            for dest, cost in self.graph[src].items():
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    # priority queueに到達可能な点を追加する.
                    heapq.heappush(heap_q, (self.dist[dest], dest))
                    self.prev[dest] = src
        if self.goal_point is not None:
            return self.get_path()
        else:
            return self.dist

    def get_path(self):
        path = [self.goal]
        dest = self.goal

        while self.prev[dest] != float("inf"):
            path.append(self.prev[dest])
            dest = self.prev[dest]

        return list(reversed(path))


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

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

solver = Dijkstra(graph, K - 1)
d = solver.run()

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

Submission status: Accepted

Solution code:
from collections import deque

INF = float("inf")


def main():
    N = int(input())
    E = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        E[a] += [(b, c)]
        E[b] += [(a, c)]
    path = [INF] * (N+1)
    Q, K = map(int, input().split())
    q = deque([(K, 0)])
    while len(q):
        x, cost = q.popleft()
        path[x] = cost
        for e in E[x]:
            nx, nc = e
            if path[nx] == INF:
                q.append((nx, cost+nc))
    for _ in range(Q):
        x, y = map(int, input().split())
        print(path[x] + path[y])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s):
    d = [float("inf")]*n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d
n = int(input())
edge = [[] for i in range(n)]
for i in range(n-1):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1])
Q,K = map(int,input().split())
L = dijkstra_heap(K-1)
query = []
for i in range(Q):
  query.append(list(map(int,input().split())))
for i in range(Q):
  print(L[query[i][0]-1]+L[query[i][1]-1])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
"""
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
n = I()
a = IR(n)
l = a[0]
for i in range(1,n):
    g = gcd(l,a[i])
    l *= a[i]//g
print(l)
"""

#B
n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = LI()
    a -= 1
    b -= 1
    v[a].append([b,c])
    v[b].append([a,c])
Q,k = LI()
d = [-1 for i in range(n)]
d[k-1] = 0
q = deque()
q.append(k-1)
while q:
    x = q.pop()
    for y,c in v[x]:
        if d[y] == -1:
            d[y] = d[x]+c
            q.append(y)
for i in range(Q):
    x,y = LI()
    x -= 1
    y -= 1
    print(d[x]+d[y])
#C

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
"""
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
n = I()
a = IR(n)
l = a[0]
for i in range(1,n):
    g = gcd(l,a[i])
    l *= a[i]//g
print(l)
"""

#B
def dijkstra(k):
    d[k] = 0
    q = [[0,k]]
    while q:
        dx,x = heappop(q)
        for y,c in v[x]:
            if d[y] > dx+c:
                d[y] = dx+c
                heappush(q,[d[y],y])

n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = LI()
    a -= 1
    b -= 1
    v[a].append([b,c])
    v[b].append([a,c])
q,k = LI()
d = [float("inf") for i in range(n)]
dijkstra(k-1)
for i in range(q):
    x,y = LI()
    x -= 1
    y -= 1
    print(d[x]+d[y])
#C

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
from collections import*
input=open(0).readline
n=int(input())
e=[[]for _ in range(n)]
for _ in range(n-1):
    a,b,c=map(int,input().split())
    e[a-1].append((b-1,c))
    e[b-1].append((a-1,c))
q,k=map(int,input().split())
d=[0]*n
f=[0]*n
f[k-1]=1
s=deque([(k-1,0)])
while s:
    t,c=s.pop()
    f[t]=1
    d[t]=c
    for i,v in e[t]:
        if not f[i]:
            s.append((i,v+c))
for _ in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Submission status: Accepted

Solution code:
def solve(N, ABCs, Q, K, XYs):
    path = [[] for _ in range(N + 1)]
    for (a, b, c) in ABCs:
        path[a].append((b, c))
        path[b].append((a, c))

    dst = [0 for _ in range(N + 1)]

    q = [K]
    while len(q):
        index = q.pop()
        for n, w in path[index]:
            if dst[n] == 0:
                dst[n] = dst[index] + w
                q.append(n)
    ans = []
    for x, y in XYs:
        ans.append(str(dst[x] + dst[y]))
    return "\n".join(ans)

if __name__ == "__main__":
    N = int(input())
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    Q, K = tuple(map(int, input().split(" ")))
    XYs = [tuple(map(int, input().split(" "))) for _ in range(Q)]
    print(solve(N, ABCs, Q, K, XYs))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

def dfs(v, p, d):
  depth[v] = d
  for to, c in ablist[v]:
    if to == p:
      continue
    dfs(to, v, d + c)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs(n,p,d):
    visited[n] = True
    dist[n] = d
    for (i,c) in A[n]:
        if i != p and not visited[i]:
            dfs(i,n,d+c)

N = int(input())
A = [[] for _ in range(N)]
for _ 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))
Q,K = map(int,input().split())
B = []
for _ in range(Q):
    x,y = map(int,input().split())
    B.append((x,y))

dist = [-1]*N
visited = [False]*N
dfs(K-1,N,0)

for (x,y) in B:
    print(dist[x-1]+dist[y-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
abc = [[int(j) for j in input().split()] for _ in range(N-1)]
Q,K = map(int, input().split())
xy = [ [int(j) for j in input().split()] for _ in range(Q)]

inf = float("inf")
con = [ [] for _ in range(N+1)]
# cost = [ [inf] * (N+1) for _ in range(N+1)]
# cost = {}
from collections import defaultdict
# cost =  defaultdict(  )

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

q = [(K,0)]
visited = [False] * (N+1)
visited[K] = True
costmap = [inf] * (N+1)
costmap[K] = 0
while q:
    n,cst = q.pop()
    for ch,chcst in con[n]:
        if visited[ch]:
            continue
        q.append( (ch, cst+chcst))
        visited[ch] = True
        costmap[ch]  = cst+ chcst
    
# def dfs(a,b, par):
#     if cost[a][b] != inf :
#         return cost[a][b]
# 
#     if len(list(filter(lambda x: x!=par, con[a]))) == 0:
#         return inf
# 
#     cst = inf
#     idx= -1
#     for e,ch in enumerate(con[a]):
#         if ch == par:
#             continue
#         if cst > cost[a][ch] + dfs(ch,b,a):
#             cst = cost[a][ch] + dfs(ch,b,a)
#             
#             idx = e
#     if idx != -1:
#         cost[a][b] = cst
#         cost[b][a] = cst
#     return cst
# 
for i in range(Q):
    x,y = xy[i]
    print( costmap[x] + costmap[y])
# for i in range(Q):
#     x,y = xy[i]
#     # _ = dfs(K,x,None)
#     # _ = dfs(y,K, None)
#     print(dfs(x,K,None) + dfs(K,y,None))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

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

def dijkstra(g,st):
    from heapq import heappush, heappop, heapify
    inf=10**18
    dist=[inf for i in range(len(g))]
    visited=[False for i in range(len(g))]
    dist[st]=0
    que=[]
    heappush(que,(0,st))
    while que:
        c,v=heappop(que)
        if visited[v]:
            continue
        visited[v]=True
        for x in g[v]:
            tmp=x[0]+c
            if tmp<dist[x[1]] and not visited[x[1]]:
                dist[x[1]]=tmp
                heappush(que,(tmp,x[1]))
    return dist

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

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

Submission status: Accepted

Solution code:
#O(ElogV)
import heapq
import sys
input = sys.stdin.readline

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

################################
n = int(input())

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

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
Adjacent_list = [[] for x in range(n)]
check = [-1 for i in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    Adjacent_list[a-1].append([b,c])
    Adjacent_list[b-1].append([a,c])
q,k = map(int,input().split())
deq = deque()
deq.appendleft([k,0])
check[k-1] = 0
while deq:
    num = deq.pop()
    for i in range(len(Adjacent_list[num[0]-1])):
        ls = Adjacent_list[num[0]-1][i]
        if check[ls[0]-1] != -1:
            continue
        check[ls[0]-1] = num[1] + ls[1]
        deq.appendleft([ls[0],num[1]+ls[1]])
for i in range(q):
    x,y = map(int,input().split())
    print(check[x-1]+check[y-1])

Submission status: Accepted

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

# distance from node [K]
dists = [None] * (N + 1)
dists[K] = 0
q = deque([K])
while len(q) > 0:
    v = q.popleft()
    d = dists[v]
    for to, c in tree[v]:
        if dists[to] is None:
            dists[to] = d + c
            q.append(to)

for x, y in XY:
    ans = dists[x] + dists[y]
    print(ans)

Submission status: Accepted

Solution code:
# D dijkstra
N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    ai,bi,ci = map(int, input().split())
    edge[ai-1].append((bi-1, ci))
    edge[bi-1].append((ai-1, ci))
Q,K = map(int, input().split())
K = K-1
x,y = [],[]
for _ in range(Q):
    xi,yi = map(int, input().split())
    x.append(xi-1)
    y.append(yi-1)


dist = [float('inf') for _ in range(N)]
import heapq
def dijkstra(start:int):
    """priority_queue ver. O(|E|log|V|)
    """
    global dist # list dist[|V|]
    global edge # 隣接リスト
    dist[start] = 0
    q = [(0,start)] # （暫定的な距離，頂点）
    while q:
        d_cur,cur = heapq.heappop(q)
        if dist[cur] < d_cur:
            continue
        for nex,cost in edge[cur]:
            if dist[nex] > dist[cur]+cost:
                dist[nex] = dist[cur]+cost
                heapq.heappush(q, (dist[nex], nex))


dijkstra(K)
for xi,yi in zip(x,y):
    print(dist[xi] + dist[yi])

Submission status: Accepted

Solution code:
# D
N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    ai,bi,ci = map(int, input().split())
    edge[ai-1].append((bi-1, ci))
    edge[bi-1].append((ai-1, ci))
Q,K = map(int, input().split())
K = K-1
x,y = [],[]
for _ in range(Q):
    xi,yi = map(int, input().split())
    x.append(xi-1)
    y.append(yi-1)


dist = [float('inf')]*N # from K
visited = [False]*N
q = [K]
dist[K] = 0
visited[K] = True
while q:
    cur = q.pop()
    visited[cur] = True
    for nex,cost in edge[cur]:
        if not visited[nex]:
            q.append(nex)
            dist[nex] = dist[cur]+cost
#print(dist)
for xi,yi in zip(x,y):
    print(dist[xi] + dist[yi])

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(1000000)
d=defaultdict(list)

N=int(input())
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())

# Kを中心とした距離を求める
dists=[None]*(N+1)
isused=[False]*(N+1)
dists[K]=0
isused[K]=True

def dfs(n):
    for i,j in d[n]:
        if isused[i]:continue
        isused[i]=True
        dists[i]=dists[n]+j
        dfs(i)

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

Submission status: Accepted

Solution code:
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
import sys
sys.setrecursionlimit(10 ** 6)
n=I()
nl=[[] for i in range(n)]
used=[False for i in range(n)]
for i in range(n-1):
    a,b,c=IL()
    nl[a-1].append([b-1,c])
    nl[b-1].append([a-1,c])
d=[None for i in range(n)]
def dfs(now,pre,dis):
    used[now]=True
    d[now]=dis
    for i in nl[now]:
        if i[0]!=pre and not used[i[0]]:
            dfs(i[0],now,dis+i[1])
    
    return
q,k=IL()
dfs(k-1,-1,0)
for i in range(q):
    x,y=IL()
    print(d[x-1]+d[y-1])

Submission status: Accepted

Solution code:
import heapq

G = [{}]

def setNode(n):
  global G
  G = [{} for i in range(n)]
def solve(s, n):
  global G
  fixed = [None]*n
  q = []
  heapq.heappush(q, (0,s))
  while q:
    w,x = heapq.heappop(q)
    if fixed[x] is not None: continue
    fixed[x] = w
    for y in G[x]:
        if fixed[y] is None:
            heapq.heappush(q, (w + G[x][y], y))
  return fixed


n = int(input())
setNode(n)
for i in range(n-1):
  s,t,w = map(int,input().split())
  G[s-1][t-1] = w
  G[t-1][s-1] = w
Q, K = map(int, input().split())
dist = solve(K-1,n)
for i in range(Q):
    x, y = map(int,input().split())
    print(dist[x-1]+dist[y-1])

Submission status: Accepted

Solution code:
N=int(input())
from collections import defaultdict
d=defaultdict(list)
f=defaultdict(int)
for _ in range(N-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c,a])
    d[b].append([a,c,b])
Q,K=map(int,input().split())

dist=defaultdict(int)
dist[K]=0
f[K]=1
que=d[K]
prev=defaultdict(int)
prev[K]=0
while len(que)>0:
    tmp=[]
    tmpd=defaultdict(int)
    for t,c,e in que:
        if f[t]==0:
            dist[t]=c+dist[e]
            tmpd[t]=c+dist[e]
            f[t]=1
            tmp+=d[t]
    prev=tmpd
    que=tmp

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

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())
    G[a - 1].append((b - 1, c))
    G[b - 1].append((a - 1, c))

Q, K = map(int, input().split())
dist = [-1] * N


def dfs(u, par, d):
    dist[u] = d
    for w, cost in G[u]:
        if w == par:
            continue
        dfs(w, u, d + cost)


dfs(K - 1, -1, 0)

for i 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:
import sys
sys.setrecursionlimit(10 ** 8)


class Solve():
    def __init__(self):
        self.N = int(input())
        self.route = [dict() for _ in range(self.N)]
        for _ in range(self.N - 1):
            a, b, c = map(int, input().split())
            self.route[a - 1][b - 1] = c
            self.route[b - 1][a - 1] = c
        self.Q, self.K = map(int, input().split())
        self.K -= 1
        self.query = []
        for _ in range(self.Q):
            x, y = map(int, input().split())
            self.query.append([x - 1, y - 1])
        self.depth = [0 for _ in range(self.N)]

    def DFS(self, v, p, d):
        self.depth[v] = d
        for dest, cost in self.route[v].items():
            if dest == p:
                continue
            self.DFS(dest, v, d + cost)

    def execute(self):
        self.DFS(self.K, -1, 0)
        for x, y in self.query:
            print(self.depth[x] + self.depth[y])


if __name__ == '__main__':
    Solve().execute()

Submission status: Accepted

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

def dijkstra(x,route):
    d=[float('inf')]*n
    d[x]=0
    visited={x}
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        visited.add(u)
        for node,cost in route[u]:
            if (node not in visited) and d[node]>d[u]+cost:
                d[node]=d[u]+cost
                heapq.heappush(hq,(d[node],node))
    return d
q,k=map(int,input().split())
k-=1
dist=dijkstra(k,edges)
for _ in range(q):
    start,goal=map(int,input().split())
    print(dist[start-1]+dist[goal-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n = int(input())
tree= [[] for i in range(n)]

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

depth=[0]*n
visited=[False for i in range(n)]
def dfs(start,kyori):
  depth[start] = kyori
  visited[start]=True
  
  for to in tree[start]:
    if not visited[to[0]]:
      dfs(to[0],kyori+to[1])
  return

dfs(k,0)

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import heapq
from collections import defaultdict

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def dijkstra(start: int, size: int, G: dict) -> list:
    costs = [INF] * size
    costs[start] = 0
    hp = []
    heapq.heappush(hp, (0, start))
    while hp:
        hc, hv = heapq.heappop(hp)
        for to, move_cost in G[hv]:
            if hc + move_cost >= costs[to]:
                continue
            costs[to] = hc + move_cost
            heapq.heappush(hp, (costs[to], to))

    return costs


n = II()

G = defaultdict(list)
for _ in range(n - 1):
    a, b, c = LI()
    a -= 1
    b -= 1
    G[a].append((b, c))
    G[b].append((a, c))

q, k = LI()
k -= 1
C = dijkstra(k, n, G)

for _ in range(q):
    x, y = LI_()
    print(C[x] + C[y])

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import heapq
from collections import defaultdict

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def dijkstra(start: int, size: int, graph: dict) -> list:
    costs = [INF] * size
    costs[start] = 0
    visited = set()
    hp = []
    heapq.heappush(hp, (0, start))
    while hp:
        hc, hv = heapq.heappop(hp)
        if hv in visited:
            continue
        for to, move_cost in graph[hv]:
            if hc + move_cost >= costs[to]:
                continue
            costs[to] = hc + move_cost
            heapq.heappush(hp, (costs[to], to))
        visited.add(hv)

    return costs


n = II()

G = defaultdict(list)
for _ in range(n - 1):
    a, b, c = LI()
    a -= 1
    b -= 1
    G[a].append((b, c))
    G[b].append((a, c))

q, k = LI()
k -= 1
C = dijkstra(k, n, G)

for _ in range(q):
    x, y = LI_()
    print(C[x] + C[y])

Submission status: Accepted

Solution code:

from collections import deque

N = int(input())
tree = [[] for _ in range(N)]

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

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

depth = [0 for _ in range(N)]

def bfs(v, p = -1, d = 0):
    q = deque()
    q.append([v, p, d])
    while len(q)>0:
        cur = q.popleft()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            q.append([i, cur[0], cur[2] + j])

bfs(K)

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = 10 ** 20
n = int(input())
edges = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    edges[a].append((b, c))
    edges[b].append((a, c))

q, k = map(int, input().split())
k -= 1
dist = [INF] * n
dist[k] = 0
que = []
heappush(que, (0, k))
while que:
    score, node = heappop(que)
    for to, cost in edges[node]:
        newScore = score + cost
        if dist[to] > newScore:
            dist[to] = newScore
            heappush(que, (newScore, to))

for _ 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:
# N 個の頂点、N-1 個の辺なので K を根にした木構造に変換する

N = int(input())
T = {}
D = [None] * (N+1)
F = [True] * (N+1)

for n in range(N+1):
    T[n] = []

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

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

D[K] = 0
F[K] = False

L = [K]

while len(L) > 0:
    L_tmp = []
    for k in L:
        for t in T[k]:
            b, c = t
            if F[b] == True:
                D[b] = D[k] + c
                F[b] = False
                L_tmp.append(b)
    L = L_tmp

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

Submission status: Accepted

Solution code:
n = int(input())
# [[[ノード1, 距離3],[ノード3, 距離5]],[],...]
tree = [[] for _ in range(n+10)]
visited = [-1 for _ in range(n+10)]
# abc = [[0, 0, 0] for _ in range(n)]
for i in range(n-1):
    a, b, c = [int(j) for j in input().split()]
    tree[a - 1].append([b - 1, c])
    tree[b - 1].append([a - 1, c])
q, k = [int(i) for i in input().split()]

stack = [[k-1, 0]]
while True:
    size = len(stack)
    if size == 0:
        break
    now, cost = stack.pop()
    visited[now] = cost
    for i in range(len(tree[now])):
        if visited[tree[now][i][0]] == -1:
            stack.append([tree[now][i][0],
                          cost+tree[now][i][1]])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = (int)(input())
edges = []
for _ in range(N-1):
    edges.append((list)(map(int, input().split())))

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

'''
 N:num of nodes
 Q: num of query
 K: node must passed in query

'''
dist = [[] for _ in range(N+1)]
for e in edges:
    dist[e[0]].append([e[1], e[2]])
    dist[e[1]].append([e[0], e[2]])

dist_from_k = [-1]*(N+1)


def dfs(v, cost):
    if dist_from_k[v] != -1:
        return

    dist_from_k[v] = cost
    for e in dist[v]:
        dfs(e[0], cost+e[1])


dfs(K, 0)

for q in querys:
    print(dist_from_k[q[0]] + dist_from_k[q[1]])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = (int)(input())
edges = []
for _ in range(N-1):
    edges.append((list)(map(int, input().split())))

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

'''
 N:num of nodes
 Q: num of query
 K: node must passed in query

'''
dist = [-1]*(N+1)
for e in edges:
    if dist[e[0]] == -1:
        dist[e[0]] = [[e[1], e[2]]]
    else:
        dist[e[0]].append([e[1], e[2]])

    if dist[e[1]] == -1:
        dist[e[1]] = [[e[0], e[2]]]
    else:
        dist[e[1]].append([e[0], e[2]])

dist_from_k = [-1]*(N+1)


def dfs(v, cost):
    if dist_from_k[v] != -1:
        return

    dist_from_k[v] = cost
    for e in dist[v]:
        dfs(e[0], cost+e[1])


dfs(K, 0)

for q in querys:
    print(dist_from_k[q[0]] + dist_from_k[q[1]])

Submission status: Accepted

Solution code:
import heapq, collections

n = int(input())
distance = collections.defaultdict(dict)
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    distance[a - 1][b - 1] = c
    distance[b - 1][a - 1] = c
q, k = map(int, input().split())
k -= 1
queries = []
for _ in range(q):
    x, y = map(int, input().split())
    queries.append((x - 1, y - 1))

d = [float('inf')] * (n + 1)
d[k] = 0
queue = [(0, k)]
while queue:
    cost, current = heapq.heappop(queue)
    for nxt in distance[current]:
        if cost + distance[current][nxt] < d[nxt]:
            d[nxt] = cost + distance[current][nxt]
            heapq.heappush(queue, (d[nxt], nxt))

for x, y in queries:
    print(d[x] + d[y])

Submission status: Accepted

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

import sys
def input(): return sys.stdin.readline().strip()

# 再帰呼び出しの回数制限(デフォルト1000)
sys.setrecursionlimit(10 ** 9)

N = int(input())
nodes = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    # nodes[出発ノード](到着ノード, コスト))
    nodes[a].append((b, c))
    # 無向グラフなのでこっちも入れる
    nodes[b].append((a, c))

memo = [0] * (N+1)
def dfs(cur, prev, dist):
    memo[cur] = dist
    for nxt, cost in nodes[cur]:
        if nxt == prev:
            continue
        dfs(nxt, cur, dist+cost)

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

for i in range(Q):
    x, y = map(int, input().split())
    # 今回は全てKを経由するので、Kからの距離さえ分かれば全部出る
    print(memo[x] + memo[y])