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:
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(10000000)
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: Accepted

Solution code:
from collections import deque

n = int(input())
preroots = []
for i in range(n-1):    
    preroots.append(list(map(int,input().split())))

roots = [[] for i in range(n+1)]

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



QK = list(map(int,input().split()))
dist  = [-1 for i in range(n+1)]
dist[QK[1]] = 0
query = []
for i in range(QK[0]):
    query.append(list(map(int,input().split())))

q = deque()
q.append(QK[1])

while(len(q)):
    curr = q.popleft()
    for i in roots[curr]:
        if dist[i[0]] != -1:continue
        dist[i[0]] = dist[curr] + i[1]
        q.append(i[0])
        
for i in query:
    print(dist[i[0]] + dist[i[1]])

Submission status: Accepted

Solution code:
import sys;sys.setrecursionlimit(int(1e7))
from sys import stdin
from collections import deque
 
input = stdin.readline
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))
 
Qn,K = map(int,input().split())
XY = [tuple(map(int,input().split())) for _ in range(Qn)]
 
depth = [None]*(N+1)
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(Qn):
    print(depth[XY[i][0]] + depth[XY[i][1]])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ
# クラスをやめてベタ書きに
from heapq import heappush, heappop


# データの入力
N = int(input())
adj = [[] for _ in range(N+1)]
for i in range(N-1):
    f, t, c = [int(x) for x in input().split(' ')]
    adj[f].append((t, c))
    adj[t].append((f, c))

queries = []
Q, K = [int(x) for x in input().split(' ')]
for _ in range(Q):
    queries.append([int(x) for x in input().split(' ')])

# 経路の探索
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * (N+1)  # 各ノードの訪問状態
d = [float('inf')] * (N+1)  # 始点からの重み

# dijkstra
d[K] = 0
pq = [(0, K)]

while pq:
    cost, u = heappop(pq)
    color[u] = BLACK
    if d[u] < cost:
        continue

    for v, c in adj[u]:
        if color[v] == BLACK:
            continue
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(pq, (d[v], v))
            color[v] = GRAY

# 結果の表示
for x, y in queries:
    print(d[x] + d[y])

Submission status: Accepted

Solution code:
def BFS(K,edges,N):
  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)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  edges[a-1]+=[(b-1,c)]
  edges[b-1]+=[(a-1,c)]
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: Accepted

Solution code:
from sys import stdin
input = stdin.readline
def BFS(K,edges,N):
  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)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  edges[a-1]+=[(b-1,c)]
  edges[b-1]+=[(a-1,c)]
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: Accepted

Solution code:
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=[]
  que.append(K)
  while que:
    label=que.pop(-1)
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[(b-1,c)]
  path[b-1]+=[(a-1,c)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Submission status: Accepted

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 = [-1 for i in range(N)]
dist[-K] = 0

# 幅優先探索（キュー）
from collections import deque
queue = deque()
queue.append(K)

while queue:
    v = queue.popleft()
    for nxt, c in adj[-v]:
        if dist[-nxt] == -1:
            dist[-nxt] = dist[-v] + c
            queue.append(nxt)

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

Submission status: Accepted

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 = [-1 for i in range(N)]
dist[-K] = 0

# 深さ優先探索（スタック）
from collections import deque
stack = deque()
stack.append(K)

while stack:
    v = stack.pop()
    for nxt, c in adj[-v]:
        if dist[-nxt] == -1:
            dist[-nxt] = dist[-v] + c
            stack.append(nxt)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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 = [-1 for i in range(N)]
dist[-K] = 0

# 深さ優先探索（再帰）
def dfs(v):
    for nxt, c in adj[-v]:
        if dist[-nxt] == -1:
            dist[-nxt] = dist[-v] + c
            dfs(nxt)

dfs(K)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

Solution code:
from collections import deque 

n = int(input())

preroots = []
preroots_appd = preroots.append

for i in range(n-1):
    preroots_appd(list(map(int,input().split())))
    
roots = [[] for x in range(n+1)]

for i in preroots:
    roots[i[0]].append((i[1],i[2]))         
    roots[i[1]].append((i[0],i[2]))     
         
QK = list(map(int,input().split()))         
query = []

query_appd = query.append
for i in range(QK[0]):
    query_appd(list(map(int,input().split())))
        
    
distfrom_K = [-1 for x in range(n+1)]
distfrom_K[QK[1]] = 0          

q = deque()
q.append(QK[1])

while(len(q)):
    currentNode = q.popleft()
    for i in roots[currentNode]:
        if distfrom_K[i[0]] != -1:continue
        distfrom_K[i[0]] = distfrom_K[currentNode] + i[1]
        q.append(i[0])

for i in query:
    print(distfrom_K[i[0]]+distfrom_K[i[1]])

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

INF = 1e21

N = int(input())
Adj_list = defaultdict(set)

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

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

def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)] # (distance, v)の順。一般的にヒープは(key, 要素)のタプルをpush, popする。
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u] + c, v))
                
    return d

distance = dijkstra(N, K-1)

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

Submission status: Accepted

Solution code:
import sys;sys.setrecursionlimit(int(1e7))

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

Solution code:
from collections import deque 


n = int(input())
preroots = [[] for i in range(n-1)]
for i in range(len(preroots)):
    preroots[i] = list(map(int,input().split()))

roots = [[] for i in range(n+1)]
for i in preroots:
    roots[i[0]].append((i[1],i[2]))
    roots[i[1]].append((i[0],i[2]))
         
    
QK = list(map(int,input().split()))
query = [[] for i in range(QK[0])]
         
for i in range(QK[0]):
    query[i] = list(map(int,input().split()))
    
    
waylen = [-1 for i in range(n+1)]
waylen[QK[1]] = 0

q = deque()
q.append(QK[1])

while len(q):
    p = q.popleft()
    for i in roots[p]:
        if waylen[i[0]] != -1:continue
        waylen[i[0]] = i[1] + waylen[p]
        q.append(i[0])
        
for i in range(QK[0]):
    print(waylen[query[i][0]]+waylen[query[i][1]])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

Solution code:
import sys
from collections import deque

# sys.stdin = open('d1.in')


def main():
    n = int(input())
    adj = [[] for u 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))

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

    Q = deque([(k, 0, 0)])
    while Q:
        u, parent, dist = Q.popleft()
        Q.extend([(v, u, dist+w) for v, w in adj[u] if v != parent])
        d[u] = dist

    res = [0] * q
    for i in range(q):
        x, y = map(int, input().split())
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()

Submission status: Accepted

Solution code:
import sys
from collections import deque


# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


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


def read_str():
    return input()


def main():
    n = read_int()
    adj = [[] for u 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))

    d = [0] * (n+1)
    q, k = read_int_list()

    # Q = [(k, 0, 0)]
    Q = deque([(k, 0, 0)])
    while Q:
        u, parent, dist = Q.popleft()
        for v, w in adj[u]:
            if v != parent:
                Q.append((v, u, dist+w))
        d[u] = dist

    res = [0] * q
    for i in range(q):
        x, y = map(int, input().split())
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  import queue
  dist=[-1]*N
  dist[K]=0
  que=queue.Queue()
  que.put(K)
  while que.qsize():
    label=que.get()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que.put(i)
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[(b-1,c)]
  path[b-1]+=[(a-1,c)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while len(que):
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[(b-1,c)]
  path[b-1]+=[(a-1,c)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1].append((b-1,c))
  path[b-1].append((a-1,c))
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[(b-1,c)]
  path[b-1]+=[(a-1,c)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Submission status: Accepted

Solution code:
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[[b-1,c]]
  path[b-1]+=[[a-1,c]]
Q,K=map(int,input().split())
distance=BFS(K-1,path,N)
for i in range(Q):
  x,y=map(int,input().split())
  print(distance[x-1]+distance[y-1])

Submission status: Accepted

Solution code:
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[[b-1,c]]
  path[b-1]+=[[a-1,c]]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
from collections import deque
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[[b-1,c]]
  path[b-1]+=[[a-1,c]]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Submission status: Accepted

Solution code:
#coding=UTF-8

N=int(input())
a=[]
b=[]
c=[]

for idx in range(0,N-1,1):
    mozir=input()
    hyo=mozir.split(' ')
    a.append(int(hyo[0])-1)
    b.append(int(hyo[1])-1)
    c.append(int(hyo[2]))

mozir=input()
hyo=mozir.split(' ')
Q=int(hyo[0])
K=int(hyo[1])-1

#process
#first half
keiro=[]
for idx in range(0,N,1):
    keiro.append([])
    
for idx in range(0,N-1,1):
    keiro[a[idx]].append((b[idx],c[idx]))
    keiro[b[idx]].append((a[idx],c[idx]))

fare=[None]*N

fare[K]=0
shirabe=[(K,0)]
while shirabe :
    tugi_shirabe=[]
    for (node,tmpcost) in shirabe:
        for (kouho,c) in keiro[node]:
            if fare[kouho]==None:
                fare[kouho]=tmpcost+c
                tugi_shirabe.append((kouho,tmpcost+c))
                
    shirabe=tugi_shirabe

#print(fare)
#exit(0)
for idx in range(0,Q,1):
    mozir=input()
    hyo=mozir.split(' ')
    x=int(hyo[0])-1
    y=int(hyo[1])-1
    print(fare[x]+fare[y])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
nodes = []
for i in range(N - 1):
    tmp = input()
    nodes.append([int(a) for a in tmp.split()])
tmp = input()
M, top = [int(a) for a in tmp.split()]
querys = []
for i in range(M):
    tmp = input()
    querys.append([int(a) for a in tmp.split()])

#
#print(nodes, querys)
nodes_dic = [[] for i in range(N + 1)]
for n in nodes:
    frm, to, dist = n
    nodes_dic[frm].append([to, dist])
    nodes_dic[to].append([frm, dist])
#
# print(nodes_dic)
dist_dic = [-1 for i in range(N + 1)]
dist_dic[top] = 0
stack = [top]
while len(stack) > 0:
    n = stack.pop()
    for a in nodes_dic[n]:
        to, dist = a
        if dist_dic[to] >= 0:
            continue
        dist_dic[to] = dist_dic[n] + dist
        stack.append(to)
#
# print(dist_dic)
for q in querys:
    print(dist_dic[q[0]] + dist_dic[q[1]])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#幅優先探索
#TLE
import sys
from collections import deque

N=input()

a=[[] for i in range(N+1)]
#隣接リスト
for i in range(N-1):
	x,y,z=list(map(int,raw_input().split()))
	a[x].append((y,z))
	a[y].append((x,z))

#print a

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


b=[]
for i in range(Q):
	b.append(map(int, raw_input().split()))
#print b



#訪問判別フラグ
F=(N+1)*[0]

#Queue
q=deque()

#距離
dist=[0 for i in range(N+1)]


length=0
#幅優先探索
q.append(K)
while len(q)!=0:
	v=q.popleft()
	F[v]=1
	for u,length in a[v]:
		if F[u]==0:
			q.append(u)
			dist[u]=dist[v]+length


#print dist


for x in range(len(b)):
	print dist[ b[x][0] ]+ dist[ b[x][1] ]

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#深さ優先探索　再帰
#
import sys
sys.setrecursionlimit(200000)

N=input()


a=[[] for i in range(N+1)]

#隣接リスト
for i in range(N-1):
	x,y,z=list(map(int,raw_input().split()))
	a[x].append((y,z))
	a[y].append((x,z))

#print a
	

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


b=[]
for i in range(Q):
	b.append(map(int, raw_input().split()))
#print b



#訪問判別フラグ
F=(N+1)*[0]

#距離
dist=[0 for i in range(N+1)]

#深さ優先探索　再帰
#現在の頂点 v, v の親 p, スタート地点Kから現在の頂点vまでの距離 d
def dfs(v,p,d):
	F[v]=1
	dist[v]=d
	for i,j in a[v]:
		#頂点 v に隣接しているかつ未訪問 
		if F[i]==0:
			#DFS(次の頂点i, 次に親となる頂点v, d+ 頂点vと頂点iの間の辺のコスト)
			dfs(i,v,d+j)


dfs(K,-1,0)

for x in range(len(b)):
	print dist[ b[x][0] ]+ dist[ b[x][1] ]

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys


N=input()


a=[[] for i in range(N+1)]

#隣接リスト
for i in range(N-1):
	x,y,z=list(map(int,raw_input().split()))
	a[x].append((y,z))
	a[y].append((x,z))

#print a
	

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


b=[]
for i in range(Q):
	b.append(map(int, raw_input().split()))
#print b



#訪問判別フラグ
F=(N+1)*[0]

#Stack
S=[]

#距離
dist=[0 for i in range(N+1)]

#先頭から深さ優先探索
S.append(K)
former_v=0
v=0
while len(S) != 0:
	v=S.pop()
	
	if F[v]==0:
		F[v]=1

		for u,length in a[v]:
			if F[u]==0:
				S.append(u)
				dist[u]=dist[v]+length
				#print dist

#print dist



for x in range(len(b)):

	print dist[ b[x][0] ]+ dist[ b[x][1] ]

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e5+10))

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 i in range(N+1):
        g[i] = []
    for _ in range(N-1):
        a, b, c = list(map(int, input().split(' ')))
        g[a] += [(b, c)]
        g[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: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

tree = dict()
cost = dict()

N = int(input())
for i in range(N - 1):
    a, b, c = map(int, input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = []
        tree[a].append(b)
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = []
        tree[b].append(a)
    cost[(a, b)] = c
    cost[(b, a)] = c
starts = []
ends = []
Q, K = map(int, input().split())
for i in range(Q):
    x, y = map(int, input().split())
    starts.append(x)
    ends.append(y)

depth = [1000000000000000 for i in range(N)]

def dps(position, total_cost):
    if depth[position - 1] > total_cost:
        depth[position - 1] = total_cost
    for next_position in tree[position]:
        if depth[next_position - 1] == 1000000000000000:
            dps(next_position, depth[position - 1] + cost[(position, next_position)])

depth[K-1] = 0
dps(K, 0)

for start, end in zip(starts, ends):
    print(depth[start - 1] + depth[end - 1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e5+10))
N = int(input())
edge = [[] for i in range(N)]
depth = [0 for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append((b,c))
    edge[b].append((a,c))
Q, K = map(int, input().split())
K = K - 1

def dfs(v, p, c):
    depth[v] = c
    for nv, nc in edge[v]:
        if nv != p:
            dfs(nv, v, c + nc)
            
dfs(K, -1, 0)

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