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 heapq


def dijkstra(K):
    c_l = [float('inf')] * N
    c_l[K] = 0
    hq = [(K, 0)]
    while hq:
        u = heapq.heappop(hq)[0]
        for nv, c in adj_list[u]:
            if c_l[nv] > c_l[u] + c:
                c_l[nv] = c_l[u] + c
                heapq.heappush(hq, (nv, c_l[nv]))
    return c_l


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

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

Q, K = map(int, input().split())
c_l = dijkstra(K - 1)

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

Submission status: Accepted

Solution code:
import heapq


def dijkstra(K):
    c_l = [float('inf')] * N
    c_l[K] = 0
    hq = [(0, K)]
    while hq:
        u = heapq.heappop(hq)[1]
        for nv, c in adj_list[u]:
            if c_l[nv] > c_l[u] + c:
                c_l[nv] = c_l[u] + c
                heapq.heappush(hq, (c_l[u] + c, nv))
    return c_l


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

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

Q, K = map(int, input().split())
c_l = dijkstra(K - 1)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

cost = [-1]*N
def calc(i,c):
    # 指定の頂点までのコストを代入
    cost[i] = c
    # 頂点から移動できる頂点があれば
    for ni,nc in X[i]:
        # 初期状態のままなら計算
        if cost[ni] == -1:
            calc(ni,c+nc)

Q,K = map(int,input().split())
# 事前計算
calc(K-1,0)

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
g = [[] for _ in range(0,N+1)]
for i in range(0,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())
xy = []
for i in range(0,Q):
    x,y = map(int,input().split())
    xy.append((x,y))

d = [-1 for _ in range(0,N+1)]
d[K] = 0
queue = deque([[K,g[K]]])
while queue:
    start,edge = queue.popleft()
    for to,cost in edge:
        if d[to] != -1:
            continue
        d[to] = d[start] + cost
        queue.append((to,g[to]))

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

Submission status: Accepted

Solution code:
N = int(input())
abc = [[int(_) for _ in input().split()] for i in range(N - 1)]
Q, K = [int(_) for _ in input().split()]
xy = [[int(_) for _ in input().split()] for i in range(Q)]

from collections import defaultdict
from heapq import *

V = list(range(1, N + 1))
E = defaultdict(lambda:{})
for a, b, c in abc:
    E[a][b] = c
    E[b][a] = c

def Dijkstra(s, V, E):
    # https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95
    d = defaultdict(lambda:10**20)
    prev = defaultdict(lambda:None)
    d[s] = 0
    Q = []
    for v in V:
        heappush(Q, (d[v], v))
    while Q:
        x, u = heappop(Q)
        for v, y in E[u].items():
            alt = d[u] + y
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heappush(Q, (alt, v))
    return d, prev

d, prev = Dijkstra(K, V, E)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])


def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)


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

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
N = int(input())
table=[[]for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    table[a-1].append([b-1,c])
    table[b-1].append([a-1,c])
Q,K=map(int,input().split())
Que=[[int(i) for i in input().split()] for i in range(Q)]
inf=10**17
dis=[inf]*N
dis[K-1]=0
kei=[]
heappush(kei,[0,K-1])
while kei:
    q,x=heappop(kei)
    if dis[x]<q:
        continue
    for i,d in table[x]:
        if dis[x]+d<dis[i]:
            dis[i]=dis[x]+d
            heappush(kei,[dis[i],i])
ans =[]
for x,y in Que:
    ans.append(dis[x-1]+dis[y-1])
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
def getDis(k, abc, n):
    r = [[] for i in range(n)]
    for a, b, c in abc:
        r[a-1] += [(b-1, c)]
        r[b-1] += [(a-1, c)]
    dis = [-1] * n
    stack = [k]
    dis[k] = 0
    while stack:
        label = stack.pop(-1)
        for i, c in r[label]:
            if dis[i] == -1:
                dis[i] = dis[label] + c
                stack.append(i)
    return dis


N = int(input())
abc = [[int(i) for i in input().split()] for i in range(N-1)]
Q, K = map(int, input().split())
xy = [[int(i) for i in input().split()] for i in range(Q)]
d = getDis(K-1, abc, N)
for i in range(Q):
    print(d[xy[i][0] - 1] + d[xy[i][1] - 1])

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

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

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

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    treedic = {}
    for i in range(1, N+1):
        treedic[i] = {}
    for i in range(N-1):
        a, b, c = map(int, input().split())
        treedic[a][b] = c
        treedic[b][a] = c

    Q, K = map(int, input().split())
    checked = set([K])
    length = [0]*(N+1)
    check = set([K])

    while len(checked) < N:
        nextcheck = set()
        for i in check:
            for j in treedic[i].keys():
                if j not in checked:
                    length[j] = length[i] + treedic[i][j]
                    checked.add(j)
                    nextcheck.add(j)
        check = nextcheck

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import queue
N=int(input())
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
c=[0 for i in range(N-1)]
VL=[dict() for i in range(N)]
for i in range(N-1):
    a[i],b[i],c[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1
    VL[a[i]][b[i]]=c[i]
    VL[b[i]][a[i]]=c[i]
Q,K=map(int,input().split())
K-=1
x=[0 for i in range(Q)]
y=[0 for i in range(Q)]
for i in range(Q):
    x[i],y[i]=map(int,input().split())
    x[i]-=1
    y[i]-=1
reached=[False for i in range(N)]
dist=[0 for i in range(N)]
q=queue.Queue()
q.put(K)
reached[K]=True
while(not(q.empty())):
    r=q.get()
    for v in VL[r]:
        if not(reached[v]):
            q.put(v)
            dist[v]=VL[r][v]+dist[r]
            reached[v]=True
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])

Submission status: Accepted

Solution code:
n = int(input())
a = [[int(i) for i in input().split()] for i in range(n-1)]
q,k = (int(i) for i in input().split())
question = [[int(i) for i in input().split()] for i in range(q)]
x,ans = [[] for i in range(n)],[False for i in range(n)]
for i in a:
	x[i[0]-1].append([i[1],i[2]])
	x[i[1]-1].append([i[0],i[2]])
visit = [False for i in range(n)]
visit[k-1],now = True,[k]
while now:
	p = now.pop()
	for i in x[p-1]:
		if not visit[i[0]-1]:
			visit[i[0]-1],ans[i[0]-1] = True,ans[p-1]+i[1]
			now.append(i[0])
for i in question:
	print(ans[i[0]-1]+ans[i[1]-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
def inpl(): return map(int, input().split())
N = int(input())

G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = inpl()
    G[a].append([b, c])
    G[b].append([a, c])

Q, K = inpl()

def BFS(G, K):
    DQ = deque([K])
    D = [-1] * (N+1)
    D[K] = 0
    while DQ:
        p = DQ.popleft()
        for q, c in G[p]:
            if D[q] != -1:
                continue
            D[q] = D[p] + c
            DQ.append(q)
    return D

D = BFS(G, K)
for _ in range(Q):
    x, y = inpl()
    print(D[x] + D[y])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
def inpl(): return map(int, input().split())
N = int(input())

G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = inpl()
    G[a].append([b, c])
    G[b].append([a, c])

Q, K = inpl()

def BFS(G, K):
    DQ = deque([K])
    D = [-1] * (N+1)
    D[K] = 0
    while DQ:
        p = DQ.popleft()
        for q, c in G[p]:
            if D[q] == -1:
                D[q] = D[p] + c
                DQ.append(q)
    return D

D = BFS(G, K)
for _ in range(Q):
    x, y = inpl()
    print(D[x] + D[y])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
def inpl(): return map(int, input().split())
N = int(input())

G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = inpl()
    G[a].append((b, c))
    G[b].append((a, c))

Q, K = inpl()

def BFS(G, K):
    DQ = deque([K])
    D = [0] * (N+1)
    visited = [False]*(N+1)
    while DQ:
        p = DQ.popleft()
        visited[p] = True
        for q, c in G[p]:
            if not visited[q]:
                D[q] = D[p] + c
                DQ.append(q)
    return D

D = BFS(G, K)
for _ in range(Q):
    x, y = inpl()
    print(D[x] + D[y])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
def inpl(): return map(int, input().split())
N = int(input())

G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = inpl()
    G[a].append((b, c))
    G[b].append((a, c))

D = [0] * (N+1)
Q, K = inpl()
DQ = deque([K])
visited = [False]*(N+1)

while DQ:
    p = DQ.popleft()
    visited[p] = True
    for q, c in G[p]:
        if not visited[q]:
            D[q] = D[p] + c
            DQ.append(q)

for _ in range(Q):
    x, y = inpl()
    print(D[x] + D[y])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
def inpl(): return map(int, input().split())
N = int(input())

G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = inpl()
    G[a].append((b, c))
    G[b].append((a, c))

D = [0] * (N+1)
Q, K = inpl()
DQ = deque([[K, 0]])
visited = [False]*(N+1)

while DQ:
    p, c = DQ.popleft()
    D[p] = c
    visited[p] = True
    for q, d in G[p]:
        if not visited[q]:
            DQ.append([q, c+d])

for _ in range(Q):
    x, y = inpl()
    print(D[x] + D[y])

Submission status: Accepted

Solution code:
def d_transit_tree_path(N, E, Q, K, V):
    # 頂点数、辺とそのコスト、クエリの数、経由する頂点、出発/到達頂点

    # 隣接リストの作成
    edge = [[] for _ in range(N)]
    for a, b, c in E:
        edge[a - 1].append([b - 1, c])
        edge[b - 1].append([a - 1, c])

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

    while queue:
        u = queue.pop()
        for v, c in edge[u]:
            if not is_visit[v]:
                is_visit[v] = True
                dist[v] = dist[u] + c
                queue.append(v)

    ans = ''
    for q1, q2 in V:
        ans += '{}\n'.format(dist[q1 - 1] + dist[q2 - 1])
    ans = ans[:-1]
    return ans

N = int(input())
E = [[int(i) for i in input().split()] for j in range(N-1)]
Q,K = [int(i) for i in input().split()]
V = [[int(i) for i in input().split()] for j in range(Q)]
print(d_transit_tree_path(N, E, Q, K, V))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

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

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

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

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

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

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

def dijkstra(n,v):
  d=[float('inf')]*n
  d[v]=0
  
  hq=[(0,v)]
  
  while hq:
    u = heapq.heappop(hq)[1]
    for nv,c in V[u]:
      if d[nv]>d[u]+c:
        d[nv]=d[u]+c
        heapq.heappush(hq,(d[u]+c,nv))
        
  return d

ans=dijkstra(N,K-1)

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

Submission status: Accepted

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

def dfs(k, path, n):
    """連結情報path,頂点の個数Nが与えられたとき
    頂点Kから各頂点までの距離をlistで返す"""
    from collections import deque # deque(),popleft()
    dist = [-1] * n
    dist[k] = 0
    que = deque([])
    que.append(k)
    while que:
        label = que.popleft()
        for i,c in path[label]: # 頂点labelと連結している頂点iと距離c
            if dist[i] == -1:
                dist[i] = dist[label] + c
                que += [i] # 次に調べる頂点に
    return dist

n = int(input())
path = [[] for i in range(n)]
# path = [{1,2}] * 3
# print(path)
for i in range(n-1):
    a, b, c = map(int, input().split())
#     print(a,b,c)
    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)]
dis = dfs(k-1, path, n)
for i in range(q):
    print(dis[xy[i][0] - 1] + dis[xy[i][1] - 1])

Submission status: Accepted

Solution code:
def dfs(k, path, n):
    """連結情報path,頂点の個数Nが与えられたとき
    頂点Kから各頂点までの距離をlistで返す"""
    from collections import deque # deque(),popleft()
    dist = [-1] * n
    dist[k] = 0
    que = deque([])
    que.append(k)
    while que:
        label = que.popleft()
        for i,c in path[label]: # 頂点labelと連結している頂点iと距離c
            if dist[i] == -1:
                dist[i] = dist[label] + c
                que += [i] # 次に調べる頂点に
    return dist

n = int(input())
path = [[] for i in range(n)]
# path = [{1,2}] * 3
# print(path)
for i in range(n-1):
    a, b, c = map(int, input().split())
#     print(a,b,c)
    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)]
dis = dfs(k-1, path, n)
for i in range(q):
    print(dis[xy[i][0] - 1] + dis[xy[i][1] - 1])

Submission status: Accepted

Solution code:
n = int(input())
E = {}

for i in range(n-1):
    a, b, c = map(int, input().split()) 
    found = E.get(a, None)
    if found is None:
        found = []
    found.append((b, c))
    E[a] = found
    found = E.get(b, None)
    if found is None:
        found = []
    found.append((a, c))
    E[b] = found

q, k = list(map(int, input().split()))
Q = [tuple(map(int, input().split())) for i in range(q)]


def make_distance_from_k(k, E):
    d = {}
    d[k] = 0
    queue = [k]
    while queue:
        i = queue.pop()
        for j, c in E[i]:
            if j not in d:
                d[j] = d[i] + c
                queue.append(j)
    return d

d = make_distance_from_k(k, E)

for x, y in Q:
    print(d[x] + d[y])

Submission status: Accepted

Solution code:
# coding=utf-8

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

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

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

s = [(K, -1, 0)]
while len(s)>0:
    (v, p, d) = s.pop()
    depth[v] = d
    for e in tree[v]:
        if e[0]==p:
            continue
        s.append((e[0], v, d+e[1]))


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

Submission status: Accepted

Solution code:
import heapq

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 = [float('inf') for i in range(n)]
dist[k-1] = 0
visited = [False for i in range(n)]
hq = [(0, k-1)]
while hq:
    d, v = heapq.heappop(hq)
    if visited[v]:
        continue
    visited[v] = True
    for nv, c in g[v]:
        if visited[nv]:
            continue
        if d+c < dist[nv]:
            heapq.heappush(hq, (d+c, nv))
            dist[nv] = d+c


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python2
# -*- coding: utf-8 -*-

import Queue

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

Q, K = map(int, raw_input().split())
K -= 1

depth = [0 for _ in xrange(N)]

def bfs(v, p = -1, d = 0):
    q = Queue.Queue()
    q.put([v, p, d])
    while not q.empty():
        cur = q.get()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            q.put([i, cur[0], cur[2] + j])

bfs(K)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python2
# -*- coding: utf-8 -*-

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

Q, K = map(int, raw_input().split())
K -= 1

depth = [0 for _ in xrange(N)]

def dfs(v, p = -1, d = 0):
    St = []
    St.append([v, p, d])
    # 空のシーケンスは偽になる
    while St:
        cur = St.pop()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            St.append([i, cur[0], cur[2] + j])

dfs(K)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python2
# -*- coding: utf-8 -*-

import Queue

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

Q, K = map(int, raw_input().split())
K -= 1

d = [float("inf") for _ in xrange(N)]

def dijkstra(s):
    que = Queue.PriorityQueue()
    d[s] = 0
    que.put([0, s])

    while not que.empty():
        p = que.get()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i, j in tree[v]:
            if d[i] > d[v] + j:
                d[i] = d[v] + j
                que.put([d[i], i])

dijkstra(K)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python2
# -*- coding: utf-8 -*-

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

Q, K = map(int, raw_input().split())
K -= 1

depth = [0 for _ in xrange(N)]

def dfs(v, p = -1, d = 0):
    St = []
    St.append([v, p, d])
    while len(St) != 0:
        cur = St.pop()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            St.append([i, cur[0], cur[2] + j])

dfs(K)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python2
# -*- coding: utf-8 -*-

import sys

sys.setrecursionlimit(200000)

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

Q, K = map(int, raw_input().split())
K -= 1

depth = [0 for _ in xrange(N)]

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

dfs(K)

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

Submission status: Accepted

Solution code:
import Queue

from sys import stdin
input = stdin.readline

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

Q, K = map(int, raw_input().split())
K -= 1

d = [float("inf") for _ in xrange(N)]

def dijkstra(s):
    que = Queue.PriorityQueue()
    d[s] = 0
    que.put([0, s])

    while not que.empty():
        p = que.get()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i, j in tree[v]:
            if d[i] > d[v] + j:
                d[i] = d[v] + j
                que.put([d[i], i])

dijkstra(K)

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

Submission status: Accepted

Solution code:
import Queue

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

Q, K = map(int, raw_input().split())
K -= 1

d = [float("inf") for _ in xrange(N)]

def dijkstra(s):
    que = Queue.PriorityQueue()
    d[s] = 0
    que.put([0, s])

    while not que.empty():
        p = que.get()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i, j in tree[v]:
            if d[i] > d[v] + j:
                d[i] = d[v] + j
                que.put([d[i], i])

dijkstra(K)

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

Submission status: Accepted

Solution code:
# coding: utf-8

# Name: Transit Tree Path
# Level: 2
# Category: Graph, 最短経路問題
# Note: 深さ優先探索

import sys

sys.setrecursionlimit(200000)

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

Q, K = map(int, raw_input().split())
K -= 1

depth = [0 for _ in xrange(N)]

def dfs(v, p = -1, d = 0):
    St = []
    St.append([v, p, d])
    while len(St) != 0:
        cur = St.pop()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            St.append([i, cur[0], cur[2] + j])

dfs(K)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200000)

N = int(raw_input())
tree = [[] for _ in xrange(N)]

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

Q, K = map(int, raw_input().split())
K -= 1

depth = [0 for _ in xrange(N)]

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

dfs(K)

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