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:
n = int(input())
tree = [[] for _ in range(n+1)]

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

q, k = map(int, input().split())
k -= 1
d = [0] * (n+1)

def dfs(x, c, p):
    global tree
    d[x] = c
    for leaf in tree[x]:
        if leaf[0] == p:
            continue
        else:
            dfs(leaf[0], leaf[1]+c, x)

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

Submission status: Runtime Error

Solution code:
n = int(input())
tree = [[] for _ in range(n+1)]

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

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

d = [0] * (n+1)

def dfs(x, c, p):
    global tree
    d[x] = c
    for leaf in tree[x]:
        if leaf[0] == p:
            continue
        else:
            dfs(leaf[0], leaf[1]+c, x)

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
 
def ans():
    def dfs(v, p, d):
        depth[v] = d
        for e, cost in tree[v]:
            if e == p:
                continue
            dfs(e, v, d + cost)
 
    n = int(input())
    tree = [[] for _ in range(n + 1)]
    depth = [0] * (n * 2)
    for _ in range(1, n):
        a, b, c = map(int, input().split())
        tree[a].append((b, c))
        tree[b].append((a, c))
 
    q, k = map(int, input().split())
    dfs(k, -1, 0)
    for _ in range(q):
        x, y = map(int, input().split())
        print(depth[x] + depth[y])
 
 
ans()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

def ans():
    def dfs(v, p, d):
        depth[v] = d
        for e, cost in tree[v]:
            if e == p:
                continue
            dfs(e, v, d + cost)

    n = int(input())
    tree = [[] for _ in range(n + 1)]
    depth = [0] * (n * 2)
    for _ in range(1, n):
        a, b, c = map(int, input().split())
        tree[a].append((b, c))
        tree[b].append((a, c))

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


ans()

Submission status: Runtime Error

Solution code:
def ans():
    def dfs(v, p, d):
        depth[v] = d
        for e, cost in tree[v]:
            if e == p:
                continue
            dfs(e, v, d + cost)
    n = int(input())
    tree = [[] for _ in range(n+1)]
    depth = [0] * (n * 2)
    for _ in range(1,n):
        a, b, c = map(int, input().split())
        tree[a].append((b,c))
        tree[b].append((a,c))

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

ans()

Submission status: Runtime Error

Solution code:
def ans():
    def dfs(v, p, d):
        depth[v] = d
        for e, cost in tree[v]:
            if e == p:
                continue
            dfs(e, v, d + cost)
    n = int(input())
    tree = [[] for _ in range(n+1)]
    depth = [0] * 100001
    for _ in range(1,n):
        a, b, c = map(int, input().split())
        tree[a].append((b,c))
        tree[b].append((a,c))

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

ans()

Submission status: Runtime Error

Solution code:
N=int(input())
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
c=[0 for i in range(N-1)]
VL=[dict() for i in range(N)]
for i in range(N-1):
    a[i],b[i],c[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1
    VL[a[i]][b[i]]=c[i]
    VL[b[i]][a[i]]=c[i]
Q,K=map(int,input().split())
K-=1
x=[0 for i in range(Q)]
y=[0 for i in range(Q)]
for i in range(Q):
    x[i],y[i]=map(int,input().split())
    x[i]-=1
    y[i]-=1
reached=[False for i in range(N)]
dist=[0 for i in range(N)]
def dfs(v):
    reached[v]=True
    for u in VL[v]:
        if not(reached[u]):
            dist[u]=dist[v]+VL[v][u]
            dfs(u)
dfs(K)
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])

Submission status: Runtime Error

Solution code:
N=int(input())
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
c=[0 for i in range(N-1)]
VL=[dict() for i in range(N)]
for i in range(N-1):
    a[i],b[i],c[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1
    VL[a[i]][b[i]]=c[i]
    VL[b[i]][a[i]]=c[i]
Q,K=map(int,input().split())
K-=1
x=[0 for i in range(Q)]
y=[0 for i in range(Q)]
for i in range(Q):
    x[i],y[i]=map(int,input().split())
    x[i]-=1
    y[i]-=1
reached=[False for i in range(N)]
dist=[0 for i in range(N)]
def dfs(v):
    reached[v]=True
    for u in VL[v]:
        if not(reached[u]):
            dist[u]=dist[v]+VL[u][v]
            dfs(u)
dfs(K)
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])

Submission status: Runtime Error

Solution code:
import heapq
n = int(input())
cost = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
for _ in range(n-1):
    From, To, d = map(int, input().split())
    cost[From][To] = d
    cost[To][From] = d

q, k = map(int, input().split())
dist = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
used = [False]*(n+1)

for i in range(n+1):
    dist[i][i] = 0
        
def dijkstra(s, dist):
    next_v = [[0, s]]
    
    while len(next_v):
        v = next_v[0][1]
        for i in range(n+1):
            if dist[s][i] > dist[s][v] + cost[v][i]:
                dist[s][i] = dist[s][v] + cost[v][i]
                heapq.heappush(next_v, [dist[s][i], i])
        heapq.heappop(next_v)
        
    return dist
dist = dijkstra(k, dist)

for _ in range(q):
    x, y = map(int, f.readline().split())
    if used[x] == False:
        dist = dijkstra(x, dist)
        used[x] = True
    print(dist[x][k]+dist[k][y])

Submission status: Runtime Error

Solution code:
import heapq
n = int(f.readline())
cost = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
for _ in range(n-1):
    From, To, d = map(int, f.readline().split())
    cost[From][To] = d
    cost[To][From] = d

q, k = map(int, f.readline().split())
dist = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
used = [False]*(n+1)

for i in range(n+1):
    dist[i][i] = 0
        
def dijkstra(s, dist):
    next_v = [[0, s]]
    
    while len(next_v):
        v = next_v[0][1]
        for i in range(n+1):
            if dist[s][i] > dist[s][v] + cost[v][i]:
                dist[s][i] = dist[s][v] + cost[v][i]
                heapq.heappush(next_v, [dist[s][i], i])
        heapq.heappop(next_v)
        
    return dist
dist = dijkstra(k, dist)

for _ in range(q):
    x, y = map(int, f.readline().split())
    if used[x] == False:
        dist = dijkstra(x, dist)
        used[x] = True
    print(dist[x][k]+dist[k][y])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

N = int(input())
edges = []
connected = [[] for i in range(100010)]
for i in range(N-1):
    x=list(map(int, input().split()))
    x[0] -= 1
    x[1] -= 1
    edges.append(x)
    connected[x[0]].append([x[1], x[2]])
    connected[x[1]].append([x[0], x[2]])

Q,K = map(int, input().split())
K -= 1
depth = [0]*100010
def DFS(v, p, d):
    depth[v] = d
    for child in connected[v]:
        if child[0] == p:
            continue
        DFS(child[0], v, d+child[1])

DFS(K,-1,0)
for i in range(Q):
    xi, yi = map(int, input().split())
    print(depth[xi-1]+depth[yi-1])

Submission status: Runtime Error

Solution code:
N = int(input())
edges = []
connected = [[] for i in range(100010)]
for i in range(N-1):
    x=list(map(int, input().split()))
    x[0] -= 1
    x[1] -= 1
    edges.append(x)
    connected[x[0]].append([x[1], x[2]])
    connected[x[1]].append([x[0], x[2]])

Q,K = map(int, input().split())
K -= 1
depth = [0]*100010
def DFS(v, p, d):
    depth[v] = d
    for child in connected[v]:
        if child[0] == p:
            continue
        DFS(child[0], v, d+child[1])

DFS(K,-1,0)
for i in range(Q):
    xi, yi = map(int, input().split())
    print(depth[xi-1]+depth[yi-1])

Submission status: Runtime Error

Solution code:
N = int(input())
edges = []
connected = [[] for i in range(N+1)]
for i in range(N-1):
    x=list(map(int, input().split()))
    x[0] -= 1
    x[1] -= 1
    edges.append(x)
    connected[x[0]].append([x[1], x[2]])
    connected[x[1]].append([x[0], x[2]])

Q,K = map(int, input().split())
K -= 1
depth = [0]*N
def DFS(v, p, d):
    depth[v] = d
    for child in connected[v]:
        if child[0] == p:
            continue
        DFS(child[0], v, d+child[1])

DFS(K,-1,0)
for i in range(Q):
    xi, yi = map(int, input().split())
    print(depth[xi-1]+depth[yi-1])

Submission status: Runtime Error

Solution code:
N = int(input())
edges = []
connected = [[] for i in range(N+1)]
for i in range(N-1):
    x=list(map(int, input().split()))
    x[0] -= 1
    x[1] -= 1
    edges.append(x)
    connected[x[0]].append([x[1], x[2]])
    connected[x[1]].append([x[0], x[2]])

Q,K = map(int, input().split())
depth = [0]*N
def DFS(v, p, d):
    depth[v] = d
    for child in connected[v]:
        if child[0] == p:
            continue
        DFS(child[0], v, d+child[1])

DFS(K,-1,0)
for i in range(Q):
    xi, yi = map(int, input().split())
    print(depth[xi-1]+depth[yi-1])

Submission status: Runtime Error

Solution code:
N = int(input())
edges = []
connected = [[] for i in range(N+1)]
for i in range(N-1):
    x=list(map(int, input().split()))
    edges.append(x)
    connected[x[0]].append([x[1], x[2]])
    connected[x[1]].append([x[0], x[2]])

Q,K = map(int, input().split())
depth = [0]*(N+1)
def DFS(v, p, d):
    depth[v] = d
    for child in connected[v]:
        if child[0] == p:
            continue
        DFS(child[0], v, d+child[1])

DFS(K,-1,0)
for i in range(Q):
    xi, yi = map(int, input().split())
    print(depth[xi]+depth[yi])

Submission status: Runtime Error

Solution code:
N = int(input())
edges = [[] for i in range(N-1)]
connected = [[] for i in range(N+1)]
for i in range(N-1):
    edges[i]=list(map(int, input().split()))
    connected[edges[i][0]].append([edges[i][1], edges[i][2]])
    connected[edges[i][1]].append([edges[i][0], edges[i][2]])

##print('edges=',edges)
'''def connected(v):
    children = []
    for edge in edges:
        if edge[0] == v:
            children.append([edge[1],edge[2]])
        elif edge[1] == v:
            children.append([edge[0],edge[2]])

    return children'''

Q,K = map(int, input().split())
##print('Q=',Q)
depth = [0]*(N+1)
def DFS(v, p, d):
    depth[v] = d
    for child in connected[v]:
        if child[0] == p:
            continue
        DFS(child[0], v, d+child[1])

DFS(K,-1,0)
for i in range(Q):
    xi, yi = map(int, input().split())
    print(depth[xi]+depth[yi])

Submission status: Runtime Error

Solution code:
# coding=utf-8

N = int(input())
tree = [[]for x in range(N)]
depth = [0 for x in range(N)]
for _ in range(N-1):
    line = input().split(" ")
    a = int(line[0])-1
    b = int(line[1])-1
    c = int(line[2])
    tree[a].append((b, c))
    tree[b].append((a, c))

line = input().split(" ")
Q = int(line[0])
K = int(line[1])-1

def dfs(v, p, d):
    depth[v] = d
    for e in tree[v]:
        if e[0]==p:
            continue
        dfs(e[0], v, d+e[1])

dfs(K, -1, 0)

for _ in range(Q):
    line = input(" ").split(" ")
    x = int(line[0])-1
    y = int(line[1])-1
    print(str(depth[x]+depth[y]))

Submission status: Runtime Error

Solution code:
import networkx
class Node:
    def __init__(self):
        pass
 
class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost
 
    def add_node(self,node):
        self.nodes.append(node)
 
class myGraph:
 
    def __init__(self):
        self.adj={}
        self.nodes={}
 
    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)
 
        u,v=edge[0],edge[1]
 
        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}
 
        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}
 
        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost
 
    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)
 
 
        u,v=edge[0],edge[1]
 
        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}
 
        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}
 
        self.adj[u][v] = cost
 
    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]
 
 
    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))
 
        return edges
 
    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges
 
    def bermn_ford(self,start,init=0):
 
        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")
 
        dists[start]=init
        edges=self.makeEdgeobj()
 
        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True
 
            if i==len(nodes)-1:
                return False
 
            if not update:
                break
 
        return dists
 
 
    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''
 
        N = len(self.adj)          # グラフのノード数
        #dist = [float('inf') for i in range(N)] # 始点から各頂点までの最短距離を格納する
        dist = {k:float('inf') for k in self.nodes}
        #prev = [float('inf') for i in range(N)]
 
        dist[start] = 0
        visited = []
 
        koho=[]
        heapq.heappush(koho,(0,start))
 
        vtx=list(self.nodes)
        vtx.remove(start)
 
        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            if dist[mini]<d:
                continue
 
 
            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:# and not(k in visited):
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    #prev[k]=mini
 
        return dist
 
    def prim(self):
 
        import heapq
 
        nodes=list(self.nodes.keys())
        N=len(nodes)
 
        X=[nodes[0]]
        unused=[]
        for u in self.adj[X[0]]:
            heapq.heappush(unused,(self.adj[X[0]][u],X[0],u))
 
        total_cost=0
        used={n:False for n in nodes}
        used[X[0]]=True
        while True:
            #print(unused)
            #print(X,total_cost)
            cost,u,v=heapq.heappop(unused)
            if used[v]:
                continue
            X.append(v)
            used[v]=True
            total_cost+=cost
            if len(X)==N:
                break
 
            for u in self.adj[v]:
                if used[u]:
                    continue
                heapq.heappush(unused,(self.adj[u][v],v,u))
 
        return total_cost
 
 
 
 
    def show(self):
 
        import networkx as nx
        import matplotlib.pyplot as plt
        G=nx.Graph()
 
        for u in self.adj:
            for v in self.adj[u]:
 
                #G.add_edge(e.node_from,e.node_to,weight=e.cost)
                G.add_edge(u,v,weight=self.adj[u][v])
                #print(e.node_from,e.node_to,e.cost)
 
        pos=nx.spring_layout(G)
        #nx.draw_networkx_edges(G,pos=pos,edgelist=G.edges())
        edge_weight=dict([((u,v,),int(d['weight'])) for u,v,d in G.edges(data=True)])
 
        nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_weight)
        #nx.draw_networkx_labels(G, pos)
        nx.draw_networkx_nodes(G,pos)
        nx.draw_networkx_edges(G,pos)
        nx.draw_networkx_labels(G,pos)
        #plt.axis('off')
        #nx.draw(G,with_labels=True)
        plt.show()
 
 
 
def spaceinput():
    s=input()
    if len(s)==0:
        return False
 
    return list(map(int,s.split(" ")))
 
if __name__=="__main__":
 
    N=int(input())
 
    g=myGraph()
 
 
    for i in range(N-1):
        try:
            ss=spaceinput()
            if not ss:
                break
        except:
            break
        g.add_edge((ss[0],ss[1]),ss[2])
        #g.add_directed_edge((ss[0],ss[1]),ss[2])
 
    Q,K=spaceinput()
 
    res=g.dijkstra(K)
    xx=[]
    for k in range(Q):
        xx.append(spaceinput())
 
 
 
    for x,y in xx:
        print(int(res[x]+res[y]))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
N = int(raw_input())
dict = {}
for i in range(1,N+1):
    dict[i]={}
for i in range(1,N):
    a = map(int,raw_input().split())
    dict[a[0]].update({a[1]:a[2]})
    dict[a[1]].update({a[0]:a[2]})
leng = {}
q,K = map(int,raw_input().split())
def rec(bef,now):
    leng[now]=leng[bef]+dict[bef][now]
    for i in dict[now]:
        if i in leng:
            continue
        rec(now,i)
leng[K] = 0
for j in dict[K]:
    rec(K,j)
for i in range(0,q):
    a,b = map(int, raw_input().split())
    print leng[a]+leng[b]

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
N = int(raw_input())
dict = {}
for i in range(1,N+1):
    dict[i]={}
for i in range(1,N):
    a = map(int,raw_input().split())
    dict[a[0]].update({a[1]:a[2]})
    dict[a[1]].update({a[0]:a[2]})
leng = {}
q,K = map(int,raw_input().split())
def rec(bef,now):
    leng[now]=leng[bef]+dict[bef][now]
    for i in dict[now]:
        if i in leng:
            continue
        rec(now,i)
leng[K] = 0
for j in dict[K]:
    rec(K,j)
for i in range(0,q):
    a,b = map(int, raw_input().split())
    print leng[a]+leng[b]

Submission status: Runtime Error

Solution code:
import sys
import Queue

graph = {}

def get_all(K, N):
    answer = {}
    stack = []
    stack.append((K, 0, []))
    while len(answer) < N:
        start, start_dist, path  = stack.pop()
        answer[start] = start_dist
        for target, target_dist in graph[start]:
            if target in path:
                continue
            stack.append((target, start_dist + target_dist, path + [start]))
    return answer

def get_all_re(K, result, dist, path):
    for target, target_dist in graph[K]:
        if target in path:
            continue
        result[target] = dist + target_dist
        get_all_re(target, result, dist + target_dist, path + [target])

test =False
if test:
    N =3
    graph[1] = [(2, 1)]
    graph[2] = [(1, 1), (3, 1)]
    graph[3] = [(2, 1)]
    #answer = get_all(2, 3)
    answer = {}
    K = 1
    get_all_re(K, answer, 0, [K])
    print answer
else:
    N = int(raw_input())
    for _ in range(N - 1):
        a, b, c = raw_input().split()
        a = int(a)
        b = int(b)
        c = int(c)
        if a not in graph:
            graph[a] = [(b, c)]
        else:
            graph[a].append((b, c))
        if b not in graph:
            graph[b] = [(a, c)]
        else:
            graph[b].append((a, c))

    Q, K = raw_input().split()
    Q = int(Q)
    K = int(K)
    #answer = get_all(K, N)
    answer = {}
    get_all_re(K, answer, 0, [K])
    for _ in range(Q):
        x, y = raw_input().split()
        x = int(x)
        y = int(y)
        print answer[x] + answer[y]

Submission status: Runtime Error

Solution code:
def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in edges[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
 
N=int(input())
edges=[]
for i in range(N-1):
  edges+=[list(map(int,input().split()))]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,edges,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Submission status: Runtime Error

Solution code:
N = int(input())

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

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

# dist[-i]:頂点Kから頂点iまでの距離
dist = [0 for i in range(N)]

def dfs(v, prv, ds):
    dist[-v] = ds
    for nxt, c in adj[-v]:
        if nxt != prv:
            dfs(nxt, v, ds + c)

dfs(K, None, 0)

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

Submission status: Runtime Error

Solution code:
N = int(input())

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

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

# dist[-i]:頂点Kから頂点iまでの距離
dist = [0 for i in range(N)]

def dfs(v, prv, ds):
    dist[-v] = ds
    for nxt, c in adj[-v]:
        if nxt != prv:
            dfs(nxt, v, ds + c)

dfs(K, None, 0)

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

Submission status: Runtime Error

Solution code:
N = int(input())
ABC = [tuple(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
XY = [tuple(map(int, input().split())) for i in range(Q)]

tree = [[] for i in range(N+1)]   
depth = [None] * (N+1)

for abc in ABC:
    tree[abc[0]].append((abc[1],abc[2]))
    tree[abc[1]].append((abc[0],abc[2]))
    
def DFS(v, p, d):
    depth[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFS(e[0], v, d + e[1])
            
DFS(K, 0, 0)

for i in range(Q):
    print(depth[XY[i][0]] + depth[XY[i][1]])

Submission status: Runtime Error

Solution code:
N = int(input())
ABC = [tuple(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
XY = [tuple(map(int, input().split())) for i in range(Q)]

tree = [[] for i in range(N+1)]   
depth = [None] * (N+1)

for abc in ABC:
    tree[abc[0]].append((abc[1],abc[2]))
    tree[abc[1]].append((abc[0],abc[2]))
    
def DFS(v, p, d):
    depth[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFS(e[0], v, d + e[1])
            
DFS(K, 0, 0)

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

Submission status: Runtime Error

Solution code:
N = int(input())
ABC = [tuple(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
XY = [tuple(map(int, input().split())) for i in range(Q)]

tree = [[] for i in range(N+1)]   
depth = [None] * (N+1)

for abc in ABC:
    tree[abc[0]].append((abc[1],abc[2]))
    tree[abc[1]].append((abc[0],abc[2]))
    
def DFS(v, p, d):
    depth[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFS(e[0], v, d + e[1])
            
DFS(K, 0, 0)

for xy in XY:
    print(depth[xy[0]] + depth[xy[1]])

Submission status: Runtime Error

Solution code:
N = int(input())
ABC = [tuple(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
XY = [tuple(map(int, input().split())) for i in range(Q)]

tree = [[] for i in range(N+1)]   
depth = [None] * (N+1)

for abc in ABC:
    tree[abc[0]].append((abc[1],abc[2]))
    tree[abc[1]].append((abc[0],abc[2]))
    
def DFS(v, p, d):
    depth[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFS(e[0], v, d + e[1])
            
DFS(K, -1, 0)

for xy in XY:
    print(depth[xy[0]] + depth[xy[1]])

Submission status: Runtime Error

Solution code:
N = int(input())

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

Q, K = [int (n) for n in input().split()]


def DFS(now, cost):
  costs[now] = cost
  for nx, cs in adj[now]:
    if costs[nx] == -1:
      DFS(nx, cost + cs)

DFS(K, 0)


for q in range(Q):
  x, y = [int(n) for n in input().split()]
  print(costs[x] + costs[y])

Submission status: Runtime Error

Solution code:
N = int(input())
abc = [[int(n) for n in input().split()] for i in range(N-1)]	
a,b,c = list(zip(*abc))
Q,K = map(int,input().split())
xy = [[int(l) for l in input().split()] for m in range(Q)]
x,y = list(zip(*xy))

l_rin = [[] for o in range(N)]
for m in range(N-1):
	l_rin[a[m]-1].extend([b[m]])
	l_rin[b[m]-1].extend([a[m]])

def search(top,bottom):
	keiro =[[top]]
	while len(keiro) > 0:
		path = keiro.pop(0)
		r = path[len(path)-1]		
		if r == bottom:
			return path
		else:
			for p in l_rin[r-1]:
				if p not in path:
					new_path = path[:]
					new_path.append(p)
					keiro.append(new_path)

def distance(fst,scd):
	dist = 0
	ppath = search(fst,scd)
	for pv in range(len(ppath) - 1):
		ppath_set = set(ppath[pv:pv+2])
		for pn in range(N-1):
			ab_set = set([a[pn],b[pn]])
			if ab_set == ppath_set:
				dist = dist + c[pn]
                                exit()
	return dist
			
for s in range(Q):
	print(distance(x[s],K) + distance(K,y[s]))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(50000)

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

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

Qn, K = list(map(int, input().split(" ")))

Q = []
for i in range(Qn):
    Q.append(list(map(int, input().split(" "))))

distance = [0]*(N+1)

def dfs(k, parent, dist):
    for n, x in M[k]:
        if n != parent:
            distance[n] = dist + x
            dfs(n, k, dist + x)

dfs(K, 0, 0)
for q in Q:
    print(distance[q[0]] + distance[q[1]])

Submission status: Runtime Error

Solution code:
N = int(input())
M = [[] for i in range(N+1)]

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

Qn, K = list(map(int, input().split(" ")))

Q = []
for i in range(Qn):
    Q.append(list(map(int, input().split(" "))))

distance = [0]*(N+1)

def dfs(k, parent, dist):
    for n, x in M[k]:
        if n != parent:
            distance[n] = dist + x
            dfs(n, k, dist + x)

dfs(K, 0, 0)
for q in Q:
    print(distance[q[0]] + distance[q[1]])

Submission status: Runtime Error

Solution code:
def dfs(v, p, d):
    distance[v] = d
    for tmp in G[v]:
        if tmp[0] == p:
            continue
        dfs(tmp[0], v, d + tmp[1])


if __name__ == '__main__':
    N = int(input())
    G = [[] for i in range(N)]
    for i in range(N - 1):
        # print(G)
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        G[a].append((b, c))
        G[b].append((a, c))

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

Submission status: Runtime Error

Solution code:
def dfs(v, p, d):
    distance[v] = d
    for tmp in G[v]:
        if tmp[0] == p:
            continue
        dfs(tmp[0], v, d + tmp[1])


if __name__ == '__main__':
    N = int(input())
    G = [[] for i in range(N + 1)]
    for i in range(N - 1):
        # print(G)
        a, b, c = list(map(int, input().split()))
        G[a].append((b, c))
        G[b].append((a, c))

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

Submission status: Runtime Error

Solution code:
def search_dist(g, dist, e):
    for b, c in g.get(e):
        if dist[b] is not None:
            continue
        dist[b] = dist[e] + c
        search_dist(g, dist, b)

def main():
    g = {}
    N = int(input())
    abc = []
    for _ in range(N-1):
        abc.append(list(map(int, input().split(' '))))
    for a, b, c in abc:
        g[a] = g.get(a, []) + [(b, c)]
        g[b] = g.get(b, []) + [(a, c)]
    Q, K = list(map(int, input().split(' ')))
    dist = [None]*(N+1)
    dist[K] = 0
    search_dist(g, dist, K)
    cood = []
    for _ in range(Q):
        cood.append(list(map(int, input().split(' '))))

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def search_dist(g, dist, e):
    for b, c in g.get(e):
        if dist[b] is not None:
            continue
        dist[b] = dist[e] + c
        search_dist(g, dist, b)

def main():
    g = {}
    N = int(input())
    for _ in range(N-1):
        a, b, c = list(map(int, input().split(' ')))
        g[a] = g.get(a, []) + [(b, c)]
        g[b] = g.get(b, []) + [(a, c)]
    Q, K = list(map(int, input().split(' ')))
    dist = [None]*(N+1)
    dist[K] = 0
    search_dist(g, dist, K)
    cood = []
    for _ in range(Q):
        cood.append(list(map(int, input().split(' '))))

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def search_dist(g, dist, e):
    for b, c in g.get(e):
        if dist[b] < 10**16:
            continue
        dist[b] = dist[e] + c
        search_dist(g, dist, b)

def main():
    g = {}
    N = int(input())
    for _ in range(N-1):
        a, b, c = list(map(int, input().split(' ')))
        g[a] = g.get(a, []) + [(b, c)]
        g[b] = g.get(b, []) + [(a, c)]
    Q, K = list(map(int, input().split(' ')))
    dist = [10**16]*(N+1)
    dist[K] = 0
    search_dist(g, dist, K)
    cood = []
    for _ in range(Q):
        cood.append(list(map(int, input().split(' '))))

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

if __name__ == '__main__':
    main()