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:
#!/usr/bin/env python3

import heapq
import sys


INF = sys.maxsize


def dijkstra(num_vertices, adj_list, source=0):
    dist = [INF for _ in range(num_vertices)]
    dist[source] = 0
    pq = [(dist[u], u) for u in range(num_vertices)]
    heapq.heapify(pq)
    while pq:
        _, u = heapq.heappop(pq)
        for v, cost in adj_list[u]:
            new_length = dist[u] + cost
            if new_length < dist[v]:
                dist[v] = new_length
                heapq.heappush(pq, (new_length, v))
    return dist


def main():
    n = int(input())
    adj_list = [set() for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = (int(z) for z in input().split())
        a -= 1
        b -= 1
        adj_list[a].add((b, c))
        adj_list[b].add((a, c))
    q, k = (int(z) for z in input().split())
    k -= 1
    dist = dijkstra(n, adj_list, k)
    for _ in range(q):
        x, y = (int(z) - 1 for z in input().split())
        res = dist[x] + dist[y]
        print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
g = []
d = [0] * (n + 1)
for i in range(n + 1):
    g.append([]);
for i in range(n - 1):
    u, v, w = map(int, input().split())
    g[u].append([v, w])
    g[v].append([u, w])
q, k = map(int, input().split())
def bfs(u):
    s = []
    s.append(u)
    while s:
        v = s[-1]
        s.pop()
        for go in g[v]:
            if not d[go[0]] and go[0] != u:
                d[go[0]] = d[v] + go[1]
                s.append(go[0])
bfs(k)
while q > 0:
    u, v = map(int, input().split())
    print(d[u] + d[v])
    q -= 1

Submission status: Accepted

Solution code:
from queue import Queue

INF=float('inf')

n=int(input())
g=[[] for _ in range(n)]
for _ in range(n-1):
    u,v,w=map(int,input().split())
    g[u-1].append((v-1,w))
    g[v-1].append((u-1,w))

q,k=map(int,input().split())
ds=[INF]*n
ds[k-1]=0
que=Queue()
que.put((k-1,0))
while not que.empty():
    u,d=que.get()
    for v,w in g[u]:
        if ds[v]==INF:
            ds[v]=d+w
            que.put((v,d+w))

for _ in range(q):
    u,v=map(int,input().split())
    print(ds[u-1]+ds[v-1])

Submission status: Accepted

Solution code:
n = int(input())
edge = [list(map(int, input().split())) for i in range(n-1)]
q, k = map(int, input().split())
query = [list(map(int, input().split())) for i in range(q)]

d = [0 for i in range(n+1)]
visited = [False for i in range(n+1)]
adj = [[] for i in range(n+1)]

for e in edge:
    adj[e[0]].append([e[1], e[2]])
    adj[e[1]].append([e[0], e[2]])
    
st = [k]
visited[k] = True
while st:
    u = st.pop()
    for p in adj[u]:
        v, w = map(int, p)
        if not visited[v]:
            visited[v] = True
            d[v] = d[u]+w
            st.append(v)

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

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
gr = { i:[] for i in range(1, n + 1)}
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    gr[a].append((b, c))
    gr[b].append((a, c))
q, k = map(int, input().split())
dmax = 10**14 + 1
dist = [dmax for _ in range(n + 1)]
dist[k] = 0
ls = deque([k])
while 0 < len(ls):
    u = ls.popleft()
    for v, c in gr[u]:
        if dist[v] == dmax:
            dist[v] = dist[u] + c
            ls.append(v)

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

Submission status: Accepted

Solution code:

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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
G=[[]for i in[0]*-~n]
for I in[lambda:map(int,input().split())]*~-n:a,b,c=I();G[a]+=(b,c),;G[b]+=(a,c),
q,k=I()
d=[0]*-~n
def f(v,p,u):
 d[v]=u
 for t,c in G[v]:p==t or f(t,v,u+c)
f(k,0,0)
for p in[print]*q:
 x,y=I()
 p(d[x]+d[y])

Submission status: Accepted

Solution code:
n=int(input())
e=[[] for i in range(n+1)]
for i in range(n-1):
 [a,b,c]=[int(j) for j in input().split()]
 e[a].append([b,c])
 e[b].append([a,c])
[q,k]=[int(j) for j in input().split()]
xy=[]
for i in range(q):
 xy.append([int(j) for j in input().split()])
def dfs(v,n):
    s=[]
    d=[-1 for i in range(n+1)]
    d[v]=0
    s.append(v)
    while len(s):
        v=s.pop()
        
        for i in e[v]:
            if d[i[0]]<0:
                d[i[0]]=d[v]+i[1]
                s.append(i[0])
    return d
d=dfs(k,n)
for i in range(q):
 print(d[xy[i][0]]+d[xy[i][1]])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
G=[[]for i in[0]*-~n]
for i in[0]*~-n:
    a,b,c=map(int,input().split())
    G[a]+=(b,c),
    G[b]+=(a,c),
q,k=map(int,input().split())
d=[0]*-~n
def f(v,p,u):
    d[v]=u
    for t,c in G[v]:
        if p!=t:f(t,v,u+c)
f(k,0,0)
for i in[0]*q:
    x,y=map(int,input().split())
    print(d[x]+d[y])

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
gr = { i:[] for i in range(1, n + 1)}
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    gr[a].append((b, c))
    gr[b].append((a, c))
q, k = map(int, input().split())
dmax = 10**14 + 1
dist = [dmax for _ in range(n + 1)]
dist[k] = 0
ls = deque([k])
while 0 < len(ls):
    u = ls[0]
    for v, c in gr[u]:
        if dist[v] == dmax:
            dist[v] = dist[u] + c
            ls.append(v)
    ls.popleft()

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

Submission status: Accepted

Solution code:
from queue import deque

n = int(input())
edges = [set() for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    edges[a].add((c, b))
    edges[b].add((c, a))
q, k = map(int, input().split())
stack = deque([(0, k)])
costs = [0] * (n + 1)
visited = set()
while stack:
    c, p = stack.popleft()
    costs[p] = c
    visited.add(p)
    stack.extend((c + c2, p2) for c2, p2 in edges[p] if p2 not in visited)

ans = []
for _ in range(q):
    x, y = map(int, input().split())
    ans.append(costs[x] + costs[y])
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
E = defaultdict(list)
W = dict()

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

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

costs = [float('inf')]*(N+1)
costs[K] = 0

stack = [K]

while stack:
  s = stack.pop()
  for t in E[s]:
    if costs[t] > costs[s] + W[(s,t)]:
      costs[t] = costs[s] + W[(s,t)]
      stack.append(t)

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

Submission status: Accepted

Solution code:
# coding: utf-8
from collections import defaultdict

INF = 10 ** 20
def II(): return int(input())
def ILI(): return list(map(int, input().split()))


def read():
    N = II()
    edges = defaultdict(list)
    for __ in range(N - 1):
        a, b, c = ILI()
        edges[a - 1].append((a - 1, b - 1, c)) # from, to, weight
        edges[b - 1].append((b - 1, a - 1, c))
    Q, K = ILI()
    query = [ILI() for __ in range(Q)]
    return N, edges, Q, K, query


def solve(N, edges, Q, K, query):
    K -= 1
    weight_from_k = [None] * N
    weight_from_k[K] = 0
    used = [False] * N
    used[K] = True
    queue = edges[K]
    while len(queue) != 0:
        next_queue = []
        for fro, to, weight in queue:
            if used[to]:
                continue
            weight_from_k[to] = weight_from_k[fro] + weight
            used[to] = True
            for e in edges[to]:
                next_queue.append(e)
        queue = next_queue

    ans = []
    for x, y in query:
        ans.append(weight_from_k[x - 1] + weight_from_k[y - 1])

    ans = "\n".join(map(str, ans))
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def dfs(now, par, d, dist, g):
    dist[now] = d
    for to, cost in g[now]:
        if to == par: continue
        dfs(to, now, d + cost, dist, g)


n = int(raw_input())
g = [[] for _ in xrange(n)]
for i in xrange(n - 1):
    a, b, c = map(int, raw_input().split())
    a -= 1; b -= 1
    g[a].append([b, c])
    g[b].append([a, c])
q, k = map(int, raw_input().split())
k -= 1
dist = [-1] * n
dfs(k, -1, 0, dist, g)
for i in xrange(q):
    x, y = map(int, raw_input().split())
    x -= 1; y -= 1
    print dist[x] + dist[y]

Submission status: Accepted

Solution code:
import sys  
sys.setrecursionlimit(200000)
n=int(raw_input())
tr=[[] for i in range(n)]
for i in range(n-1) :
  a,b,c=map(int,raw_input().split())
  a -= 1
  b -= 1
  tr[a].append((b,c))
  tr[b].append((a,c))
m,k=map(int,raw_input().split())
k -= 1
dis=[0 for i in range(n)]
def dfs(u,w=-1,l=0) :
  dis[u]=l
  for v,v1 in tr[u] :
    if v!=w :
      dfs(v,u,l+v1)
dfs(k)
for i in range(m) :
  x,y=map(int,raw_input().split())
  x-=1
  y-=1
  print dis[x]+dis[y]

Submission status: Accepted

Solution code:

from collections import defaultdict, deque


def bfs(graph, n, start):
    q = deque([start])

    dists = [-1] * (n+1)
    dists[start] = 0

    while q:
        cur = q.pop()

        for neigh, d in graph[cur].items():
            if dists[neigh] == -1:
                q.appendleft(neigh)
                dists[neigh] = dists[cur] + d

    return dists


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

    graph = defaultdict(dict)

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

    q, k = (int(x) for x in input().split())

    dists = bfs(graph, n, k)

    for _ in range(q):
        start, end = (int(x) for x in input().split())
        print(dists[start] + dists[end])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000001)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
g = []
for i in range(n+1): g.append([])

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

q,k = na()

def dfs(cur, pre, g, par, dw, w):
    dw[cur] = w
    par[cur] = pre
    for e in g[cur]:
        if e[0] != pre:
            dfs(e[0], cur, g, par, dw, w + e[1])

par = [-1] * (n+2)
dw = [-1] * (n+2)
dfs(k, -1, g, par, dw, 0)

for z in range(q):
    x, y = na()
    print(dw[x] + dw[y])

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
g = []
for i in range(n+1): g.append([])

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

q,k = na()

def dfs(cur, pre, g, par, dw, w):
    dw[cur] = w
    par[cur] = pre
    for e in g[cur]:
        if e[0] != pre:
            dfs(e[0], cur, g, par, dw, w + e[1])

par = [-1] * (n+2)
dw = [-1] * (n+2)
from queue import Queue
qs = Queue()
qs.put(k)
dw[k] = 0

while not qs.empty():
    cur = qs.get()
    for e in g[cur]:
        if e[0] != par[cur]:
            par[e[0]] = cur
            dw[e[0]] = dw[cur] + e[1]
            qs.put(e[0])


# dfs(k, -1, g, par, dw, 0)

for z in range(q):
    x, y = na()
    print(dw[x] + dw[y])

Submission status: Accepted

Solution code:
import heapq

def dijkstra(s,g,n):
    d=[float('inf')]*n
    d[s]=0
    pq=[]
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        if d[u]<t:
            continue
        for v,c in g[u]:
            if d[u]+c<d[v]:
                d[v]=d[u]+c
                heapq.heappush(pq,[d[v],v])
    return d

n = int(raw_input())
g = [[] for _ in xrange(n)]
for i in xrange(n - 1):
    a, b, c = map(int, raw_input().split())
    a -= 1; b -= 1
    g[a].append([b, c])
    g[b].append([a, c])
q, k = map(int, raw_input().split())
k -= 1
dist = dijkstra(k, g, n)
for i in xrange(q):
    x, y = map(int, raw_input().split())
    x -= 1; y -= 1
    print dist[x] + dist[y]

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
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())

dist = [10**18]*n
que = [(0, k-1)]
dist[k-1] = 0
while que:
    cost, v = heappop(que)
    if dist[v] < cost:
        continue
    for t, c in G[v]:
        if cost + c < dist[t]:
            dist[t] = cost + c
            heappush(que, (cost + c, t))
ans = []
for i in range(q):
    x, y = map(int, input().split())
    ans.append("%d" % (dist[x-1] + dist[y-1]))
print("\n".join(ans))

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
n = int(input())
adj = [[] for i in range(n+1)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    adj[a].append((b,c))
    adj[b].append((a,c))
qn, k = map(int,input().split())

from collections import deque
dist = [-1]*(n+1)
dist[k] = 0
Q = deque()
Q.append(k)
while len(Q):
    p = Q.popleft()
    for q,c in adj[p]:
        if dist[q] != -1: continue
        dist[q] = dist[p]+c
        Q.append(q)
for i in range(qn):
    x, y = map(int,input().split())
    print(dist[x]+dist[y])

Submission status: Runtime Error

Solution code:
N = int(input())

tree = {}

for _ in range(N-1):
  A, B, C = [int(i) for i in input().split()]
  if A not in tree:
    tree[A] = []
  if B not in tree:
    tree[B] = []
  tree[A].append((B, C))
  tree[B].append((A, C))


c = {}
q = []
visited = set()

def dfs(a, acc):
  c[a] = acc
  for n, cost in tree[a]:
    if n not in visited:
      visited.add(n)
      dfs(n, acc + cost)


Q, K = [int(i) for i in input().split()]
visited.add(K)
c[K] = 0
dfs(K, 0)

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

Submission status: Runtime Error

Solution code:
N = int(input())
a = [[] for _ in range(N + 1)]; b = [[] for _ in range(N + 1)]
for i in range(N - 1):
    p, q, r = list(map(int, input().split()))
    a[p].append([q, r]); a[q].append([p, r])
Q, K = map(int, input().split())
x = []; y = []
for i in range(Q):
    p, q = map(int, input().split())
    x.append(p); y.append(q)

depth = [0 for i in range(N + 1)]
def dfs(s,t,u):
    depth[s] = u
    for x in a[s]:
        if x[0] == t:
            continue
        dfs(x[0], s, u + x[1])

dfs(K, -1, 0)

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

Submission status: Runtime Error

Solution code:
N=int(input())
G=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    G[a].append([b,c])
    G[b].append([a,c])
Q,K=map(int,input().split())
K-=1
dist=[-1 for _ in range(N)]
dist[K]=0
def dfs(G,x,dist):
    for p in G[x]:
        if dist[p[0]]!=-1:
            continue
        dist[p[0]]=dist[x]+p[1]
        dfs(G,p[0],dist)

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

Submission status: Runtime Error

Solution code:
N = int(input())

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

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

def DFS(a, b, c):
    for i, j in graph[b]:
        if(i != a):
            visited[i] = c+j
            DFS(b, i, c+j)
DFS(-1, K-1, 0)
             
for _ in range(Q):
    x, y = map(int, input().split())
    print(visited[x-1]+visited[y-1])

Submission status: Runtime Error

Solution code:
N= int(input())

graph = {i+1:[] for i in range(N)}

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

def DFS(a, b, c):
    for i, j in graph[b]:
        if(i != a):
            visited[i] = c+j
            DFS(b, i, c+j)
DFS(-1, K, 0)
             
for i in range(Q):
    x, y = map(int, input().split())
    print(visited[x]+visited[y])

Submission status: Runtime Error

Solution code:
N= int(input())

graph = {i+1:[] for i in range(N)}

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

def DFS(a, b, c):
    for i, j in graph[b]:
        if(i != a):
            visited[i] = c+j
            DFS(b, i, c+j)
DFS(0, K, 0)
             
for i in range(Q):
    x, y = map(int, input().split())
    print(visited[x]+visited[y])

Submission status: Runtime Error

Solution code:
N=int(input())
tree=[[] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  tree[a-1].append((b-1,c))
  tree[b-1].append((a-1,c))
depth=[0 for i in range(N)]
def dfs(v,p,d):
  depth[v]=d
  for vv,dd in tree[v]:
    if vv==p:
      continue
    dfs(vv,v,d+dd)
Q,K=map(int,input().split())
dfs(K-1,-1,0)
for i 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())
to = [[] for _ in range(N)]

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

Q, K = map(int, input().split())
K -= 1
query = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(Q)]
depth = [0] * N


def dfs(v, d, p=-1):
    depth[v] = d
    for cost, nv in to[v]:
        if nv == p:
            continue
        dfs(nv, d + cost, v)


def main():
    dfs(K, 0)
    for x, y in query:
        print(depth[x] + depth[y])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
t = [[] for _ in range(n)]
for i in range(n-1):
  a,b,c = map(int,input().split())
  t[a-1].append((b-1,c))
  t[b-1].append((a-1,c))
q,k = map(int,input().split())
k -= 1
l = [0]*n
def dfs(a,b,c):
  for i,j in t[b]:
    if i != a:
      l[i] = c+j
      dfs(b,i,c+j)
dfs(-1,k,0)
for _ in range(q):
  x,y = map(lambda x:int(x)-1,input().split())
  print(l[x]+l[y])

Submission status: Runtime Error

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

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

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


D=[None]*(n+1)
 
def dfs(x,d):
    D[x]=d
    for yy,dd in G[x] :
        if D[yy] is not None:
            continue
        dfs(yy,dd+d)
dfs(k,0)

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

Submission status: Runtime Error

Solution code:
n = int(input())
 
def bellman_ford(s):
	d = [float('inf')]*10 # 各頂点への最小コスト
	d[s] = 0 # 自身への距離は0
	for i in range(10):
		update = False # 更新が行われたか
		for x, y, z in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				update = True
		if not update:
 			break
		# 負閉路が存在
		if i == 9:
			return -1
	return d

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

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

Submission status: Runtime Error

Solution code:
N =int(input())
#graph作成
graph = [[] for _ in range(N)]
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
query = [tuple(int(x) for x in input().split()) for _ in range(Q)]


def dfs(v, graph, seen, dist, distfromK):
    for next_v in graph[v]:
        if next_v[0] in seen:
            continue
        seen.append(next_v[0])
        ndist = dist + next_v[1]
        distfromK[next_v[0]] = ndist
        dfs(next_v[0], graph, seen, ndist, distfromK)


#dfs
seen = [K]
distfromK =[0] * N
dfs(K, graph, seen, 0, distfromK)

for q in query:
    print(distfromK[q[0]-1]+distfromK[q[1]-1])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
points = [list(map(int,input().split())) for _ in xrange(N-1)]
Q, K = map(int,input().split())
Query = [list(map(int,input().split())) for _ in xrange(Q)]

tree = [[0]*N for _ in xrange(N)]
for i in range(N-1):
    a = points[i][0] - 1
    b = points[i][1] - 1
    tree[a][b] = points[i][2]
    tree[b][a] = points[i][2]
def  bfs(u,q):
    queue = deque([u])
    cost = [None]*N
    cost[u] = 0
    while queue:
        v = queue.popleft()
        for i in xrange(N):
            if tree[v][i] != 0 and cost[i] == None:
                cost[i] =cost[v] + tree[v][i]
                queue.append(i)
    return cost[q]
answer = [0]*Q
for i in xrange(Q):
    answer[i] = bfs(Query[i][0]-1,K-1) + bfs(K-1,Query[i][1]-1)

for distance in answer:
    print(distance)

Submission status: Runtime Error

Solution code:
#coding: utf-8
from collections import defaultdict
import sys

N = int(input())

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

Q, K = (int(x) for x in input().split())

shortest_path = [-1] * (N+1)

def dfs(v, cost):
    if shortest_path[v] != -1 and shortest_path[v] <= cost:
        return

    shortest_path[v] = cost
    if v not in G:
        return
    if cost == -1:
        cost = 0 
    for next_v in G[v]:
        dfs(next_v, cost + G[v][next_v])

dfs(K, -1)

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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


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

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

    depth[0] = 0
    dfs(0)

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

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

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



if __name__ == "__main__":
    main()