Problem:


Score : 400 points

Problem Statement

You are given a tree with N vertices.

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

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

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

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

Constraints

3≤N≤10^5 

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

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

The given graph is a tree.

1≤Q≤10^5 

1≤K≤N 

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

x_j≠y_j (1≤j≤Q) 

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

Input

Input is given from Standard Input in the following format:  

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

Output

Print the responses to the queries in Q lines.

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

Sample Input 1

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

Sample Output 1

3
2
4

The shortest paths for the three queries are as follows:

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

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

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

Sample Input 2

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

Sample Output 2

5
14
22

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

Sample Input 3

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

Sample Output 3

17000000000



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


Sample output:
3
2
4

Submission status: Accepted

Solution code:
from collections import deque
n,*t=map(int,open(0).read().split())
con=[[] for _ in range(n)]
dist_f_k=[0]*n

for a,b,c in zip(t[:3*n-3:3],t[1::3],t[2::3]):
	con[a-1].append((b-1,c))
	con[b-1].append((a-1,c))

k=t[3*n-2]
que=deque([k-1])
while que:
	cur=que.popleft()
	for nxt,dd in con[cur]:
		if dist_f_k[nxt]==0 and nxt!=k-1:
			que.append(nxt)
			dist_f_k[nxt]=dist_f_k[cur]+dd

for x,y in zip(t[3*n-1::2],t[3*n::2]):
	print(dist_f_k[x-1]+dist_f_k[y-1])

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
con=[[] for _ in range(n)]
dist_f_k=[0]*n

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

q,k=map(int,input().split())
que=deque([k-1])
while que:
	cur=que.popleft()
	for nxt,dd in con[cur]:
		if dist_f_k[nxt]==0 and nxt!=k-1:
			que.append(nxt)
			dist_f_k[nxt]=dist_f_k[cur]+dd

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

Submission status: Accepted

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


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


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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    from collections import defaultdict
    D = defaultdict(list)
    for i in range(N-1):
        a,b,c = map(int,input().split())
        D[a].append([b,c])
        D[b].append([a,c])
        
    Q,K = map(int,input().split())
    fromK = [[0] for i in range(N+1)]
    
    visited = {}
    queue = [[K,0]]
    while queue != []:
        v,C = queue.pop()
        visited[v] = 1
        fromK[v] = C
        for i in D[v]:
            j,c = i
            if not j in visited:
                queue.append([j,C+c])
    for i in range(Q):
        x,y = map(int,input().split())
        print(fromK[x]+fromK[y])
    
    
main()

Submission status: Accepted

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

N = int(input())
E = [set() for _ in range(N)]
C = {}
for i in range(N-1):
  a,b,c = map(int,input().split())
  E[a-1].add(b-1)
  E[b-1].add(a-1)
  C[min(a-1,b-1)*N+max(a-1,b-1)] = c
  
Q,K = map(int,input().split())
K -= 1
#print(E)
#print(C)
#print(K)

Kcost = [0 for _ in range(N)]
def dfs(u,v):
  if v != -1:
    Kcost[u] = Kcost[v] + C[min(u,v)*N+max(u,v)]
  for t in E[u]:
    if t != K and Kcost[t] == 0:
      dfs(t,u)
dfs(K,-1)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

N=int(input())
dp = [0]*N

E = []
for i in range(N):
    E.append([])

def dfs(cur,pre):
    for r,d in E[cur]:
        if r != pre:
            dp[r] = dp[cur] + d
            dfs(r,cur)


for i in range(N-1):
    x,y,d= list(map(int,input().split()))
    E[x-1].append((y-1,d))
    E[y-1].append((x-1,d))

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

dfs(K-1,-1)

for j in range(Q):
    s,g= list(map(int,input().split()))
    print(dp[s-1]+dp[g-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100002)
input=sys.stdin.readline
n=int(input())
graph=[{} for i in range(n)]
visited=[False]*n
for i 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())
dist=[0]*n
def dfs(chi,par,cost):
    dist[chi]=cost
    for i in graph[chi].keys():
        if visited[i]:continue
        if i==par:continue
        visited[i]=True
        dfs(i,chi,cost+graph[i][chi])
    return
dfs(k-1,-1,0)
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
sys.setrecursionlimit(1000000)

N = int(input())

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

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

visited = [False] * N
visited[K-1] = True

distance = [-1]*N


def dfs(v, p, d):  # 現在の頂点v, vの親p, 現在の距離d
    distance[v-1] = d
    for i, c in G[v-1]:
        if visited[i-1] is False:
            if i == p:
                continue
            dfs(i, v, d+c)
    return


dfs(K, -1, 0)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    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())
    k-=1
    d=[INF]*n
    d[k]=0

    # dfs (root=k)
    Q=[[k,0]]
    while(Q):
        v,dist=Q.pop()
        for u,cost in edges[v]:
            if d[u]>dist+cost:
                d[u]=dist+cost
                Q.append([u,d[u]])

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

resolve()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

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

visited = [False] * N
visited[K-1] = True

distance = [-1]*N

que = deque([(K, 0)])
while que:
    cur, d = que.popleft()
    distance[cur-1] = d

    for nx, nd in G[cur-1]:
        if visited[nx-1] is False:
            visited[nx-1] = True
            que.append((nx, d+nd))

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(200000)
input = sys.stdin.readline

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

m = [set() for _ in range(N)]
c = {}
for x, y, z in L:
    m[x - 1].add(y - 1)
    m[y - 1].add(x - 1)

    if c.get(x - 1) == None:
        c[x - 1] = {}

    if c.get(y - 1) == None:
        c[y - 1] = {}

    c[x - 1][y - 1] = z
    c[y - 1][x - 1] = z

s = [None] * N
s[K - 1] = 0

def f(index, b):
    for v in m[index]:
        if s[v] == None:
            s[v] = b + c[index][v]
            f(v, s[v])
        else:
            if s[v] > b + c[index][v]:
                s[v] = b + c[index][v]
                f(v, s[v])

f(K - 1, 0)

for x, y in QL:
    print(s[x] + s[y])

Submission status: Accepted

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


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

dis=[None]*(n+1)

def set_dis(x,d):
    dis[x]=d
    for yy,dd in graph[x] :
        if dis[yy] is not None:
            continue
        set_dis(yy,dd+d)
set_dis(k,0)

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
def main():
  def p(a,b):
    if a < b:
      return (a,b)
    else:
      return (b,a)
  input = sys.stdin.readline
  N = int(input())
  E = [[] for i in range(N)]
  C = {}
  D = [0] * N
  parent = [0]*N
  for i in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    C[p(a,b)] = c

  M, K = map(int, input().split())
  K -= 1
  parent[K] = K
  Q = deque()
  Q.append(K)

  while Q:
    u = Q.popleft()
    d = D[u]
    for v in E[u]:
      if parent[u] == v:
        continue
      parent[v] = u
      D[v] = d + C[p(u,v)]
      Q.append(v)

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

main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
  def p(a,b):
    if a < b:
      return (a,b)
    else:
      return (b,a)
  input = open(0).readline
  N = int(input())
  E = [[] for i in range(N)]
  C = {}
  D = [0] * N
  parent = [0]*N
  for i in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    C[(a,b)] = c
    C[(b,a)] = c

  M, K = map(int, input().split())
  K -= 1
  parent[K] = K
  Q = deque()
  Q.append(K)

  while Q:
    u = Q.popleft()
    d = D[u]
    for v in E[u]:
      if parent[u] == v:
        continue
      parent[v] = u
      D[v] = d + C[(u,v)]
      Q.append(v)

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

main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
  def p(a,b):
    if a < b:
      return (a,b)
    else:
      return (b,a)
  #input = open(0).readline
  N = int(input())
  E = [[] for i in range(N)]
  C = {}
  D = [0] * N
  parent = [0]*N
  for i in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    C[p(a,b)] = c

  M, K = map(int, input().split())
  K -= 1
  parent[K] = K
  Q = deque()
  Q.append(K)

  while Q:
    u = Q.popleft()
    d = D[u]
    for v in E[u]:
      if parent[u] == v:
        continue
      parent[v] = u
      D[v] = d + C[p(u,v)]
      Q.append(v)

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

main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
  def p(a,b):
    if a < b:
      return (a,b)
    else:
      return (b,a)
  input = open(0).readline
  N = int(input())
  E = [[] for i in range(N)]
  C = {}
  D = [0] * N
  parent = [0]*N
  for i in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    C[p(a,b)] = c

  M, K = map(int, input().split())
  K -= 1
  parent[K] = K
  Q = deque()
  Q.append(K)

  while Q:
    u = Q.popleft()
    d = D[u]
    for v in E[u]:
      if parent[u] == v:
        continue
      parent[v] = u
      D[v] = d + C[p(u,v)]
      Q.append(v)

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

main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
E = [[] for i in range(N)]
C = {}
D = [0] * N
parent = [0]*N
for i in range(N-1):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  E[a].append(b)
  E[b].append(a)
  C[(a,b)] = c
  C[(b,a)] = c
  
M, K = map(int, input().split())
K -= 1
parent[K] = K
Q = deque()
Q.append(K)

while Q:
  u = Q.popleft()
  d = D[u]
  for v in E[u]:
    if parent[u] == v:
      continue
    parent[v] = u
    D[v] = d + C[(u,v)]
    Q.append(v)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n = getN()

vtxs = [[] for i in range(n)]
dist = [0 for i in range(n)]
visit = [0 for i in range(n)]

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

ques, k = getList()

from collections import deque
q = deque([k-1])
visit[k-1] = 1
while(q):
    cur = q.popleft()
    cdist = dist[cur]
    for nx in vtxs[cur]:
        nxa, nxc = nx
        if visit[nxa] == 0:
            dist[nxa] = cdist + nxc
            visit[nxa] = 1
            q.append(nxa)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

class Node:
    def __init__(self, id):
        self.id = id
        self.link = []
        self.cost = []
        self.check = False

def main():
    N = int(input())
    
    nodes = [Node(i) for i in range(N+1)]

    for i in range(N-1):
        a, b, c = map(int, input().split())
        nodes[a].link.append(nodes[b])
        nodes[b].link.append(nodes[a])
        nodes[a].cost.append(c)
        nodes[b].cost.append(c)
    
    Q, K = map(int, input().split())

    q = deque()
    q.append((nodes[K], 0))
    nodes[K].check = True
    costs = [0] * (N+1)
    while len(q) > 0:
        node, cost = q.popleft()
        costs[node.id] = cost
        for i in range(len(node.link)):
            next_node = node.link[i]
            if not next_node.check:
                q.append((next_node, cost + node.cost[i]))
                next_node.check = True
    
    for i in range(Q):
        x, y = map(int, input().split())
        print(costs[x] + costs[y])
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
import heapq
def main():

    N = int(input())
    edges = collections.defaultdict(dict)
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        edges[a][b] = c
        edges[b][a] = c

    Q, K = map(int, input().split())
    dist = dict()
    cur = [[0, K]]
    while cur:
        d, a = heapq.heappop(cur)
        if a not in dist:
            dist[a] = d
            for b in edges[a]:
                if b not in dist:
                    heapq.heappush(cur, [d+edges[a][b], b])

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def dfs(v,p,d):
    for i, j in tree[v]:
        if i != p:
            depth[i] = d + j
            dfs(i,v,d+j)

N = int(input())

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

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

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

depth = [0 for i in range(N)]
depth[K-1] = 0

dfs(K-1,-1,0)

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

Submission status: Accepted

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

class Edge:
    def __init__(self,to,cost):
        self.to = to
        self.cost = cost
#隣接グラフ
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    graph[a-1].append(Edge(b-1,c))
    graph[b-1].append(Edge(a-1,c))
dp = [0 for i in range(N)]

def dfs(s,pare):
    for i in graph[s]:
        if i.to != pare :
            dp[i.to] = dp[s] + i.cost
            dfs(i.to,s)
        else:
            continue 


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

Submission status: Accepted

Solution code:
N = int(input())
INF = float("inf")
es = [[] for _ in range(N)]
for i in range(N-1):
    a,b,c = map(int, input().split())
    a,b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))

Q, K = map(int, input().split())
xy = []
for i in range(Q):
    x,y = map(int, input().split())
    xy.append([x-1, y-1])

checked = [False] * N
d = [INF] * N
d[K-1] = 0

next_check = []
next_check.append(K-1)
while len(next_check):
    now = next_check.pop()
    for next,cost in es[now]:
        if not checked[next]:
            d[next] = min(d[next], d[now] + cost)
            checked[next] = True
            next_check.append(next)
    


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

Submission status: Accepted

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

N=int(input())

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

Q,K=map(int,input().split())
A=[list(map(int,input().split())) for i in range(Q)]


depth=[0 for i in range(N)]
depth[K-1]=0

def dfs(cur,p,d):
	for i,j in G[cur]:
		if i!=p:
			depth[i]=d+j
			dfs(i,cur,d+j)

dfs(K-1,-1,0)


for i,j in A:
	print(depth[i-1]+depth[j-1])

Submission status: Accepted

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

def main():
    N = int(input())
    X = [list(map(int,input().split())) for _ in range(N-1)]
    Q,K = map(int,input().split())
    Y = [list(map(int,input().split())) for _ in range(Q)]

    tree = [[] for _ in range(N)]
    dif = [10**15 for _ in range(N)]
    dif[K-1] = 0
    for i in range(N-1):
        tree[X[i][0]-1].append((X[i][1]-1,X[i][2]))
        tree[X[i][1]-1].append((X[i][0]-1,X[i][2]))

    queue = [K-1]
    while queue:
        a = queue.pop()
        for i in tree[a]:
            s,t = i[0],i[1]
            if dif[s] == 10**15:
                dif[s] = dif[a]+t
                queue.append(s)

    for i in range(Q):
        print(dif[Y[i][0]-1]+dif[Y[i][1]-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def dijkstra(graph: 'List[List[int]]', s: int):
    """
    特定の始点から各点への最短距離を求めます。
    重みが非負であることを前提とします。
    ================
    s: 始点
    graph: 隣接リスト
    ----------------
    d: sから各頂点への最短距離
    counter: sから各頂点への最短経路の個数
    """
    import heapq
    INF = 1e18
    d = [INF] * len(graph)
    d[s]  = 0
    counter = [0] * len(graph)
    counter[s] = 1

    q = []
    heapq.heappush(q, (0, s))
    while q:
        (dd, vv) = heapq.heappop(q)
        if d[vv] < dd:
            continue
        for (to, cost) in graph[vv]:
            if d[to] > (d[vv] + cost):
                d[to] = d[vv] + cost
                counter[to] = counter[vv]
                heapq.heappush(q, (d[to], to))
            elif d[to] == (d[vv] + cost):
                counter[to] += counter[vv]
    return d, counter


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):
    G = [[] for _ in range(N)]
    for i in range(N-1):
        G[a[i]-1].append((b[i]-1, c[i]))
        G[b[i]-1].append((a[i]-1, c[i]))
    dist, _ = dijkstra(G, K-1)

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

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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())
A = [list(map(int,input().split())) for i in range(n-1)]
q, k = map(int,input().split())
X = [list(map(int,input().split())) for i in range(q)]

M = [[] for i in range(n+1)]
V = [0] * (n+1)
D = [0] * (n+1)

for i in range(n-1):
    M[A[i][0]].append([A[i][1], A[i][2]])
    M[A[i][1]].append([A[i][0], A[i][2]])

#print(M)

def d(x, dist):
    V[x] = 1
    D[x] = dist
    #print(M[x])
    for i in range(len(M[x])):
        #print(M[x][i][0])
        if V[M[x][i][0]] == 0:
            #print("V")
            Q.append([M[x][i][0], dist+M[x][i][1]])

Q = [[k, 0]]

st = 0
while st < len(Q):
    #print(st)
    d(Q[st][0], Q[st][1])
    st += 1

for i in range(q):
    print(D[X[i][0]] + D[X[i][1]])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
Tree=[[] for _ in range(n)]
for _ 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=[float('inf')]*n
dist[k-1]=0
stack=[k-1]

while stack!=[]:
    p=stack.pop()
    for q in Tree[p]:
        qp,ql=q[0],q[1]
        if dist[qp]==float('inf'):
            dist[qp]=dist[p]+ql
            stack.append(qp)

for _ 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, deque
inf = float('inf')

def solve(graph, n, start_node, end_node):
  if start_node == end_node:
    return 0

  global costs_dict
  key = str(start_node) + '-' + str(end_node)
  if key in costs_dict:
    return costs_dict[key][end_node]

  costs = [inf for _ in range(n)]
  costs[start_node] = 0
  flgs = [False for _ in range(n)]

  while not all(flgs):
    prv_node = _get_min_idx(flgs,costs)
    flgs[prv_node] = True

    for node, dis in graph[prv_node]:
      if costs[node] > costs[prv_node] + dis:
        costs[node] = costs[prv_node] + dis
  costs_dict[key] = costs  
  return costs[end_node]
    
    
def _get_min_idx(flgs, costs):
    min_cost = inf
    min_idx = None
    cnt = 0
    for cost, flg in zip(costs, flgs):
      if min_cost > cost and flg is False:
        min_cost = cost
        min_idx = cnt
      cnt += 1
    return min_idx
        

n =int(input())
graph = defaultdict(list)
costs_dict = {}

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

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

l = [0 for _ in range(n)]
queue = deque()
queue.append(k)
while len(queue) > 0:
  a = queue.pop()
  for b, c in graph[a]:
    if l[b] == 0:
      l[b] = l[a] + c
      queue.append(b)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
import random
import sys


def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007


n = I()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a-1] += [[b-1, c]]
    graph[b-1] += [[a-1, c]]



q, k = LI()
q_ab = LIRM(q)



dist = n * [-1]
dist[k-1] = 0
que = deque([k-1])
while que:
    cur = que.pop()
    for nxt, c in graph[cur]:
        if dist[nxt] == -1:
            dist[nxt] = dist[cur] + c
            que += [nxt]



for a, b in q_ab:
    print(dist[a] + dist[b])

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from collections import deque
N = int(input())
D =dd(list)
for i in range(N-1):
  a, b, c = map(int, input().split())
  D[a-1].append((b-1, c))
  D[b-1].append((a-1, c))

Q, K = map(int, input().split())
K -= 1
L = [0 for _ in range(N)]
q = deque([])
q.append(K)
while len(q) > 0:
  a = q.pop()
  for b, c in D[a]:
    if L[b] == 0:
      L[b] = L[a] + c
      q.append(b)

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#A
def A():
    n = S()
    n1 = n[::-1]
    for i in range(len(n)):
        if n1[i] != n[i]:
            print("No")
            return
    print("Yes")
    return

#B
def B():
    a, b, c, d = LI()
    ans = [0 for i in range(101)]
    ans[a] += 1
    ans[b] -= 1
    ans[c] += 1
    ans[d] -= 1
    for i in range(100):
        ans[i+1] += ans[i]
    print(ans.count(2))
#C
def C():
    n = II()
    ans = 1
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    for _ in range(n):
        t = II()
        ans = ans // gcd(ans, t) * t
    print(ans)
    return

#D
def D():
    n = II()
    vedg = defaultdict(list)
    for _ in range(n-1):
        a, b, c = LI()
        vedg[a].append((b, c))
        vedg[b].append((a, c))
    dist = defaultdict(lambda :inf)
    Q, k = LI()
    q = deque([k])
    dist[k] = 0
    while q:
        f = q.pop()
        for t, value in vedg[f]:
            if dist[t] > dist[f] + value:
                dist[t] = dist[f] + value
                q.append(t)
    for _ in range(Q):
        x, y = LI()
        print(dist[x] + dist[y])
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from collections import deque
N = int(input())
D =dd(list)
for i in range(N-1):
  a, b, c = map(int, input().split())
  D[a-1].append((b-1, c))
  D[b-1].append((a-1, c))

Q, K = map(int, input().split())
K -= 1
L = [0 for _ in range(N)]
q = deque([])
q.append(K)
while len(q) > 0:
  a = q.pop()
  for b, c in D[a]:
    if L[b] == 0:
      L[b] = L[a] + c
      q.append(b)

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

Submission status: Accepted

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

n=int(input())
l=[list(map(int,input().split())) for _ in [0]*(n-1)]
q,k=map(int,input().split())
L=[list(map(int,input().split())) for _ in [0]*q]

neighbor=[[] for _ in range(n+1)]
for i in range(n-1):
    neighbor[l[i][0]].append([l[i][1],l[i][2]])
    neighbor[l[i][1]].append([l[i][0],l[i][2]])

cost=[-1]*(n+1)
cost[k]=0
c=0

def sol(i,p,d):
    global cost
    cost[i]=d
    for x in neighbor[i]:
        if x[0]!=p:
            sol(x[0],i,d+x[1])
sol(k,-1,0)

for i in range(q):
    print(cost[L[i][0]]+cost[L[i][1]])

Submission status: Accepted

Solution code:
N = int(input())
E = [[] for i in range(N)]
for i in range(N-1):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  E[a].append((b, c))
  E[b].append((a, c))
Q, K = map(int, input().split())
K = K-1
D = [-1]*N
D[K] = 0
q = [(K, 0)]
while q:
  k, d = q.pop()
  for n, c in E[k]:
    if D[n] < 0:
      D[n] = d+c
      q.append((n, d+c))
#print(D)
for i in range(Q):
  x, y = map(int, input().split())
  x, y = x-1, y-1
  r = D[x]+D[y]
  print(r)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
abc = [list(map(int,input().split())) for _ in range(n-1)]
q,k = map(int,input().split())
query = [list(map(int,input().split())) for _ in range(q)]

point = [[] for _ in range(n+1)]
for l in abc:
  point[l[0]].append([l[1],l[2]])
  point[l[1]].append([l[0],l[2]])

done = set()
done.add(k)
d = [0]*(n+1)
lst = [k]

while lst:
  start = lst.pop()
  for l in point[start]:
    if l[0] not in done:
      d[l[0]] = d[start] + l[1]
      done.add(l[0])
      lst.append(l[0])

for l in query:
  print(d[l[0]]+d[l[1]])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
to = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    to[a - 1].append((b - 1, c))
    to[b - 1].append((a - 1, c))
Q, K = map(int, input().split())
XY = []
for _ in range(Q):
    x, y = map(int, input().split())
    XY.append((x - 1, y - 1))

ds = [0] * N
q = deque()
q.append((K - 1, 0, -1))
while len(q):
    a, d, par = q.pop()
    ds[a] = d
    for b, c in to[a]:
        if b != par:
            q.append((b, d + c, a))

for x, y in XY:
    print(ds[x] + ds[y])