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:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
 
sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**9
mod = 10**9 + 7
 
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
 
 
def main():
    n = I()
    e = collections.defaultdict(list)
    for _ in range(n-1):
        a,b,c = LI()
        e[a].append((b,c))
        e[b].append((a,c))
 
    # メソッドのみ版
    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True
 
            for uv, ud in e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))
 
        return d
 
    q,k = LI()
 
    d = search(k)
    r = []
    for _ in range(q):
        x,y = LI()
        r.append(d[x]+d[y])
 
    return '\n'.join(map(str,r))
 
 
 
print(main())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

depth = [0] * (n + 1)
def dfs(v, p, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to != p:
            dfs(to, v, d + cost)

q, k = map(int, input().split())
dfs(k, 0, 0)
xy = [tuple(map(int, input().split())) for i in range(q)]

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

Submission status: Accepted

Solution code:
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())
distance = [None] * n
distance[k-1] = 0
queue = [k-1]
while(len(queue)):
    p = queue.pop()
    for i,c in path[p]:
        if(distance[i] == None):
            distance[i] = distance[p] + c
            queue.append(i)

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))
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:
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)]

dist = [-1]*(N+1)
dist[K] = 0
Q = deque()
Q.append(K)
while len(Q):
    p = Q.popleft()
    for q,c in tree[p]:
        if dist[q] != -1: continue
        dist[q] = dist[p]+c
        Q.append(q)

for i in range(Qn):
    print(dist[XY[i][0]] + dist[XY[i][1]])

Submission status: Accepted

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

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

dist = [-1]*(N+1)
dist[K] = 0
Q = deque()
Q.append(K)
while len(Q):
    p = Q.popleft()
    for q,c in tree[p]:
        if dist[q] != -1: continue
        dist[q] = dist[p]+c
        Q.append(q)

for i in range(Qn):
    print(dist[XY[i][0]] + dist[XY[i][1]])

Submission status: Accepted

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

N = int(input())
ABC = [tuple(map(int,input().split())) for _ in range(N-1)]
Qn,K = map(int,input().split())
XY = [tuple(map(int,input().split())) for _ in range(Qn)]

tree = [[] for _ in range(N+1)]
for abc in ABC:
    tree[abc[0]].append((abc[1],abc[2]))
    tree[abc[1]].append((abc[0],abc[2]))

dist = [-1]*(N+1)
dist[K] = 0
Q = deque()
Q.append(K)
while len(Q):
    p = Q.popleft()
    for q,c in tree[p]:
        if dist[q] != -1: continue
        dist[q] = dist[p]+c
        Q.append(q)

for i in range(Qn):
    print(dist[XY[i][0]] + dist[XY[i][1]])

Submission status: Accepted

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

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

tree = [[] for _ 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: Accepted

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

N = int(input())
ABC = [list(map(int,input().split())) for _ in range(N-1)]
Q,K = map(int,input().split())
XY = [list(map(int,input().split())) for _ in range(Q)]

tree = [[] for _ 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: Accepted

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

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

tree = [[] for _ in range(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):
    tree[v][0].append(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(tree[XY[i][0]][0][2] + tree[XY[i][1]][0][2])

Submission status: Accepted

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

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

tree = [[] for _ in range(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):
    for e in tree[v]:
        e.append(d)
        if e[0] != p:
            DFS(e[0], v, d + e[1])

DFS(K,0,0)

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

Submission status: Accepted

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

N = int(input())

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

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

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

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

class edge():
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

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

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

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to == p:
            continue
        DFS(e.to, v, d + e.cost)
DFS(K,-1,0)

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**9
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    e = collections.defaultdict(list)
    for _ in range(n-1):
        a,b,c = LI()
        e[a].append((b,c))
        e[b].append((a,c))

    # メソッドのみ版
    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    q,k = LI()

    d = search(k)
    r = []
    for _ in range(q):
        x,y = LI()
        r.append(d[x]+d[y])

    return '\n'.join(map(str,r))



print(main())

Submission status: Accepted

Solution code:
import heapq
N = int(input())
es = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))
Q,K = map(int, input().split())
K -= 1

INF = float('inf')
ds = [INF for i in range(N)]
ds[K] = 0
visited = [0 for i in range(N)]
q = [K]
heapq.heapify(q)
while q:
    now = heapq.heappop(q)
    visited[now] = 1
    for to,cost in es[now]:
        ds[to] = min(ds[to], ds[now]+cost)
        if visited[to]: continue
        heapq.heappush(q,to)

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

Submission status: Accepted

Solution code:
import collections

def bfs(tree, s, distance):
    queue = collections.deque([s])
    distance[s] = 0

    while queue:
        v = queue.popleft()
        v_c = distance[v]
        for node, cost in tree[v]:
            if distance[node] == -1:
                distance[node] = v_c + cost
                queue.append(node)

N = int(input())

Tree = collections.defaultdict(list)

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

distance = collections.defaultdict(lambda : -1)
bfs(Tree, k, distance)

for i in range(q):
    x, y = map(int, input().split())
    print(distance[x] + distance[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 asyncio import Queue
qs = Queue()
qs.put_nowait(k)
dw[k] = 0

while not qs.empty():
    cur = qs.get_nowait()
    for e in g[cur]:
        if e[0] != par[cur]:
            par[e[0]] = cur
            dw[e[0]] = dw[cur] + e[1]
            qs.put_nowait(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:
def Q4(x):
    N = x[0][0]  # 木の頂点数
    edge = x[1:N][:]  # 辺とその距離
    Q = x[N][0]  # クエリ数
    K = x[N][1]  # 経由すべき頂点の番号
    query = x[N + 1:][:]  # クエリの内容

    # 木の初期化
    tree = list(range(N))  # adjacent(隣接)のほうがいいかな？
    for idx in range(N):
        tree[idx] = []

    for idx in range(len(edge)):
        # i番目の要素は、節点iに接続されている節点
        # これ以降、-1を足すのは、頂点の添字が1スタートに対しリストは0スタートのため
        a = edge[idx][0] - 1
        b = edge[idx][1] - 1
        c = edge[idx][2]
        tree[a].append([b, c])
        tree[b].append([a, c])

    # Kから各節点への距離を求める
    dist = [0 for i in range(N)]  # 頂点Kからの距離
    isVisit = [False for i in range(N)]  # ある頂点が探索済か
    queue = [K - 1] #幅探索用キュー
    isVisit[K - 1] = True

    while queue:
        u = queue.pop()
        for p in tree[u]:
            v, w = map(int, p)
            if not isVisit[v]:
                isVisit[v] = True
                dist[v] = dist[u] + w
                queue.append(v)

    for q in query:
        print(dist[q[0] - 1] + dist[q[1] - 1])
        
N=int(input())
edge = [[int(i) for i in input().split()] for i in range(N-1)]
Q , K = (int(i) for i in input().split())
query = [[int(i) for i in input().split()] for i in range(Q)]
l = [[N]]+edge+[[Q,K]]+query
Q4(l)

Submission status: Accepted

Solution code:
import sys
x = input()
d = {}
dist = {}
for i in range(1, x+1):
    d[i] = []
    dist[i] = 0
for i in range(x-1):
    num1, num2, num3 = map(int, sys.stdin.readline().split())
    d[num1].append((num2, num3))
    d[num2].append((num1, num3))

q, k = map(int, raw_input().split())
vis = set()
vis.add(k)
current = [k]
newnode = []
while True:
    for i in range(len(current)):
        for j in range(len(d[current[i]])):
            if d[current[i]][j][0] not in vis:
                dist[d[current[i]][j][0]] = dist[current[i]]+d[current[i]][j][1]
                vis.add(d[current[i]][j][0])
                newnode.append(d[current[i]][j][0])
    if len(newnode) == 0:
        break
    current = []
    current = newnode
    newnode = []

for i in range(q):
    num1, num2 = map(int, sys.stdin.readline().split())
    hold = 0
    hold1 =0
    print dist[num1] + dist[num2]

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(int(1e7))

def dfs(node, parent, distance):
    depth[node] = distance
    for next_node, cost in Tree[node]:
        if next_node != parent:
            dfs(next_node, node, distance + cost)

N = int(input())

Tree = collections.defaultdict(list)

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

depth = {}
dfs(k, -1, 0)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
n=int(input())
g=[[] for _ in range(n)]
for _ 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())
d=[-1]*n
def f(k,c):
    d[k]=c
    for i,v in g[k]:
        if d[i]==-1:
            f(i,c+v)
f(k-1,0)
for _ in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Submission status: Accepted

Solution code:
import queue
n=int(input())
r=[[] for i in range(n)]
d=[[] for i in range(n)]

for i in range(n-1):
    line=input().split()
    a=int(line[0])-1
    b=int(line[1])-1
    c=int(line[2])
    r[a].append(b)
    r[b].append(a)
    d[a].append(c)
    d[b].append(c)

line=input().split()
q=int(line[0])
k=int(line[1])-1

dist=[-1 for i in range(n)]

qd=queue.Queue()
qn=queue.Queue()
qd.put(0)
qn.put(k)

while not qn.empty():
    dd=qd.get()
    nn=qn.get()
    dist[nn]=dd
    for i in range(len(r[nn])):
        if dist[r[nn][i]]!=-1:
            continue
        qd.put(dd+d[nn][i])
        qn.put(r[nn][i])

for i in range(q):
    line=input().split()
    x=int(line[0])-1
    y=int(line[1])-1
    print(dist[x]+dist[y])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    ai, bi, ci = map(int, input().split())
    edges[ai].append((bi, ci))
    edges[bi].append((ai, ci))
Q, K = map(int, input().split())

distance = [-1]*(N+1)
# def add_weight(k, pre):
#     for v in edges[k]:
#         d, w = v
#         if d != pre:
#             distance[d] = w + distance[k]
#             add_weight(d, k)
# add_weight(K, -1)
que = deque()
que.append(K); distance[K] = 0
while len(que):
    a = que.popleft()
    for b, c in edges[a]:
        if distance[b] == -1:
            distance[b] = c + distance[a]
            que.append(b)

# print(distance)

for _ in range(Q):
    s, e = map(int, input().split())
    print(distance[s] + distance[e])

Submission status: Accepted

Solution code:
N = int(input())
g = {i: [] for i in range(1, N+1)}    

l = [0] * (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())

stack = [K]

while len(stack):
    v = stack.pop()
    for c,ln in g[v]:
        if l[c] != 0:
            continue
        l[c] = l[v] + ln
        stack.append(c)

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

Submission status: Accepted

Solution code:
n = int(input())
edges = [[] for _ in range(n + 1)]
for a, b, c in (map(int, input().split()) for _ in range(n - 1)):
    edges[a].append((c, b))
    edges[b].append((c, a))
q, k = map(int, input().split())
stack = [(0, k, None)]
costs = [0] * (n + 1)
while stack:
    c, p, a = stack.pop()
    costs[p] = c
    stack.extend((c + c2, p2, p) for c2, p2 in edges[p] if p2 != a)
print('\n'.join(map(str, (costs[x] + costs[y] for x, y in (map(int, input().split()) for _ in range(q))))))

Submission status: Accepted

Solution code:
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 = [(0, k, None)]
costs = [0] * (n + 1)
while stack:
    c, p, a = stack.pop()
    costs[p] = c
    stack.extend((c + c2, p2, p) for c2, p2 in edges[p] if p2 != a)

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

Submission status: Accepted

Solution code:
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 = [(0, k, None)]
costs = [0] * (n + 1)
visited = set()
while stack:
    c, p, a = stack.pop()
    costs[p] = c
    visited.add(p)
    stack.extend((c + c2, p2, p) for c2, p2 in edges[p] if p2 != a)

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

Submission status: Accepted

Solution code:
def dfs():
    sta = []
    ans = [-1]*(N+1)

    sta.append(K)
    ans[K] = 0

    while sta:
        nod = sta.pop()
        for t, d in tree[nod]:
            if ans[t] < 0:
                ans[t] = ans[nod] + d
                sta.append(t)

    return ans


N = int(input())
tree = [[] for i in range(N+1)]
for i 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())
dis = dfs()

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

Submission status: Accepted

Solution code:
I=lambda:map(int,input().split());n,=I();G=[[]for i in[0]*-~n]
for i in G[2:]:a,b,c=I();G[a]+=(b,c),;G[b]+=(a,c),
q,k=I();s=[(k,0,0)]
while s:v,p,u=s.pop();s+=[(t,v,u+c)for t,c in G[v]if p-t];G[v]=u
for p in[0]*q:x,y=I();print(G[x]+G[y])

Submission status: Accepted

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

n = raw_input()
n = int(n)

tree = []
for i in range(n):
    tree.append([])

for i in range(n-1):
    abc = raw_input()
    abc = abc.split()
    abc = map(int, abc)
    tree[abc[0]-1].append([abc[1]-1,abc[2]])
    tree[abc[1]-1].append([abc[0]-1,abc[2]])


qk = raw_input()
qk = qk.split()
q,k = map(int,qk)

question = []
for i in range(q):
    xy = raw_input()
    xy = xy.split()
    xy = map(int,xy)
    question.append(xy)

distance = []
for i in range(n):
    distance.append(-1)

distance[k-1] = 0

next_point = [k-1]

while 1:
    search_point = next_point
    next_point = []
    if len(search_point) == 0:
        break
    else:
        for i in search_point:
            for j in tree[i]:
                if distance[j[0]] == -1:
                    distance[j[0]] = distance[i] + j[1]
                    next_point.append(j[0])

for line in question:
    print distance[line[0]-1] + distance[line[1]-1]

Submission status: Accepted

Solution code:
# Transit Tree Path

N = int(input())
p =[]
for i in range(N-1):
    p.append(list(map(int, input().split())))
Q,K = list(map(int, input().split()))
r = []
for i in range(Q):
    r.append(list(map(int, input().split())))

#隣接行列
adj = [[] for i in range(N+1)]
for pi in p:
    adj[pi[0]].append((pi[1],pi[2]))
    adj[pi[1]].append((pi[0],pi[2]))
adj


from collections import deque #decue使う
dist = [-1]*(N+1) #距離リスト
dist[K] = 0 #頂点Kからの距離は0
d = deque() #探索済みのリスト
d.append(K)
while len(d):
    pp = d.popleft() #探索中の頂点
    for q,c in adj[pp]:
        if dist[q] != -1:
            continue
        dist[q] = dist[pp]+c
        d.append(q)
for i in range(Q):
    x, y = r[i]
    print(dist[x]+dist[y])

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
g = [[] for i in range(n + 1)]

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

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

d = [-1] * (n + 1)
d[k] = 0
pq = deque()
pq.append(k)
while len(pq):
    u = pq.popleft()
    for v, w in g[u]:
        if d[v] != -1: continue
        d[v] = d[u] + w
        pq.append(v)

for i in range(q):
    u, v = [int(x) for x in input().split()]
    print(d[u] + d[v])

Submission status: Accepted

Solution code:

N = int(input())
E = [[] for _ in range(N)]

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

Q,K = map(int,input().split())
K -= 1
costs = [None]*N
costs[K] = 0

stack = [K]

while stack:
  s = stack.pop()
  c = costs[s]
  for t,d in E[s]:
    if costs[t] is None:
      costs[t] = c + d
      stack.append(t)

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

Submission status: Accepted

Solution code:

import sys
from collections import deque
import copy

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

#class edge:
#    def __init__(x, y, cost):

class point_node:
    def __init__(self, point, cost):
        self.point = point
        self.cost = cost

def  BFS(con_list, start_point):
    cost_list = {}
    cost_list[start_point] = 0

    node_list = deque([point_node(start_point, 0)])
    while 1:
        #new_node_list = []
        #for i in range(len(node_list)):
        now_node = node_list.popleft()
        connects = con_list[now_node.point]
        for c in connects:
            if c[0] not in cost_list:
                cost_list[c[0]] = c[1] + now_node.cost
                node_list.append(point_node(c[0], c[1] + now_node.cost))
        if len(node_list) == 0:
            break
        #node_list = copy.deepcopy(new_node_list)

    return cost_list


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    pass_dict = {}
    for i in range(N - 1):
        input_raw = read_func().strip().split()
        [a, b, c] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
        if a not in pass_dict:
            pass_dict[a] = []
        pass_dict[a].append((b, c))
        if b not in pass_dict:
            pass_dict[b] = []
        pass_dict[b].append((a, c))

    input_raw = read_func().strip().split()
    [Q, K] = [int(input_raw[0]), int(input_raw[1])]

    cost_list = BFS(pass_dict, K)

    for i in range(Q):
        input_raw = read_func().strip().split()
        [x, y] = [int(input_raw[0]), int(input_raw[1])]
        print cost_list[x] + cost_list[y]


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections
import sys
sys.setrecursionlimit(int(1e7))

def dfs(n, pre, T, dist, d) :
	dist[n] = d
	for i in T[n] :
		if i[0] != pre :
			dfs(i[0], n, T, dist, d + i[1])


N = int(input())
T = collections.defaultdict(lambda : [])
for i in range(N-1) :
	a, b, c = map(int, input().split())
	T[a].append((b, c))
	T[b].append((a, c))
Q, K = map(int, input().split())

d = {}
dfs(K, -1, T, d, 0)

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

Submission status: Accepted

Solution code:
n=int(input())-1

edges = {}
lens = {}
for _ in range(n):
    [a, b, c] = map(int, input().split())
    if a > b:
        a,b=b,a
    edges.setdefault(a, []).append(b)
    edges.setdefault(b, []).append(a)
    lens[(a,b)] = c

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

dists = {}
def build(x, d=0):
    ss = [(x, 0)]
    while ss:
        x, d = ss.pop()
        if x not in dists:
            dists[x] = d
            for c in edges.get(x, []):
                ss.append((c, d + lens[(min(x,c), max(x,c))]))

build(k)

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

Submission status: Accepted

Solution code:
# encoding:utf-8
import sys
 
def main():
	n = int(input())
	vers = [list(map(int, input().split())) for _ in range(n - 1)]
	q, k = list(map(int, input().split()))
	queries = [list(map(int, input().split())) for _ in range(q)]
 
	#n = 10 ** 5
	#vers = [[i + 1, i + 2, 10 ** 9] for i in range(n - 1)]
 
	new_vers = mapping(n, vers)
	dist = calcMinDist(n, new_vers, k, queries)
	calcQueries(dist, queries, k)
	
def mapping(n, vers):
	new_vers = {i :[] for i in range(n)}
	for ver in vers:
		new_vers[ver[0] - 1].append((ver[1], ver[2]))
		new_vers[ver[1] - 1].append((ver[0], ver[2]))
	return new_vers
 
def calcMinDist(n, new_vers, k, queries):
	dist = [- 1 for _ in range(n)]
	flag = [False for _ in range(n)]
	dist[k - 1] = 0
	flag[k - 1] = True
	dfs(new_vers, dist, flag, k)
	return dist
 
def dfs(new_vers, dist, flag, frm):
	flag[frm - 1] = True
	vs = new_vers[frm - 1]
	for v in vs:
		if flag[v[0] - 1] == False:
			dist[v[0] - 1] = dist[frm - 1] + v[1]
			new_ver, dist, flag, _ = dfs(new_vers, dist, flag, v[0])
 
	return [new_vers, dist, flag, frm]
 
def calcQuery(dist, query, k):
	print(dist[query[0] - 1] + dist[query[1] - 1])
 
def calcQueries(dist, queries, k):
	for query in queries:
		calcQuery(dist, query, k)
 
if __name__ == '__main__':
	sys.setrecursionlimit(1000000)
	main()

Submission status: Accepted

Solution code:
from collections import deque

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
que=deque([(k-1,0)])
while len(que):
    u,d=que.popleft()
    if ds[u]!=INF:
        continue
    ds[u]=d
    for v,w in g[u]:
        que.append((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:
from collections import deque

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=deque()
que.append((k-1,0))
while len(que):
    u,d=que.popleft()
    for v,w in g[u]:
        if ds[v]==INF:
            ds[v]=d+w
            que.append((v,d+w))

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