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: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

tmp = []
tree = []

def dfs(node, depth, fr):
    global tmp, tree
    tree[node] = (fr, depth)
    for i, c in tmp[node]:
        if i != fr:
            dfs(i, depth+c, node)

def main():
    global tmp, tree
    n = int(input().strip())
    tmp = [[] for _ in range(n)]
    tree = [0] * n
    for _ in range(n-1):
        a, b, c = map(int, input().strip().split())
        a -= 1
        b -= 1

        if b > a:
            a, b = b, a
        tmp[a].append((b, c))
        tmp[b].append((a, c))

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n=int(input())
dct=defaultdict(list)

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

q,k=map(int,input().split())
lk=[0]*(n)

def dfs(v,p,d):
  lk[v-1]=d
  for l in dct[v]:
    if l[0]==p:
      continue
    dfs(l[0],v,d+l[1])
  return

dfs(k,-1,0)


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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n=int(input())
dct=defaultdict(list)

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


q,k=map(int,input().split())
lk=[0]*(n)

def dfs(v,p,d):
  lk[v-1]=d

  for l in dct[v]:
    if l[0]==p or lk[l[0]-1]!=0:
      continue
    else:
      dfs(l[0],v,d+l[1])
  return

dfs(k,-1,0)



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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n=int(input())
dct=defaultdict(list)

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


q,k=map(int,input().split())
lk=[0]*(n)

def dfs(v,p,d):
  lk[v-1]=d

  for l in dct[v]:
    if l[0]==p or lk[l[0]-1]!=0:
      continue
    else:
      dfs(l[0],v,d+l[1])
  return

dfs(k,-1,0)



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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n=int(input())
dct=defaultdict(list)

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


q,k=map(int,input().split())
lk=[0]*(n)

def dfs(v,p,d):
  lk[v-1]=d

  for l in dct[v]:
    if l[0]==p:
      continue
    else:
      dfs(l[0],v,d+l[1])
  return

dfs(k,-1,0)



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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n=int(input())
dct=defaultdict(list)

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

q,k=map(int,input().split())
lk=[0]*(n)

def dfs(v,p,d):
  lk[v-1]=d
  print(k,v,p,d,lk)
  for l in dct[v]:
    if l[0]==p:
      continue
    else:
      dfs(l[0],v,d+l[1])
  return

dfs(k,-1,0)

print(lk)

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

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

n = int(input())
ls = [list(map(int, input().split())) for _ in range(n - 1)]

es = [[] for _ in range(n + 1)]
for a, b, c in ls:
    es[a].append((b, c))
    es[b].append((a, c))
ds = [0] * (n + 1)


def dfs(cur, prev, c):
    ds[cur] = ds[prev] + c
    for e, c in es[cur]:
        if e != prev:
            dfs(e, cur, c)


q, k = map(int, input().split())
qs = [list(map(int, input().split())) for _ in range(q)]

dfs(k, k, 0)
for x, y in qs:
    print(ds[x] + ds[y])

Submission status: Runtime Error

Solution code:
from collections import deque

N = int(input())

abc = []

dic = {}

for i in range(N-1):

    a,b,c = map(int,input().split())

    if a not in dic:
        dic[a-1] = []
    if b not in dic:
        dic[b-1] = []

    dic[a-1].append([b-1,c])
    dic[b-1].append([a-1,c])

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

K -= 1

lis = [0] * N

queue = deque([])

queue.append(K)

while len(queue) > 0:

    now = queue.pop()

    for nlis in dic[now]:

        if lis[nlis[0]] != 0 or nlis[0] == K:
            continue

        lis[nlis[0]] = lis[now] + nlis[1]
        queue.append(nlis[0])

#print (lis)

for i in range(Q):

    x,y = map(int,input().split())

    print (lis[x-1]+lis[y-1])

Submission status: Runtime Error

Solution code:
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
Query = []
for i in range(Q):
  x,y = map(int,input().split())
  Query.append([x-1,y-1])
#print(E)
#print(C)
#print(K)
#print(Query)

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 x,y in Query:
  print(Kcost[x]+Kcost[y])

Submission status: Runtime Error

Solution code:
N=int(input())
M=1000000007
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: Runtime Error

Solution code:
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: Runtime Error

Solution code:
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: Runtime Error

Solution code:
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: Runtime Error

Solution code:
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=[float('inf')]*(n+1)

def set_dis(x,d):
    dis[x]=d
    for yy,dd in graph[x] :
        if dis[yy]!=float('inf'):
            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: Runtime Error

Solution code:
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=[float('inf')]*(n+1)

def set_dis(x,d):
    dis[x]=d
    for yy,dd in graph[x] :
        if dis[yy]!=float('inf'):
            continue
        else:
            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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**15) 
N = int(input())
ds = [[0]*N for i in range(N)]
for i in range(N-1):
  a, b, c = list(map(int, input().split(" ")))
  ds[a-1][b-1] = c
  ds[b-1][a-1] = c
q, k = list(map(int, input().split(" ")))
 
def dfs(path, dist, c):
  if c==g:
    return dist
  dists = []
  for i in range(N):
    if ds[i][c]>0 and i not in path:
      dists.append(dfs(path+[c],dist+ds[i][c],i))
  if len(dists)>0:
	  return min(dists)
  else:
      return 10**15
 
ky = []
for i in range(N):
  if i==k-1:
    ky.append(0)
  else:
    g = i
    ky.append(dfs([],0,k-1))
    
for i in range(q):
  x, y = list(map(int, input().split(" ")))
  print(xy[x-1]+ky[y-1])

Submission status: Runtime Error

Solution code:
N = int(input())
ds = [[0]*N for i in range(N)]
for i in range(N-1):
  a, b, c = list(map(int, input().split(" ")))
  ds[a-1][b-1] = c
  ds[b-1][a-1] = c
q, k = list(map(int, input().split(" ")))
 
def dfs(path, dist, c):
  if c==g:
    return dist
  dists = []
  for i in range(N):
    if ds[i][c]>0 and i not in path:
      dists.append(dfs(path+[c],dist+ds[i][c],i))
  if len(dists)>0:
	  return min(dists)
  else:
      return 10**15
 
ky = []
for i in range(N):
  if i==k-1:
    ky.append(0)
  else:
    g = i
    ky.append(dfs([],0,k-1))
    
for i in range(q):
  x, y = list(map(int, input().split(" ")))
  print(xy[x-1]+ky[y-1])

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
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)


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

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
from scipy.sparse.csgraph import shortest_path, dijkstra
import numpy as np

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

Q, K = map(int, input().split())
K -= 1
L1 = dijkstra(L, indices = K)
for i in range(Q):
  x, y = map(int, input().split())
  x -= 1
  y -= 1

  print (int(L1[x] + L1[y]))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
N = int(input())
L = np.full((N, N), np.inf)
for i in range(N-1):
  a, b, c = map(int, input().split())
  L[a-1][b-1] = c
  L[b-1][a-1] = c
L = csr_matrix(L)
L = floyd_warshall(L, 0)
print (L)
Q, K = map(int, input().split())
K -= 1
for i in range(Q):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  print (int(L[x][K] + L[K][y]))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall
N = int(input())
L = np.full((N, N), np.inf)
for i in range(N-1):
  a, b, c = map(int, input().split())
  L[a-1][b-1] = c
  L[b-1][a-1] = c
L = floyd_warshall(L, 0)
Q, K = map(int, input().split())
K -= 1
for i in range(Q):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  print (int(L[x][K] + L[K][y]))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
N = int(input())
L = np.full((N, N), np.inf)
for i in range(N-1):
  a, b, c = map(int, input().split())
  L[a-1][b-1] = c
  L[b-1][a-1] = c
L = shortest_path(L)
Q, K = map(int, input().split())
K -= 1
for i in range(Q):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  print (int(L[x][K] + L[K][y]))

Submission status: Runtime Error

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

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: Runtime Error

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

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: Runtime Error

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

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):
    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: Runtime Error

Solution code:
# ABC070D - Transit Tree Path
import sys
input = sys.stdin.readline

def dfs(v: int, p: int) -> None:
    d = dist[v]
    for u, c in G[v]:  # search vertices available from v recursively
        if u != p:  # p: parent
            dist[u] += d + c  # dist(K, v) + dist(v, u) == d + c
            dfs(u, v)


def main():
    global G, dist
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    Q, K = tuple(map(int, input().split()))
    X = tuple(tuple(map(int, input().split())) for _ in range(Q))
    G = [[] for _ in range(N + 1)]  # graph, N+1: 1-idx
    for v, u, c in E:  # construct a graph
        G[v] += [(u, c)]
        G[u] += [(v, c)]
    dist = [0] * (N + 1)  # distance from vertex K
    dfs(K, -1)
    ans = [dist[x] + dist[y] for x, y in X]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall
n=int(input())
edge = [[10**9 for i in range(n)] for i in range(n)] 
for i in range(n-1):
    x,y,z = map(int,input().split())
    edge[x-1][y-1] = z
    edge[y-1][x-1] = z
for i in range(n):
    edge[i][i] = 0
G = csgraph_from_dense(edge, null_value=10**9)
d = floyd_warshall(G)
q,k=map(int,input().split())
for i in range(q):
    a,b=map(int,input().split())
    print(int(d[a-1][k-1]+d[k-1][b-1]))

Submission status: Runtime Error

Solution code:
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 = [[] * N for _ in range(N)]
for a, b, c in ABC:
  G[a - 1].append((b - 1, c))
  G[b - 1].append((a - 1, c))

D = [-1] * N

def dfs(v, d):
  D[v] = d
  for i, c in G[v]:
    if D[i] < 0:
      dfs(i, d + c)

dfs(K - 1, 0)

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

Submission status: Runtime Error

Solution code:
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 = [[] * N for _ in range(N)]
for a, b, c in ABC:
  G[a - 1].append((b - 1, c))
  G[b - 1].append((a - 1, c))

D = [-1] * N

def dfs(v, p, d):
  D[v] = d
  for i, c in G[v]:
    if D[i] < 0:
      if i == p:
        continue
      dfs(i, v, d + c)

dfs(K - 1, -1, 0)

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

Submission status: Runtime Error

Solution code:
n = int(input())
edges = [[] for _ in range(n)]
for i 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

visited = [0] * n
d = [0] * n
def dfs(v, c):
    for u, c2 in edges[v]:
        if visited[u] == 0:
            d[u] = c + c2
            visited[u] = 1
            dfs(u, c + c2)

visited[k] = 1
dfs(k, 0)

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
sys.setrecursionlimit(100000)
INF = float("inf")


class Graph(object):
    """グラフを扱うオブジェクト
    """

    def __init__(self, N):
        self.N = N
        self.edges = defaultdict(list)
        pass

    def add_edges(self, from_, to_, weight):
        """必ず0インデックスで入力すること。
        """
        self.edges[from_].append([to_, weight])
        self.edges[to_].append([from_, weight])
        pass


def LCA_constract(g: Graph, root=0):
    """
    木gにおいて、頂点u, vのLCA(Lowest Common Ancestor)を求める
    g: 木。無向グラフとして与える。
    u, v:頂点
    root: 根
    元: https://tjkendev.github.io/procon-library/python/graph/lca-doubling.html
    """
    N = g.N
    LN = int(math.log2(g.N))

    ###
    # 各頂点の親 parと各頂点の深さdepthを求める
    ###
    par = [INF]*N
    depth = [INF]*N

    def dfs(curr, pre, dep):         # whileに変えたい
        par[curr] = pre
        depth[curr] = dep
        for n, w in g.edges[curr]:
            if n != pre:
                dfs(n, curr, dep+w)
    dfs(root, None, 0)

    ###
    # 祖先 ancの構築
    ###

    anc = [par]

    for i in range(LN):
        buf = [None]*N
        for j in range(N):
            if anc[i][j] == None:
                continue
            buf[j] = anc[i][anc[i][j]]
        anc.append(buf)
    return anc, depth


def LCA_query(anc, depth, u: int, v: int):
    ###
    # 共通祖先を求める
    ###
    N = len(depth)
    LN = int(math.log2(g.N))

    dd = depth[v] - depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd

    # assert depth[u] <= depth[v]
    for k in range(LN):
        if dd & 1:
            v = anc[k][v]
        dd >>= 1

    # assert depth[u] == depth[v]
    if u == v:
        return u

    for k in range(LN-1, -1, -1):
        pu = anc[k][u]
        pv = anc[k][v]
        if pu != pv:
            u = pu
            v = pv

    # assert anc[0][u] == anc[0][v]
    return anc[0][u]


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

    g = Graph(N)
    for aa, bb, cc in zip(a, b, c):
        g.add_edges(*[aa-1, bb-1, cc])

    anc, depth = LCA_constract(g, root=K-1)

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

    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: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
sys.setrecursionlimit(10**6)
INF = float("inf")


class Graph(object):
    """グラフを扱うオブジェクト
    """

    def __init__(self, N):
        self.N = N
        self.edges = defaultdict(list)
        pass

    def add_edges(self, from_, to_, weight):
        """必ず0インデックスで入力すること。
        """
        self.edges[from_].append([to_, weight])
        self.edges[to_].append([from_, weight])
        pass


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

    g = Graph(N)
    for aa, bb, cc in zip(a, b, c):
        g.add_edges(aa-1, bb-1, cc)

    N = g.N

    depth = [INF]*N

    def dfs(curr, pre, dep):         # whileに変えたい
        depth[curr] = dep
        for n, w in g.edges[curr]:
            if n != pre:
                dfs(n, curr, dep+w)
    dfs(K, None, 0)

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

    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: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
INF = float("inf")


class Graph(object):
    """グラフを扱うオブジェクト
    """

    def __init__(self, N):
        self.N = N
        self.edges = defaultdict(list)
        pass

    def add_edges(self, from_, to_, weight):
        """必ず0インデックスで入力すること。
        """
        self.edges[from_].append([to_, weight])
        self.edges[to_].append([from_, weight])
        pass


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

    g = Graph(N)
    for aa, bb, cc in zip(a, b, c):
        g.add_edges(*[aa-1, bb-1, cc])

    N = g.N

    par = [INF]*N
    depth = [INF]*N

    def dfs(curr, pre, dep):         # whileに変えたい
        par[curr] = pre
        depth[curr] = dep
        for n, w in g.edges[curr]:
            if n != pre:
                dfs(n, curr, dep+w)
    dfs(K, None, 0)

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

    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: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
INF = float("inf")


class Graph(object):
    """グラフを扱うオブジェクト
    """

    def __init__(self, N):
        self.N = N
        self.edges = defaultdict(list)
        pass

    def add_edges(self, from_, to_, weight):
        """必ず0インデックスで入力すること。
        """
        self.edges[from_].append([to_, weight])
        self.edges[to_].append([from_, weight])
        pass


def LCA_constract(g: Graph, root=0):
    """
    木gにおいて、頂点u, vのLCA(Lowest Common Ancestor)を求める
    g: 木。無向グラフとして与える。
    u, v:頂点
    root: 根
    元: https://tjkendev.github.io/procon-library/python/graph/lca-doubling.html
    """
    N = g.N
    LN = int(math.log2(g.N))

    ###
    # 各頂点の親 parと各頂点の深さdepthを求める
    ###
    par = [INF]*N
    depth = [INF]*N

    def dfs(curr, pre, dep):         # whileに変えたい
        par[curr] = pre
        depth[curr] = dep
        for n, w in g.edges[curr]:
            if n != pre:
                dfs(n, curr, dep+w)
    dfs(root, None, 0)

    ###
    # 祖先 ancの構築
    ###

    anc = [par]

    for i in range(LN):
        buf = [None]*N
        for j in range(N):
            if anc[i][j] == None:
                continue
            buf[j] = anc[i][anc[i][j]]
        anc.append(buf)
    return anc, depth


def LCA_query(anc, depth, u: int, v: int):
    ###
    # 共通祖先を求める
    ###
    N = len(depth)
    LN = int(math.log2(g.N))

    dd = depth[v] - depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd

    # assert depth[u] <= depth[v]
    for k in range(LN):
        if dd & 1:
            v = anc[k][v]
        dd >>= 1

    # assert depth[u] == depth[v]
    if u == v:
        return u

    for k in range(LN-1, -1, -1):
        pu = anc[k][u]
        pv = anc[k][v]
        if pu != pv:
            u = pu
            v = pv

    # assert anc[0][u] == anc[0][v]
    return anc[0][u]


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

    g = Graph(N)
    for aa, bb, cc in zip(a, b, c):
        g.add_edges(*[aa-1, bb-1, cc])

    anc, depth = LCA_constract(g, root=K-1)

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

    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: Runtime Error

Solution code:
## abc070d: Transit Tree Path

n = int(input())

T = [None]*(n+1)
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    if(T[v1] is None): T[v1] = [[v2,d]]
    else: T[v1].append([v2,d])
    if(T[v2] is None): T[v2] = [[v1,d]]
    else: T[v2].append([v1,d])

depth = [0 for _ in  range(n+1)]

def dfs(p, c, d):
    depth[c] = d
    for (v,vd) in T[c]:
        if v!=p: dfs(c, v, depth[c] + vd)

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

dfs(0,k,0)

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])

Submission status: Runtime Error

Solution code:
## abc070d: Transit Tree Path

n = int(input())

T = [None]*(n+1)
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    if(T[v1] is None): T[v1] = [[v2,d]] # [child, distance]
    else: T[v1].append([v2,d])
    if(T[v2] is None): T[v2] = [[v1,d]]
    else: T[v2].append([v1,d])

depth = [-1 for _ in  range(n+1)]

def dfs(p, d, pd):
    depth[p] = d + pd # 距離設定 == 訪問済み
    for (c,cd) in T[p]:
        if depth[c]>=0: continue # 訪問済み
        dfs(c, cd, depth[p])

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

dfs(k,0,0)

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])

Submission status: Runtime Error

Solution code:
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    G[a-1].append((b-1,c))
    G[b-1].append((a-1,c))
q,k=map(int,input().split())
k=k-1
stack=[k]
dis=[-1]*n
dis[k]=0
while len(stack)!=[]:
    now=stack.pop()
    d=dis[now]
    for i in G[now]:
        if dis[i[0]]==-1:
            dis[i[0]]=d+i[1]
            stack.append(i[0])
for i in range(q):
    x,y=map(int,input().split())
    x=x-1
    y=y-1
    print(dis[x]+dis[y])