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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


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

    """graph.input.linkedlist_with_weight
        input: u[]:start, v[]:end, w[]:weight
        output:g[][]
    """
    g = [[] for i in range(N+1)]
    for i in range(N-1):
        g[a[i]].append([b[i], c[i]])
        g[b[i]].append([a[i], c[i]])

    def dikstra(nodes: int, graph: "List[List[int, int]]", start: int):
        """dikstra
        
        Arguments:
            nodes {int} -- Nodes in graph
            graph {List["List[int, int]"]} -- graph (adjancency matrix)
            start {int} -- start point
        
        Returns:
            [type] -- great distances from start point to each nodes in graph
        """
        INF = 1<<48
        from heapq import heapify, heappop, heappush
        hq = []
        heapify(hq)
        # i-indexed
        colors = ['W'] * (nodes+1)
        d = [INF] * (nodes+1)
        d[start] = 0
    
        heappush(hq, [start, start])
        colors[start] = 'G'
    
        while hq:
            f = hq.pop()
            u = f[1]
            colors[u]= 'B'
            
            if d[u] < -f[0]:
                continue
    
            for adj_i in graph[u]:
                v = adj_i[0]
                if colors[v] == 'B':
                    continue
                if d[v] > d[u] + adj_i[1]:
                    d[v] = d[u] + adj_i[1]
                    heappush(hq, [-d[v], v])
                    colors[v] = 'G'
        return d
    
    d = dikstra(N, g, K)

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

    return



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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):
    """graph.input.linkedlist_with_weight
        input: u[]:start, v[]:end, w[]:weight
        output:g[][]
    """
    INF = 1<<48
    g = [[] for i in range(N+1)]
    for i in range(N-1):
        g[a[i]].append([b[i], c[i]])
        g[b[i]].append([a[i], c[i]])

    from heapq import heapify, heappop, heappush
    hq = []
    heapify(hq)
    # start
    s = K
    colors = ['W'] * (N+1)
    d = [INF] * (N+1)
    d[s] = 0

    heappush(hq, [s, s])
    colors[s] = 'G'

    while hq:
        f = hq.pop()
        u = f[1]
        colors[u]= 'B'
        
        if d[u] < -f[0]:
            continue

        for adj_i in g[u]:
            v = adj_i[0]
            if colors[v] == 'B':
                continue
            if d[v] > d[u] + adj_i[1]:
                d[v] = d[u] + adj_i[1]
                heappush(hq, [-d[v], v])
                colors[v] = 'G'

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

    # print(d)

    return



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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append((b,c))
    edge[b].append((a,c))
Q,K = map(int,input().split())
K -= 1
dist = [-1 for _ in range(N)]
dist[K] = 0
searched = [i == K for i in range(N)]
search = [e for e in edge[K]]
while len(search) > 0:
    e = search.pop()
    n,d = e[0], e[1]
    searched[n] = True
    dist[n] = d
    for c,d2 in edge[n]:
        if searched[c]:
            continue
        search.append((c, d+d2))
for _ in range(Q):
    x,y= map(int, input().split())
    x -= 1
    y -= 1
    print(dist[x]+dist[y])

Submission status: Accepted

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

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

def dfs(v):
    dist = [10 ** 20] * (n+1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        for w,cost in graph[v]:
            if dist[w] >= dist[v] + cost:
                dist[w] = dist[v] + cost
                stack.append(w)
    return dist
q,k = map(int,input().split())
distance = dfs(k)
for i in range(q):
    x,y = map(int,input().split())
    print(distance[x]+distance[y])

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

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

lst=[[] for i in range(n+1)]
# print(lst)
for i in range(n-1):
    a,b,c=abc[i]
    lst[a].append([b,c])
    lst[b].append([a,c])
dist=[float('inf')]*(n+1)
# dist[k]=0
# print(lst)
d=deque()
d.append([[[k,0]],0])
while d:
    tmp=d.popleft()
    # print(tmp)
    for i in range(len(tmp[0])):
        # print(tmp[0][i])
        if dist[tmp[0][i][0]]==float('inf'):
            dist[tmp[0][i][0]]=tmp[0][i][1]+tmp[-1]
            d.append([lst[tmp[0][i][0]],dist[tmp[0][i][0]]])
# print(dist)
for i in range(q):
    x,y=xy[i]
    print(dist[x]+dist[y])

Submission status: Accepted

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

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())
dist = [INF] * N
dist[K-1] = 0

def dfs(n, d):
    if dist[n] == INF:
        dist[n] = d
    for i, c in g[n]:
        if dist[i] == INF:
            dfs(i, dist[n]+c)
    return

dfs(K-1, 0)
# print(dist)

for i 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 ** 8)
N = int(input())
graph = [[] * N for _ in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append([b, c])
    graph[b].append([a, c])
    
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

depth = [0] * N
def dfs(v, p, d):
    depth[v] = d
    for new_v_list in graph[v]:
        new_v = new_v_list[0]
        if new_v == p:
            continue
        dfs(new_v, v, d + new_v_list[1])

dfs(K-1, -1, 0)
for i in range(Q):
    print(depth[xy[i][0] - 1] + depth[xy[i][1] - 1])

Submission status: Accepted

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

# BFSのためのデータ構造
dist = [-1 for _ in range(N)]   # 全頂点を未訪問に
que = deque()

# 初期条件(頂点 K-1 を初期ノードとする)
dist[K-1] = 0
que.append(K-1)

# BFS 開始(キューが空になるまで探索を行う)
while que:
    v = que[0]
    que.popleft()
    for new_v_list in graph[v]:
        new_v = new_v_list[0]
        if dist[new_v] != -1:   # すでに探索済みの頂点は探索しない
            continue
        # 新たな頂点 new_vについて距離情報を更新してキューに追加する
        dist[new_v] = dist[v] + new_v_list[1]
        que.append(new_v)


for i in range(Q):
    print(dist[xy[i][0] - 1] + dist[xy[i][1] - 1])

Submission status: Accepted

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
edges = [[] for _ in range(N+1)] #1-indexed
for i in range(N-1):
    a, b, c = lr()
    edges[a].append((b, c))
    edges[b].append((a, c))

INF = 10 ** 15
dist = [INF] * (N+1)
def set_dist(x, d):
    dist[x] = d
    for next, dd in edges[x]:
        if dist[next] != INF:
            continue
        set_dist(next, d + dd)


Q, K = lr()
set_dist(K, 0)
for i in range(Q):
    x, y = lr()
    print(dist[x] + dist[y])

Submission status: Accepted

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def measure(x):
    dist = [INF] * (N)
    dist[x] = 0
    que = deque()
    que.append(x)
    while que:
        cur = que.popleft()
        cur_dist = dist[cur]
        for next, c in edges[cur]:
            if dist[next] == INF:
                dist[next] = cur_dist + c
                que.append(next)
    
    return dist

N = ir()
INF = 10 ** 15
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = lr()
    edges[a-1].append((b-1, c))
    edges[b-1].append((a-1, c))

Q, K = lr()
dist = measure(K-1)
for _ in range(Q):
    x, y = lr()
    print(dist[x-1] + dist[y-1])


# 20

Submission status: Accepted

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

def DFS(node, p_node, length):
    l[node] = length
    for i, j in graph[node]:
        if i==p_node:
            continue
        DFS(i, node, length+j)
sys.setrecursionlimit(2 * n)
l = [0]*n
DFS(k, -1, 0)
for x, y in xy:
    print(l[x]+l[y])

Submission status: Accepted

Solution code:
from collections import deque


def dfs():
    dis_from_k = [float('inf') for _ in range(N+1)]
    q = deque()
    used = set()
    q.append([K, 0])
    used.add(K)

    while len(q) > 0:
        prv_node, prv_cost = q.pop()
        for node, cost in g[prv_node]:
            if node in used:
                continue
            dis_from_k[node] = min(dis_from_k[node], prv_cost + cost)
            q.append([node, prv_cost + cost])
            used.add(node)
    return dis_from_k


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

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

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

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())

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

def BFS(s):
 dist=[-1 for i in range(n)]
 dist[s]=0

 que=deque()
 que.append(s)

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

 return dist

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

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

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())

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

q,k=map(int,input().split())
dist=[-1 for i in range(n)]
dist[k-1]=0

que=deque()
que.append(k-1)

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

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

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    edge[a-1].append((b-1, c))
    edge[b-1].append((a-1, c))
Q, K = map(int, input().split())
seen = [0] * N
dist = [0] * N
seen[K-1] = 0
todo = deque([(K-1, 0)])
while todo:
    cur_v, cur_weight = todo.pop()
    seen[cur_v] = 1
    dist[cur_v] = cur_weight
    for next_v, next_weight in edge[cur_v]:
        if not seen[next_v]:
            todo.append((next_v, cur_weight + next_weight))

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

Submission status: Accepted

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

q, k = map(int, input().split())
k -= 1
hq = []
d = [10**18] * n
d[k] = 0
heapq.heappush(hq, (0, k))
while len(hq):
    dist, v = heapq.heappop(hq)
    if d[v] < dist:
        continue
    for e in g[v]:
        nv, l = e
        if d[nv] > d[v] + l:
            d[nv] = d[v] + l
            heapq.heappush(hq, (d[nv], nv))

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

def main():    
    for i in range(N-1):
        a, b, c = map(int, input().split())
        a -= 1; b -= 1
        g[a].append((b, c))
        g[b].append((a, c))
        
    Q, K = map(int, input().split())
    K -= 1
        
    q = deque([(K, 0, -1)])

    while q:
        v, c, p = q.popleft()
        
        dist[v] = c
        for u, d in g[v]:
            if u == p: continue
            q.append((u, c+d, v))
    
    for i in range(Q):
        x, y = map(int, input().split())
        print(dist[x-1]+dist[y-1])
 
if __name__ == '__main__':
    N = int(input())
    g = [[] for i in range(N)]
    dist = [0] * N
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop, heapify
input = sys.stdin.readline

def main():
    N = int(input())
    g = [[] for i in range(N)]
    
    for i in range(N-1):
        a, b, c = map(int, input().split())
        a -= 1; b -= 1
        g[a].append((c, b))
        g[b].append((c, a))
        
    Q, K = map(int, input().split())
    K -= 1
    dist = [0] * N
    visited = [False] * N
    
    q = [(c, v) for c, v in g[K]]
    heapify(q)
    
    dist[K], visited[K] = 0, True
    
    while q:
        c, v = heappop(q)
        
        if visited[v]: continue
        dist[v], visited[v] = c, True
        
        for d, u in g[v]:
            if visited[u]: continue
            heappush(q, (c+d, u))
        
    for i in range(Q):
        x, y = map(int, input().split())
        
        print(dist[x-1]+dist[y-1])
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    T = [[] for _ in range(N+1)]
    cost = [None] * (N+1)
    for _ 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())
    cost[K] = 0
    stack = [K]
    while stack:
        x = stack.pop()
        d = cost[x]
        for y, c in T[x]:
            if cost[y] is None:
                cost[y] = d + c
                stack.append(y)
    for _ in range(Q):
        x, y = map(int, input().split())
        print(cost[x]+cost[y])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

def main():
    n = int(input())
    edge = []
    for i in range(n):
        edge.append([])
    for i in range(n-1):
        abc = list(map(int, input().split()))
        edge[abc[0]-1].append((abc[1]-1, abc[2])) # zero index
        edge[abc[1]-1].append((abc[0]-1, abc[2])) # zero index
    q, k = map(int, input().split())
    k -= 1 # zero index
    xy = []
    for i in range(q):
        xy.append(list(map(int, input().split())))
        xy[-1][0] -= 1 # zero index
        xy[-1][1] -= 1 # zero index

    distance_from_k = []
    visited = []
    for i in range(n):
        distance_from_k.append(0)
        visited.append(False)
    st = [k]
    while st:
        now = st.pop()
        if visited[now]:
            continue
        visited[now] = True
        for x in edge[now]:
            if visited[x[0]]:
                continue
            distance_from_k[x[0]] = distance_from_k[now] + x[1]
            st.append(x[0])

    ans = []
    for i in range(q):
        ans.append(distance_from_k[xy[i][0]] + distance_from_k[xy[i][1]])

    for x in ans:
        print(x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())

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


Q,K=[int(x) for x in input().split()]
dist=[0 for i in range(N+1)]

import heapq
queue=[[K,0]]
heapq.heapify(queue)
while queue:
	#print(queue)
	a=heapq.heappop(queue)
	node=a[0]
	cost=a[1]
	for temp in adj[node]:
		if dist[temp[0]]==0:
			heapq.heappush(queue,[temp[0],temp[1]+cost])
			dist[temp[0]]=cost+temp[1]

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

Submission status: Accepted

Solution code:
N=int(input())
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())
qs=[tuple(map(int,input().split())) for _ in range(Q)]


#DFS
stack=[(K,0)]
dist=[0]*(N+1)
dist[K]=0
while stack:
    n,c=stack.pop()
    for to,cost in E[n]:
        if dist[to]:
            continue
        dist[to]=c+cost
        stack.append((to,c+cost))

for x,y in qs:
    print(dist[x]+dist[y])

Submission status: Accepted

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

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

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

INF = 10 ** 12
dist = [INF] * N

def dfs(v, p=-1, d=0):
    dist[v] = d
    for nv, c in es[v]:
        if nv == p:
            continue
        dfs(nv, v, d+c)

dfs(K, -1, 0)
for x, y in qs:
    print(dist[x-1]+dist[y-1])

Submission status: Accepted

Solution code:
N = int(input())
edge = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    edge[a-1].append((c, b-1))
    edge[b-1].append((c, a-1))
Q, K = map(int, input().split())
query = [tuple(map(int, input().split())) for _ in range(Q)]

import heapq

def dijkstra_heap(s):
    d = [10**12] * N
    used = [False] * N
    d[s] = 0
    used[s] = True
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist, e)
    while len(edgelist):
        min_edge = heapq.heappop(edgelist)
        if used[min_edge[1]]:
            continue
        v = min_edge[1]
        d[v] = min_edge[0]
        used[v] = True
        for e in edge[v]:
            heapq.heappush(edgelist, (e[0] + d[v], e[1]))
    return d

dist = dijkstra_heap(K-1)
for q in query:
    x, y = q[0], q[1]
    x -= 1
    y -= 1
    print(dist[x] + dist[y])

Submission status: Accepted

Solution code:
N=int(input())
g=[[] for _ in range(N)]
length={}
for _ in range(N-1):
    a,b,c=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    length[(a-1,b-1)]=c
    length[(b-1,a-1)]=c
#print(g)
Q,K=map(int,input().split())
K-=1
from collections import deque
que=deque()
que.append(K)
unvisited=[1]*N
unvisited[K]=0
l=[0]*N
while que:
    v=que.pop()
    for u in g[v]:
        if unvisited[u]:
            l[u]=l[v]+length[(u,v)]
            que.appendleft(u)
            unvisited[u]=0
#print(l)
for i in range(Q):
    x,y=map(int,input().split())
    print(l[y-1]+l[x-1])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
ABC=[map(int,input().split(' ')) for i in range(N-1)]
Q,K =  map(int,input().split(' '))
query = [map(int,input().split(' ')) for i in range(Q)]
tree = [[] for i in range(N+1)]
for a,b,c in ABC:
    tree[b].append((a,c))
    tree[a].append((b,c))
k_shortest = [0]*(N+1)
stack=deque([K])
while stack:
    k = stack.popleft()
    for v,d in tree[k]:
        if k_shortest[v] == 0:
            k_shortest[v] = k_shortest[k]+d
            stack.append(v)
for i,j in query:
    print(k_shortest[i]+k_shortest[j])

Submission status: Accepted

Solution code:
from collections import deque

def dfs(graph, start, n):
    stack = deque()
    push, pop = stack.append, stack.pop
    inf = float('INF')
    costs = [inf for i in range(n)]
    visited = [False] * n
    push((start, 0))
    visited[start] = True
    costs[start] = 0

    while stack:
        a,c = pop()
        for b,cc in graph[a].items():
            if visited[b]:
                continue
            if cc + c < costs[b]:
                push((b, cc+c))
                visited[b] = True
                costs[b] = cc + c
    return costs

n = int(input())
graph = {}
for i in range(n-1):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    if a not in graph:
        graph[a] = {}
    if b not in graph:
        graph[b] = {}
    graph[a][b] = graph[b][a] = c

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

Submission status: Accepted

Solution code:
# ABC070 D - Transit Tree Path
import heapq
def dijkstra_heap(s):
    """
    始点sから各頂点への最短距離を返す

    Parameters
    ----------
    s : int
        視点とする頂点

    Returns
    -------
    d ：list
    始点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[0]]:
            continue
        v = minedge[0]
        d[v] = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[0]]:
                heapq.heappush(edgelist,[e[0],e[1]+d[v]])
    return d

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

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

Submission status: Accepted

Solution code:
import sys

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())
dist = [0] * N
sys.setrecursionlimit(2 * N)
def rec(v, pred, d):
    dist[v] = d
    for u, c in E[v]:
        if u == pred:
            continue
        rec(u, v, d + c)
rec(K-1, -1, 0)
ans = [0] * Q
for i in range(Q):
    x, y = map(int, input().split())
    ans[i] = dist[x-1] + dist[y-1]

[print(a) for a in ans]

Submission status: Accepted

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

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

def calcurate_cost(fr, to, cost):
  cost_from_k[to] += cost_from_k[fr]+cost
  for n_to, n_cost in tree[to]:
    if n_to == fr:
      continue
    if K != n_to:
      calcurate_cost(to, n_to, n_cost)
      
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
calcurate_cost(K, K, 0)

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

Submission status: Accepted

Solution code:
from collections import deque

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())
distance = [0] * N
stack = deque([K-1])
# checked = [False] * N
while stack:
    v = stack.pop()
    for u, c in E[v]:
        if distance[u] != 0:
            continue
        distance[u] = distance[v] + c
        stack.append(u)
    # checked[v] = True

ans = [0] * Q
for i in range(Q):
    x, y = map(int, input().split())
    ans[i] = distance[x-1] + distance[y-1]

[print(a) for a in ans]

Submission status: Accepted

Solution code:
from collections import deque

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())
distance = [0] * N
stack = deque([K-1])
checked = [False] * N
while stack:
    v = stack.pop()
    for u, c in E[v]:
        if checked[u]:
            continue
        distance[u] = distance[v] + c
        stack.append(u)
    checked[v] = True

ans = [0] * Q
for i in range(Q):
    x, y = map(int, input().split())
    ans[i] = distance[x-1] + distance[y-1]

[print(a) for a in ans]

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
n = int(input())
m = {}
np = [deque([]) for _ in range(n)]
for _ in range(n-1):
    a, b, c = [int(x) for x in input().strip().split()]
    m[(a, b)] = c
    m[(b, a)] = c
    np[a-1].append(b)
    np[b-1].append(a)

q, k = [int(x) for x in input().strip().split()]
master = [-1 for _ in range(n)]
master[k-1] = 0

def dfs(cur, pre, master):
    #print('cur = {}, pre = {}'.format(cur, pre))
    for p in np[cur-1]:
        if p == pre:
            continue
        master[p-1] = master[cur-1] + m[(cur, p)]
        dfs(p, cur, master)

dfs(k, -1, master)

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

Submission status: Accepted

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

def search_unseen(fr,to,cost):  
  cost_from_k[to] += cost_from_k[fr] + cost
  for n_to,n_cost in es[to]:
    if cost_from_k[n_to] == 0 and k!=n_to:
      search_unseen(to, n_to, n_cost)

n = int(input())
es = {i:[] for i in range(n)}
for i in range(n-1):
  a,b,c = map(int,input().split())
  es[a-1].append((b-1,c))
  es[b-1].append((a-1,c))      
      
q,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(q)]
k -=1

cost_from_k = [0]*n      
search_unseen(k, k, 0)

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

L = [[int(v) for v in input().split()] for _ in range(N - 1)]
Q, K = map(int, input().split())
QL = [[int(v) for v in input().split()] for _ in range(Q)]

m = {}
l = [set() for _ in range(N)]
for a, b, c in L:
    a -= 1
    b -= 1
    if m.get(a) == None:
        m[a] = {}
    if m.get(b) == None:
        m[b] = {}

    m[a][b] = c
    m[b][a] = c

    l[a].add(b)
    l[b].add(a)

ans = [None] * N
ans[K - 1] = 0
def dfs(now, a):
    for v in l[now]:
        p = a + m[now][v]
        if ans[v] == None:
            ans[v] = p
            dfs(v, ans[v])
        elif ans[v] > p:
            ans[v] = p
            dfs(v, ans[v])

dfs(K - 1, 0)
for x, y in QL:
    print(ans[x - 1] + ans[y - 1])

Submission status: Accepted

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

def dfs(v, d=0):
    seen[v] = True
    dist[v] = d

    for i in graph[v]:
        next_v = i[0]
        l = i[1]
        if seen[next_v] == True:
            continue
        dfs(next_v, d+l)

    return

N = int(input())

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

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

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

seen = [False for i in range(N + 1)]
dist = [0 for i in range(N + 1)]
dfs(K)

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