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 heapq
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] += [[b, c]]
  graph[b] += [[a, c]]

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

def dijkstra(s):
  dist = [float('inf')]*N
  dist[s] = 0
  num = [0]*N
  num[s] = 1
  q = [[0, s]]
  heapq.heapify(q)
  while q:
    c, u = heapq.heappop(q)
    if dist[u] < c:
      continue
    for v, weight in graph[u]:
      if dist[v] > dist[u] + weight:
        dist[v] = dist[u] + weight
        num[v] = num[u]
        heapq.heappush(q, [dist[v], v])
      elif dist[v] == dist[u] + weight:
        num[v] += num[u]
  return dist, num

dist, _ = dijkstra(K-1)

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

from collections import deque
from heapq import heappop, heappush
def main():
        

    def dijkstra(k):
        def push(v, x):
            if dist[v] <= x:
                return
            dist[v] = x
            heappush(q, (x, v))

        inf = 10**18
        dist = [inf]*n
        q = []
        push(k, 0)
        while q:
            x, v = heappop(q)
            if x > dist[v]:
                continue
            for nv, c in g[v]:
                push(nv, x+c)
        return dist

    n = ii()
    g = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b, c = mi()
        a -= 1
        b -= 1

        g[a].append((b, c))
        g[b].append((a, c))
    q, k = mi()
    k -= 1
    dist = dijkstra(k)
    for i in range(q):
        a, b = mi()
        a -= 1
        b -= 1
        print(dist[a]+dist[b])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

length=[-1]*(N+1)
length[K]=0

import heapq
q=[[tmp[1], tmp[0], K] for tmp in links[K]]
heapq.heapify(q)
while q:
  tmp=heapq.heappop(q)
  length[tmp[1]]=tmp[0]+0
  for x in links[tmp[1]]:
    if tmp[2]!=x[0]:
      heapq.heappush(q, [tmp[0]+x[1], x[0], tmp[1]])

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

Submission status: Accepted

Solution code:
from collections import deque
def bfs(start, g, visited):
    q = deque([])
    k_neibs = g[start]
    visited[start] = (0,start)
    for neib, dist in k_neibs:
        q.append((neib, neib)) # node, root parent (k neib)
        visited[neib] = (dist, neib) # dist, root parent (k neib)

    while q:
        curr_node, root_pare = q.popleft()
        for next_node, dist in g[curr_node]:
            if visited[next_node] != (-1,-1): continue
            curr_dist = visited[curr_node][0]
            visited[next_node] = (curr_dist+dist, root_pare)
            q.append((next_node, root_pare))


def main():
    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())
    visited = [(-1,-1)] * (n+1) # dist, root parent (k neib)
    bfs(k, g, visited)

    ansl = []
    for _ in range(q):
        x,y = map(int, input().split())
        xd, xp = visited[x]
        yd, yp = visited[y]
        # めっちゃ無駄なことしてたーーーーーーーー！
        if xp == yp:
            ans = xd+yd
            ansl.append(ans)
        else:
            ans = xd+yd
            ansl.append(ans)

    for a in ansl: print(a)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

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

for _ in range(N-1):
    a,b,c=list(map(int,input().split()))
    tree[a].append([b,c])
    tree[b].append([a,c])
Q,K=list(map(int,input().split()))
    
memo = [-1]*(N+1)
q = collections.deque([K])
memo[K]=0
while q:
    now = q.pop()
    for direct,cost in tree[now]:
        if memo[direct]== -1:
            memo[direct]=memo[now]+cost
            q.append(direct)
for _ in range(Q):
    a,b=map(int,input().split())
    ans =memo[a]+memo[b]
    print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    G = [[] for _ in range(N)] 
    for _ in range(N - 1):
        a, b, c = LI()
        G[a-1].append((b - 1, c))
        G[b-1].append((a - 1, c))
    Q, K = LI()
    K -= 1

    dist = [-1] * N
    dist[K] = 0
    que = collections.deque()
    que.append(K)
    while que:
        c = que.popleft()
        for n, l in G[c]:
            if dist[n] == -1:
                dist[n] = dist[c] + l
                que.append(n)

    for _ in range(Q):
        x, y = LI_()
        ans = dist[x] + dist[y]
        print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200000)

n = int(input())
l = [list(map(int,input().split())) for _ in range(n-1)]
q,k = map(int,input().split())
k -= 1
#kからの距離
tree = [[] for _ in range(n)]
for a,b,c in l:
    a -= 1
    b -= 1
    tree[a].append([b,c])
    tree[b].append([a,c])

bit = [0 for _ in range(n)]
depth = [0 for _ in range(n)]
def dfs(v,d=0):
    bit[v] = 1
    depth[v] = d
    for j,k in tree[v]:
        if bit[j]==0:
            dfs(j,d+k)
dfs(k)

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

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
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())
K -= 1

def dijkstra(start):
    dist = [INF for _ in range(N)]
    visited = [False for _ in range(N)] 
    q = [(0, start)]
    dist[start] = 0
    while len(q) > 0:
        v = heapq.heappop(q)
        a = v[1]
        if visited[a]:
            continue
        visited[a] = True
        for u in adj[a]:
            w = u[0]
            b = u[1]
            if dist[a] + w < dist[b]: 
                dist[b] = dist[a] + w
                heapq.heappush(q, (dist[b], b))
    return dist

dist = dijkstra(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:
from collections import deque

N=int(input())
G=[{} for _ in range(N+1)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  G[a][b]=G[b][a]=c
  
def bfs(s):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    cross = []
    todo = deque()
    seen[s]=1
    todo.append(s)
    while 1:
      if len(todo)==0:break
      a = todo.popleft()
      for b in G[a].keys():
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + G[a][b]
    return d

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

Submission status: Accepted

Solution code:
n = int(raw_input())
import collections
adj = collections.defaultdict(list)
for _ in range(n-1):
	u,v,w = map(int,raw_input().split())
	adj[u].append((v,w))
	adj[v].append((u,w))

dist =  {}
qq,k = map(int, raw_input().split())
vis = set([])
q = collections.deque([(k,0)])
while(q):
	u, c = q.popleft()
	dist[u]  = c
	for v,w in adj[u]:
		if v not in vis: 
			vis.add(v)
			q.append((v,w+c))
for _ in range(qq):
	u,v = map(int, raw_input().split())
	print dist[u] + dist[v]

Submission status: Accepted

Solution code:
import sys

def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a]+=[(b,c)]
    roots[b]+=[(a,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack.append(i)
  return dist
      
      
a = []
edge = []
for l in sys.stdin:
    a.append(l.split())
V = int(a[0][0])
for i in range(V-1):
  buf = [int(a[i+1][0])-1, int(a[i+1][1])-1, int(a[i+1][2])]
  edge.append(buf)
n = int(a[V][0])
s = int(a[V][1])-1
ques = []
for i in range(n):
  buf = [int(a[V+i+1][0])-1, int(a[V+i+1][1])-1]
  ques.append(buf)
dist = BFS(s, edge, V)
for a, b in ques:
  res = dist[a] + dist[b]
  print(res)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

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

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
maps = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = lr()
    maps[a-1].append([b-1,c])
    maps[b-1].append([a-1,c])
Q,k  = lr()
k-=1
ans = [inf for i in range(n)]
visited = [False for i in range(n)]
visited[k] = True
q = [[k,0]]
q = deque(q)

while q:
    nown, dist = q.popleft()
    for nn, d in maps[nown]:
        if visited[nn] == False:
            ans[nn] = min(ans[nn], dist+d)
            q.append([nn, dist+d])
            visited[nn] = True
for i in range(Q):
    x,y = lr()
    x-=1
    y-=1
    print(ans[x]+ans[y])

Submission status: Accepted

Solution code:
import collections

n = int(input())
route = {i + 1 : {} for i in range(n)}
for i in range(n - 1):
    a, b, c = map(int, input().split())
    route[a][b] = c
    route[b][a] = c
q, k = map(int, input().split())
queue = collections.deque([k])
length = [0] * (n + 1)
while queue:
    search = queue.popleft()
    pairs = []
    for i, j in route[search].items():
        queue.append(i)
        length[i] = length[search] + j
        pairs.append([search, i])
    for i, j in pairs:
        del route[i][j]
        del route[j][i]
for i in range(q):
    x, y = map(int, input().split())
    print(length[x] + length[y])

Submission status: Accepted

Solution code:
import sys
from math import log2
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10**6)


def main():
    """
    Kの指定があるのに気づかずダブリングでLCA求めちゃった・・・！
    https://algo-logic.info/lca/
    勉強になったから良しとする。ポイントとして
    1. parents[k][u]の求め方がまず再帰
    2. LCAでまず深さを揃えるとこも2べき（必ずfor文はint(log2(N))まで回すこと！）
    3. ダブリングは祖先が一致しない時だけ更新
    を押さえとけば自力で再現できそう？
    """
    N = int(input())
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b, c = map(int, input().split())
        repn[a - 1].append((b - 1, c))
        repn[b - 1].append((a - 1, c))
    depth = [-1] * N
    dist = [0] * N
    parents = [[-1] * N for _ in range(int(log2(N)) + 3)]  # parents[k][u] = (頂点uから2^k先の祖先)

    def dfs(u):
        for v, c in repn[u]:
            if depth[v] != -1: continue
            depth[v] = depth[u] + 1
            dist[v] = dist[u] + c
            parents[0][v] = u
            dfs(v)

    depth[0] = 0
    dfs(0)

    for k in range(int(log2(N)) + 2):
        for u in range(N):
            if parents[k][u] < 0:
                parents[k + 1][u] = -1
            else:
                parents[k + 1][u] = parents[k][parents[k][u]]

    def doubling(u, v):
        if depth[u] < depth[v]: u, v = v, u
        for k in range(int(log2(N)) + 1):
            if ((depth[u] - depth[v]) & (1 << k)):
                u = parents[k][u]
                k += 1
        if u == v: return u
        for k in range(int(log2(N)) + 1, -1, -1):
            if parents[k][u] != parents[k][v]:
                u = parents[k][u]
                v = parents[k][v]
        return parents[0][u]

    Q, K = map(int, input().split())
    for _ in range(Q):
        u, v = map(int, input().split())
        lca1 = doubling(u - 1, K - 1)
        lca2 = doubling(K - 1, v - 1)
        d1 = dist[u - 1] + dist[K - 1] - dist[lca1] * 2
        d2 = dist[K - 1] + dist[v - 1] - dist[lca2] * 2
        print(d1 + d2)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc070/tasks/abc070_d

# 都度のクエリーに答えていると時間が足りない。
# 必ずKを通過すると決まっているので、各頂点とKの距離を
# 事前に計算しておく。O(V + E)

from heapq import heappush, heappop
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((c, b))
    graph[b].append((c, a))
q, k = map(int, input().split())
queries = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    queries.append((x, y))


def dijkstra_with_heap(graph, start, v):
    distance = [float('infinity')] * v
    distance[start] = 0
    stack = [[0, start]] # cost, vertex
    while stack:
        _, vertex = heappop(stack)
        edges = graph[vertex]
        for d, t in edges:
            if d + distance[vertex] < distance[t]:
                distance[t] = d + distance[vertex]
                heappush(stack, (d, t))
    return distance


distance = dijkstra_with_heap(graph, k - 1, n)

for x, y in queries:
    ans = distance[x] + distance[y]
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    G = defaultdict(list)
    for _ in range(N-1):
        a, b, c = read_ints()
        G[a].append((b, c))
        G[b].append((a, c))
    Q, K = read_ints()

    dist = [0]*(N+1)
    stack = [(None, 0, K)]
    while stack:
        parent, base_d, node = stack.pop()
        for child, d in G[node]:
            if child != parent:
                dist[child] = base_d+d
                stack.append((node, base_d+d, child))

    for _ in range(Q):
        x, y = read_ints()
        print(dist[x]+dist[y])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import networkx as nx

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

G = nx.Graph()

for a, b, c in ABC:
    G.add_edge(a - 1, b - 1, weight=c)

# pred, dist = nx.dijkstra_predecessor_and_distance(G, K - 1)
dist = nx.shortest_path_length(G, K - 1, weight="weight", method="bellman-ford")

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

Submission status: Accepted

Solution code:
import networkx as nx

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

G = nx.Graph()

for a, b, c in ABC:
    G.add_edge(a - 1, b - 1, weight=c)

# pred, dist = nx.dijkstra_predecessor_and_distance(G, K - 1)
dist = nx.shortest_path_length(G, K - 1, weight='weight')

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

Submission status: Accepted

Solution code:
import networkx as nx

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

G = nx.Graph()

for a, b, c in ABC:
    G.add_edge(a - 1, b - 1, weight=c)

pred, dist = nx.dijkstra_predecessor_and_distance(G, K - 1)

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

Submission status: Accepted

Solution code:
import sys
import os
from collections import defaultdict
adj = defaultdict(list)
vis =[0 for i in range(1000000)]
dis =[0 for i in range(1000000)]
# since it's a tree shortest path will be only one and unique between two node
# find distance from k to each and every node 
def dfs(u, p):
	for v, w in adj[u]:
		if v==p:
			continue
		dis[v]=dis[u]+w
		dfs(v, u)

def main():
	n = int(input())
	for i in range(n-1):
		a, b, w = map(int , input().split())
		adj[a].append((b, w))
		adj[b].append((a, w))

	q, k = map(int , input().split())
	sys.setrecursionlimit(1000000)
	dfs(k , 0)
	for i in range(q):
		x, y  =map(int , input().split())
		# print the sum of the two distance from k 
		print(dis[x]+dis[y])
#	rec_limit= sys.getrecursionlimit()
#	print(rec_limit)


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
import os
from collections import defaultdict
adj = defaultdict(list)
vis =[0 for i in range(1000000)]
dis =[0 for i in range(1000000)]
def dfs(u, p):
	for v, w in adj[u]:
		if v==p:
			continue
		dis[v]=dis[u]+w
		dfs(v, u)

def main():
	n = int(input())
	for i in range(n-1):
		a, b, w = map(int , input().split())
		adj[a].append((b, w))
		adj[b].append((a, w))

	q, k = map(int , input().split())
	sys.setrecursionlimit(1000000)
	dfs(k , 0)
	for i in range(q):
		x, y  =map(int , input().split())
		print(dis[x]+dis[y])
#	rec_limit= sys.getrecursionlimit()
#	print(rec_limit)


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N=int(input())
l=[-1]*N
tree=[[] for i in range(N)]
for i in range(N-1):
   A,B,C=list(map(int,input().split()))
   A-=1;B-=1
   tree[A].append((B,C))
   tree[B].append((A,C))
Q,V=list(map(int,input().split()))
def DFS(now,past,dis):
   l[now]=dis
   for i in tree[now]:
      if i[0]==past:
         continue
      elif l[i[0]] == -1:
         DFS(i[0],now,dis+i[1])
DFS(V-1,-1,0)
for i in range(Q):
   s,e=list(map(int,input().split()))
   s-=1;e-=1
   print(l[s]+l[e])

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict
    from heapq import heappop, heappush
    N = int(input())
    edge = defaultdict(list)
    length = defaultdict(lambda : defaultdict(lambda : 10**20))
    
    for i in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        if b<a:
            a,b = b,a
        length[a][b] = c
    Q,K = map(int,input().split())
    K -= 1
    cost = [0]*N
    length[K][K] = 0
    targets = [(0,K)]
    cost = [10**18]*N
    cost[K] = 0
    visited = [False]*N
    while targets:
        c,t = heappop(targets)
        if visited[t]:
            continue
        cost[t] = c
        visited[t] = True
        for v in edge[t]:
            if cost[v] > cost[t] + length[min(t,v)][max(t,v)]:
                heappush(targets,(cost[t] + length[min(t,v)][max(t,v)],v))

    out = []
    for i in range(Q):
        x,y = map(lambda x: int(x)-1, input().split())
        out.append(cost[x]+cost[y])

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







main()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys
finput=lambda: sys.stdin.readline().strip()

def main():
  n=int(finput())
  edges=[tuple(map(int,finput().split())) for _ in range(n-1)]
  q,k=map(int,finput().split())
  xy=[tuple(map(int,finput().split())) for _ in range(q)]
  ed=defaultdict(deque)
  wt=defaultdict(int)
  for e in edges:
    ed[e[0]].append(e[1])
    ed[e[1]].append(e[0])
    wt[(e[0],e[1])]=e[2]
    wt[(e[1],e[0])]=e[2]
  stack=deque([k])
  cv=stack[0]
  dist=defaultdict(int)
  while stack:
    while ed[cv]:
      if cv!=k:
        if ed[cv][-1]==stack[-1]:
          ed[cv].pop()
          if not ed[cv]:
            break
      stack.append(cv)
      cv=ed[cv].pop()
      dist[cv]=dist[stack[-1]]+wt[(stack[-1],cv)]
    cv=stack.pop()
  for que in xy:
    print(dist[que[0]]+dist[que[1]])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:

from collections import defaultdict,deque
import sys
finput=lambda: sys.stdin.readline().strip()

def main():
  n=int(finput())
  edges=[tuple(map(int,finput().split())) for _ in range(n-1)]
  q,k=map(int,finput().split())
  xy=[tuple(map(int,finput().split())) for _ in range(q)]
  
  stack=[-1]*(n+1)
  stack[k]=0
  ed=defaultdict(list)
  wt=defaultdict(int)
  for e in edges:
    ed[e[0]].append(e[1])
    ed[e[1]].append(e[0])
    wt[(e[0],e[1])]=e[2]
    wt[(e[1],e[0])]=e[2]
  ce=deque([(k,x) for x in ed[k]])
  ne=deque()
  while True:
    while ce:
      e=ce.pop()
      stack[e[1]]=stack[e[0]]+wt[e]
      for v in ed[e[1]]:
        if stack[v]<0:
          ne.append((e[1],v))
    if not ne:
      break
    ce.extend(ne)
    ne.clear()
  
  for que in xy:
    print(stack[que[0]]+stack[que[1]])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
n=int(input())
edges=[tuple(map(int,input().split())) for _ in range(n-1)]
q,k=map(int,input().split())
xy=[tuple(map(int,input().split())) for _ in range(q)]

stack=[-1]*(n+1)
stack[k]=0
ed=defaultdict(list)
wt=defaultdict(int)
for e in edges:
  ed[e[0]].append(e[1])
  ed[e[1]].append(e[0])
  wt[(e[0],e[1])]=e[2]
  wt[(e[1],e[0])]=e[2]
ce=deque([(k,x) for x in ed[k]])
ne=deque()
while True:
  while ce:
    e=ce.pop()
    stack[e[1]]=stack[e[0]]+wt[e]
    for v in ed[e[1]]:
      if stack[v]<0:
        ne.append((e[1],v))
  if not ne:
    break
  ce.extend(ne)
  ne.clear()

for que in xy:
  print(stack[que[0]]+stack[que[1]])

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    Q, K, *XY = map(int, read().split())
    K -= 1

    stack = deque([K])
    dist = [INF] * N
    dist[K] = 0
    while stack:
        v = stack.pop()
        for nv, cost in G[v]:
            if dist[nv] == INF:
                dist[nv] = dist[v] + cost
                stack.append(nv)

    ans = [0] * Q
    for i, (x, y) in enumerate(zip(*[iter(XY)] * 2)):
        ans[i] = dist[x - 1] + dist[y - 1]

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    Q, K, *XY = map(int, read().split())
    K -= 1

    hq = [(0, K)]
    dist = [INF] * N
    dist[K] = 0
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for nv, cost in G[v]:
            if dist[nv] > d + cost:
                dist[nv] = d + cost
                heappush(hq, (dist[nv], nv))

    ans = [0] * Q
    for i, (x, y) in enumerate(zip(*[iter(XY)] * 2)):
        ans[i] = dist[x - 1] + dist[y - 1]

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

q, k = map(int, input().split())
ds = [-1]*n
hq = [(0,k-1)]
while hq:
    c,idx = heapq.heappop(hq)
    if ds[idx] != -1:
        continue
    ds[idx] = c
    for i in g[idx]:
        if ds[i[0]] == -1:
            heapq.heappush(hq,(i[1]+c,i[0]))

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

Submission status: Accepted

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

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

check = [False for _ in range(n)]
dist = [0 for _ in range(n)]
def dfs(pos, b_pos):
    for n_pos, c in edges[pos]:
        if n_pos == b_pos:
            continue
        check[n_pos] = True
        dist[n_pos] = c + dist[pos]
        dfs(n_pos, pos)

check[k - 1] = True
dfs(k - 1, -1)

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

N = int(input())
tree = [[] for _ 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] * N
def dfs(v, total_cost):
    # v：頂点, total_cost：今までかかったコストの合計
    dist[v] = total_cost
    for v_next, cost in tree[v]:
        if dist[v_next] >= 0:
            continue
            # v_nextが訪問済みならスキップ
        dfs(v_next, total_cost+cost)

dfs(K-1, 0)

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

def dfs(now_node,parent_node,dist):
  depth[now_node]=dist
  for next_node,w in graph[now_node]:
    if next_node==parent_node:
      continue
    dfs(next_node,now_node,dist+w)

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))
  
q,k=map(int,input().split())
depth=[-1]*(n+1)
dfs(k,0,0)
for _ in range(q):
  x,y=map(int,input().split())
  print(depth[x]+depth[y])

Submission status: Accepted

Solution code:
def abc070_d():
    import sys
    sys.setrecursionlimit(10010010)
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    n = next(inp)
    adjlist = [[] for _ in range(n)]
    for _ in range(n-1):
        a = next(inp) - 1
        b = next(inp) - 1
        c = next(inp)
        adjlist[a].append((b, c))
        adjlist[b].append((a, c))

    q = next(inp)
    k = next(inp) - 1

    dist = [-1] * n

    def dfs(x:int, d:int):
        dist[x] = d
        for nx, nd in adjlist[x]:
            if dist[nx] != -1: continue
            dfs(nx, d + nd)

    dfs(k, 0)

    for _ in range(q):
        x = next(inp) - 1
        y = next(inp) - 1
        ans = dist[x] + dist[y]
        print(ans)

if __name__ == '__main__':
    abc070_d()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(pow(10,6))
readline = sys.stdin.readline

def dfs(nw, d):
    V[nw] = d
    for nx in G[nw]:
        if V[nx[0]]==-1:
            dfs(nx[0], d+nx[1])

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

V = [-1]*n
dfs(k-1, 0)

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