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
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]
from heapq import *

def dfs(s, es):
    dist = [None] * len(es)
    dist[s] = 0
    def ret(v, d):
        for u, c in es[v]:
            if dist[u] == None:
                dist[u] = dist[v] + c
                ret(u, dist[u])
    ret(s, 0)
    return dist
  
N = int(input())
es = [[] for i in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    es[a].append((b, c))
    es[b].append((a, c))
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(Q)]
dist = dfs(K, es)
for i in range(Q):
    print(dist[xy[i][0]] + dist[xy[i][1]])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]
from heapq import *

INF = 10 ** 20
def dijkstra(s, edges):
    dist = [INF for _ in range(len(edges))]
    dist[s], h = 0, []
    heappush(h, (0, s))
    while (len(h)):
        dv, v = heappop(h)
        if dv > dist[v]:
            continue
        for u, cost in edges[v]:
            if dv + cost < dist[u]:
                dist[u] = dv + cost
                heappush(h, (dist[u], u))
    return dist

N = int(input())
es = [[] for i in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    es[a].append((b, c))
    es[b].append((a, c))
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(Q)]
dist = dijkstra(K, es)
for i in range(Q):
    print(dist[xy[i][0]] + dist[xy[i][1]])

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    N = len(V)
    dist = [INF]*N
    heap = []
    heappush(heap, (0, s))
    while heap:
        d, v = heappop(heap)
        # don't need to check when the stored value is greater than provisional distance
        if d > dist[v]:
            continue
        dist[v] = d
        for u, c in E[v].items():
            temp = d + c
            if temp < dist[u]:
                heappush(heap, (temp, u))
    return dist

N = int(input())
V = list(range(N))
E = defaultdict(dict)
for _ in range(N-1):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = c
    E[b-1][a-1] = c
Q, K = map(int, input().split())
dist = dijkstra(V, E, K-1)
for _ in range(Q):
    x, y = map(int, input().split())
    ans = dist[x-1] + dist[y-1]
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def solve(n, a, b, c, q, k, x, y):
    E = {}
    G = {}
    for u, v, d in zip(a, b, c):
        if not u in E:
            E[u] = []
        if not v in E:
            E[v] = []
        E[u].append(v)
        E[v].append(u)
        G[u, v] = d
        G[v, u] = d
    dist = {}
    dist[k] = 0
    que = deque([k])
    while que:
        v = que.pop()
        for u in E[v]:
            if not u in dist:
                dist[u] = dist[v] + G[u,v]
                que.append(u)
    for i in range(q):
        print(dist[x[i]] + dist[y[i]])

n = int(input())
a = [0] * (n-1)
b = [0] * (n-1)
c = [0] * (n-1)
for i in range(n-1):
    a[i], b[i], c[i] = map(int, input().split())
q, k = map(int, input().split())
x = [0] * q
y = [0] * q
for i in range(q):
    x[i], y[i] = map(int, input().split())
solve(n, a, b, c, q, k, x, y)

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

N = int(input())
G = [[] for _ in range(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())
K_to = [[] for _ in range(N + 1)]
visited = [0] * (N + 1)

def dfs(v, p, d):
    K_to[v] = d
    if not visited[p]:
        for to, c  in G[v]:
            if to == p:
                continue
            dfs(to, v, c + d)
    else:
        visited[p] = True
    return

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

Submission status: Accepted

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

input = sys.stdin.readline

N = int(input())

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

dist = [None]*(N+1)

def dfs(now,d) :
    dist[now] = d
    for to,c in T[now] :
        if dist[to] is not None :
            continue
        dfs(to,d+c)

dfs(K,0)

ans = [0]*Q

for i in range(Q) :
    u,v = map(int,input().split())
    ans[i] = dist[u]+dist[v]

print(*ans,sep="\n")

Submission status: Accepted

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

N = int(input())
T = [[] for _ in range(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())

dist = [None]*(N+1)

def dfs(now,d) :
    dist[now] = d
    for to,c in T[now] :
        if dist[to] is not None :
            continue
        dfs(to,d+c)

dfs(K,0)

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

Submission status: Accepted

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

N = int(input())
T = [[] for _ in range(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())

dist = [None]*(N+1)

def dfs(now,d) :
    dist[now] = d
    for to,c in T[now] :
        if dist[to] is not None :
            continue
        dfs(to,d+c)

dfs(K,0)

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

Submission status: Accepted

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

N = int(input())
T = [[] for _ in range(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())

dist = [None]*(N+1)

def dfs(now,d) :
    dist[now] = d
    for to,c in T[now] :
        if dist[to] is not None :
            continue
        dfs(to,d+c)

dfs(K,0)

ans = []

for _ in range(Q) :
    u,v = map(int,input().split())
    ans.append(dist[u]+dist[v])

print(*ans,sep="\n")

Submission status: Accepted

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

N = int(input())
T = [[] for i in range(N+1)]

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

dist = [None]*(N+1)

def dfs(now,d) :
    dist[now] = d
    for to,c in T[now] :
        if dist[to] is not None :
            continue
        dfs(to,d+c)

dfs(K,0)

ans = []

for i in range(Q) :
    u,v = map(int,input().split())
    ans.append(dist[u]+dist[v])

print(*ans,sep="\n")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000001)

N = int(input())
D = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    D[a].append((b, c))
    D[b].append((a, c))
Q, K = map(int, input().split())
DS = [-1] * (N + 2)


def dfs(c, p, d):
    DS[c] = d
    for r in D[c]:
        if r[0] == p:
            continue
        dfs(r[0], c, d + r[1])


def main():
    dfs(K - 1, -1, 0)
    for _ in range(Q):
        x, y = map(int, input().split())
        print(DS[x - 1] + DS[y - 1])


main()

Submission status: Accepted

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

class Tree:
  def __init__(s, N):
    s.D = [-1] * (N + 1)
    s.R = {}
  def setR(s, a, b, c):
    if a in s.R:
      s.R[a].append([b, c])
    else:
      s.R[a] = [[b, c]]
    if b in s.R:
      s.R[b].append([a, c])
    else:
      s.R[b] = [[a, c]]
  def setD(s, x):
    S = [[x, s.R[x]]]
    s.D[x] = 0
    while S:
      y, t = S.pop()
      k = s.D[y]
      for a, d in t:
        if s.D[a] == -1:
          s.D[a] = k + d
          S.append([a, s.R[a]])
  def getD(s, x):
    return s.D[x]

T = Tree(N)
for a, b, c in abc:
  T.setR(a, b, c)
T.setD(K)

for x, y in xy:
  print(T.getD(x) + T.getD(y))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

N = int(input())
g = [[] for _ in range(N)]
for _ 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))

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

Submission status: Accepted

Solution code:
N = int(input())

##########木を作る###########
S = [[]for i in range(N)] 
for i in range(N-1):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])

############クエリを保存#########
Q,K = map(int,input().split())
xy = list(list(map(int,input().split()))for i in range(Q))

len_ = [float('inf')]*N  # Kまでの距離
len_[K-1] = 0 #　K~Kは距離0

#############幅優先探索############
queue = [K-1]
hoge = []
while queue != []:
    for i in queue:
        for b,c in S[i]:
            if len_[b] > len_[i]+c:
                hoge.append(b)
                len_[b] = len_[i]+c
    queue = hoge
    hoge = []

#############x~K,y~Kの距離の和###########
for x,y in xy:
    print(len_[x-1]+len_[y-1])

Submission status: Accepted

Solution code:
N = int(input())
S = [[]for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
Q,K = map(int,input().split())
xy = list(list(map(int,input().split()))for i in range(Q))
len_ = [float('inf')]*N
len_[K-1] = 0
queue = [K-1]
hoge = []
while queue != []:
    for i in queue:
        for b,c in S[i]:
            if len_[b] > len_[i]+c:
                hoge.append(b)
                len_[b] = len_[i]+c
    queue = hoge
    hoge = []
for x,y in xy:
    print(len_[x-1]+len_[y-1])

Submission status: Accepted

Solution code:
N=int(input())
from collections import defaultdict
branch=defaultdict(dict)
for i in range(N-1):
    a,b,c=map(int,input().split())
    branch[a-1][b-1]=c
    branch[b-1][a-1]=c
Q,K=map(int,input().split())
dist=[float('inf')]*N
dist[K-1]=0
check={K-1}
while len(check)>0:
    now=check.pop()
    for nex,d in branch[now].items():
        if dist[nex]>dist[now]+d:
            dist[nex]=dist[now]+d
            check|={nex}
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 defaultdict
from heapq import heappop, heappush

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

graph = defaultdict(set)
for v, w, c in edges:
    graph[v].add((w, c))
    graph[w].add((v, c))

dp = [-1] * (N + 1)
pq = []

# Initialization
dp[K] = 0
heappush(pq, (0, K))

while pq:
    cost, u = heappop(pq)
    
    for w, c in graph[u]:
        if dp[w] > -1:
            continue

        dp[w] = dp[u] + c
        heappush(pq, (dp[w], w))

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

Submission status: Accepted

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


q, k = [ int(v) for v in input().split() ]
k -= 1

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

searching_list = [k]

while searching_list != []:

    new_search_list = []
    for i in searching_list:
        for j in connect_list[i]:
            x, y = j
            if shortest_list[x] == -1:
                shortest_list[x] = y + shortest_list[i]
                new_search_list.append(x)
    searching_list = new_search_list


for i in range(q):
    a, b = [ int(v)-1 for v in input().split() ]
    print(shortest_list[a] + shortest_list[b])

Submission status: Accepted

Solution code:

from collections import defaultdict

import sys
input = sys.stdin.readline

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

    link = defaultdict(set)
    weight = defaultdict(int)
    for i in range(num - 1):
        a, b, c = map(int, input().split())
        link[a].add(b)
        link[b].add(a)
        weight[(min(a, b), max(a, b))] = c

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

    dist_data = [-1 for i in range(num + 1)]
    dist_data[k] = 0
    now_check = set()
    next_check = set()
    now_check.add(k)

    while len(now_check) > 0:
        for ele in now_check:
            now_dist = dist_data[ele]
            for now_ele in link[ele]:
                if dist_data[now_ele] != -1:
                    continue
                next_check.add(now_ele)
                dist_data[now_ele] = now_dist + weight[(min(now_ele, ele), max(now_ele, ele))]
        now_check = next_check
        next_check = set()

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



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from collections import defaultdict


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

    link = defaultdict(set)
    weight = defaultdict(int)
    for i in range(num - 1):
        a, b, c = map(int, input().split())
        link[a].add(b)
        link[b].add(a)
        weight[(min(a, b), max(a, b))] = c

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

    dist_data = [-1 for i in range(num + 1)]
    dist_data[k] = 0
    now_check = set()
    next_check = set()
    now_check.add(k)

    while len(now_check) > 0:
        for ele in now_check:
            now_dist = dist_data[ele]
            for now_ele in link[ele]:
                if dist_data[now_ele] != -1:
                    continue
                next_check.add(now_ele)
                dist_data[now_ele] = now_dist + weight[(min(now_ele, ele), max(now_ele, ele))]
        now_check = next_check
        next_check = set()

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



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappush, heappop
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()
        
class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
N = int(input())
gp = Graph()
for _ in range(N-1):
    s,d,w = [int(x) for x in input().split()]
    gp.add_edge(s-1,d-1,w)
    gp.add_edge(d-1,s-1,w)

Q,K = [int(x) for x in input().split()]
xy = [[int(x) for x in input().split()]for _ in range(Q)]
di = Dijkstra(gp,K-1)
for x,y in xy:
    print(di.shortest_distance(x-1)+di.shortest_distance(y-1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist


n = int(input())
adj = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
q, k = map(int, input().split())
shortest = dijkstra(adj, n, k - 1)
for i in range(q):
    x, y = map(int, input().split())
    print(shortest[x - 1] + shortest[y - 1])

Submission status: Accepted

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


def main():
    from collections import defaultdict
    from collections import deque
    import sys

    n = int(input())
    graph = [defaultdict(int) for _ in range(n)]
    visited = [False for _ in range(n)]
    dist = [float('inf') for _ in range(n)]
    lines = sys.stdin.readlines()

    for i in range(n - 1):
        ai, bi, ci = map(int, lines[i].split())
        ai -= 1
        bi -= 1
        graph[ai][bi] = ci
        graph[bi][ai] = ci

    q, k = map(int, lines[n - 1].split())
    k -= 1
    dist[k] = 0
    d = deque()
    d.append(k)

    while d:
        di = d.popleft()
        visited[di] = True

        for bi, ci in graph[di].items():
            if visited[bi]:
                continue

            dist[bi] = dist[di] + ci
            d.append(bi)

    ans = [0 for _ in range(q)]

    for j in range(q):
        xi, yi = map(int, lines[n + j].split())
        xi -= 1
        yi -= 1
        ans[j] = dist[xi] + dist[yi]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    from collections import defaultdict
    from collections import deque

    n = int(input())
    graph = [defaultdict(int) for _ in range(n)]
    visited = [False for _ in range(n)]
    dist = [float('inf') for _ in range(n)]

    for i in range(n - 1):
        ai, bi, ci = map(int, input().split())
        ai -= 1
        bi -= 1
        graph[ai][bi] = ci
        graph[bi][ai] = ci

    q, k = map(int, input().split())
    k -= 1
    dist[k] = 0
    d = deque()
    d.append(k)

    while d:
        di = d.popleft()
        visited[di] = True

        for bi, ci in graph[di].items():
            if visited[bi]:
                continue

            dist[bi] = dist[di] + ci
            d.append(bi)

    ans = [0 for _ in range(q)]

    for j in range(q):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1
        ans[j] = dist[xi] + dist[yi]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    from collections import defaultdict
    from collections import deque

    n = int(input())
    graph = [defaultdict(int) for _ in range(n)]
    visited = [False for _ in range(n)]
    dist = [0 for _ in range(n)]

    for i in range(n - 1):
        ai, bi, ci = map(int, input().split())
        ai -= 1
        bi -= 1
        graph[ai][bi] = ci
        graph[bi][ai] = ci

    q, k = map(int, input().split())
    k -= 1
    dist[k] = 0
    d = deque()
    d.append(k)

    while d:
        di = d.popleft()
        visited[di] = True

        for bi, ci in graph[di].items():
            if visited[bi]:
                continue

            dist[bi] = dist[di] + ci
            d.append(bi)

    for j in range(q):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1
        print(dist[xi] + dist[yi])


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    from collections import defaultdict
    from collections import deque

    n = int(input())
    graph = [defaultdict(int) for _ in range(n)]
    visited = [False for _ in range(n)]
    dist = [float('inf') for _ in range(n)]

    for i in range(n - 1):
        ai, bi, ci = map(int, input().split())
        ai -= 1
        bi -= 1
        graph[ai][bi] = ci
        graph[bi][ai] = ci

    q, k = map(int, input().split())
    k -= 1
    dist[k] = 0
    d = deque()
    d.append(k)

    while d:
        di = d.popleft()
        visited[di] = True

        for bi, ci in graph[di].items():
            if visited[bi]:
                continue

            dist[bi] = dist[di] + ci
            d.append(bi)

    for j in range(q):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1
        print(dist[xi] + dist[yi])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

n = int(input())
edges = {}
dist = {}
con = {}

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

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

dist[k] = 0
frontier = [k]
while len(dist.keys()) != n:
  frontier_new = []
  for f in frontier:
    for neigh in con[f]:
      if con[f][neigh]:
        dist[neigh] = dist[f] + edges[frozenset([neigh, f])]
        frontier_new.append(neigh)
        con[f][neigh] = False
        con[neigh][f] = False
  frontier = frontier_new[:]

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

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
def dijkstra(s):
    d = [float("inf")]*n
    used = [True]*n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heappush(edgelist,e)
    while len(edgelist):
        short_edge = heappop(edgelist)
        if not used[short_edge[1]]:
            continue
        v = short_edge[1]
        d[v] = short_edge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                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):
    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()) 
d = dijkstra(k-1)
for i in range(q):
    x,y = map(int,input().split())
    print(d[x-1]+d[y-1])

Submission status: Accepted

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

sys.setrecursionlimit(300000)

def dfs(idx, visited, conn, d, cur):
    visited[idx] = True
    for nex in conn[idx]:
        if not visited[nex[0]]:
            d[nex[0]] = cur + nex[1]
            d = dfs(nex[0], visited, conn, d, cur + nex[1])
    return d


def solve(N: int, A: "List[int]", B: "List[int]", C: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):

    conn = [[] for _ in range(N)]
    for j in range(N - 1):
        a = A[j] - 1
        b = B[j] - 1
        conn[a].append([b, C[j]])
        conn[b].append([a, C[j]])
    visited = [False] * N
    d = [0] * N
    d = dfs(K - 1, visited, conn, d, 0)
    for q in range(Q):
        s = x[q] - 1
        t = y[q] - 1
        ret = d[s] + d[t]
        print(ret)
    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())
g=[[] for i in range(1+n)]
v=[0]*(1+n)
dist=[0]*(1+n)
for i in range(n-1):
    a,b,c=map(int,input().split())
    g[a].append([b,c])
    g[b].append([a,c])

def dfs(p):  # p = [node, 0]
    while p:
        cur, depth=p.pop()
        v[cur]=1
        dist[cur]=depth
        for nb in g[cur]:
            if v[nb[0]]==0:
                p.append([nb[0],depth+nb[1]])
    return

q,k=map(int,input().split())
dfs([[k,0]])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs(l,d,k):
  for i in l[k]:
    if d[i[0]]==-1:
      d[i[0]]=d[k]+i[1]
      dfs(l,d,i[0])

n=int(input())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  l[a-1].append([b-1,c])
  l[b-1].append([a-1,c])
q,k=map(int,input().split())
d=[-1 for i in range(n)]
d[k-1]=0
dfs(l,d,k-1)
L=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  print(d[L[i][0]-1]+d[L[i][1]-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N=int(input())

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

Q,K=map(int,input().split())
MP=[-1]*(N+1)
MP[K]=0
def dfs(k):
    for i, c in NODES[k]:
        if MP[i] == -1:
            MP[i] = MP[k] + c
            dfs(i)

dfs(K)
# print(MP)
for l,r in [tuple(map(int,input().split())) for _ in range(Q)]:
    print(MP[l]+MP[r])

Submission status: Accepted

Solution code:
import sys
from collections import deque

N=input()

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

Q,K=map(int, sys.stdin.readline().split())

question=[ map(int, sys.stdin.readline().split())  for i in range(Q) ] 

Visit=[ None for i in range(N+1) ] 
Visit[K]=0

q=deque()
q.append(K)


while q:
	fro=q.popleft()
	for to,cost in nl[fro]:
		if Visit[to] is None:
			Visit[to]=Visit[fro]+cost
			q.append(to)


for x, y in question:
	print Visit[x]+Visit[y]

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
List = [[] for _ in range(N)]
ans = [-1]*N
for i in range(N-1):
    a, b, c = map(int, input().split())
    List[a-1].append((b-1, c))
    List[b-1].append((a-1, c))
Q, K = map(int, input().split())
queue = [K-1]
ans[K-1] = 0
while queue:
    edge = queue.pop()
    for node in List[edge]:
        index, cost = node
        if ans[index]>0:
            continue
        ans[index] = ans[edge]+cost
        queue.append(index)
for i in range(Q):
    x, y = map(int, input().split())
    print(ans[x-1]+ans[y-1])

Submission status: Accepted

Solution code:
import collections
N = int(input())
List = [[] for _ in range(N)]
ans = [-1]*N
for i in range(N-1):
    a, b, c = map(int, input().split())
    List[a-1].append((b-1, c))
    List[b-1].append((a-1, c))
Q, K = map(int, input().split())
queue = collections.deque([K-1])
ans[K-1] = 0
while queue:
    edge = queue.pop()
    for node in List[edge]:
        index, cost = node
        if ans[index]>0:
            continue
        ans[index] = ans[edge]+cost
        queue.append(index)
for i in range(Q):
    x, y = map(int, input().split())
    print(ans[x-1]+ans[y-1])

Submission status: Accepted

Solution code:
N = int(input())
List = [[] for _ in range(N)]
ans = [-1]*N
for i in range(N-1):
    a, b, c = map(int, input().split())
    List[a-1].append((b-1, c))
    List[b-1].append((a-1, c))
Q, K = map(int, input().split())
queue = [K-1]
ans[K-1] = 0
while queue:
    edge = queue.pop()
    for node in List[edge]:
        index, cost = node
        if ans[index]>0:
            continue
        ans[index] = ans[edge]+cost
        queue.append(index)
for i in range(Q):
    x, y = map(int, input().split())
    print(ans[x-1]+ans[y-1])