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 Tree_with_edge_cost:
    def __init__(self, n, edge):
        self.n = n
        self.nexts = [[] for _ in range(n)]
        for u, v, c in edge:
            self.nexts[u].append((v, c))
            self.nexts[v].append((u, c))
        self.parent = [-1] * self.n
        self.children = [[] for _ in range(self.n)]
        self.cost = [0] * self.n
        self.dist = [0] * self.n  # 根からの距離
        self.depth = [0] * self.n  # 根からの深さ(cost=1での距離)
        self.order = []

    def set_root(self, root):  # O(n)
        self.order.append(root)
        stack = [root]
        while stack:
            v = stack.pop()
            for child, cost in self.nexts[v]:
                if child == self.parent[v]:
                    continue
                else:
                    self.parent[child] = v
                    self.children[v].append(child)
                    self.depth[child] = self.depth[v] + 1
                    self.dist[child] = self.dist[v] + cost
                    self.cost[child] = cost
                    self.order.append(child)
                    stack.append(child)

    def get_diameter(self, restore=False):  # double-sweepで求める  O(n)
        u = self.dist.index(max(self.dist))  # 根から一番遠いものを根とし、そこから一番遠いものを見つける
        dist_u = [-1] * self.n
        dist_u[u] = 0
        stack = [u]
        parent_u = [None for _ in range(self.n)]
        while stack:
            v = stack.pop()
            for child, cost in self.nexts[v]:
                if dist_u[child] == -1:
                    dist_u[child] = dist_u[v] + cost
                    parent_u[child] = v
                    stack.append(child)
        diameter = max(dist_u)
        v = dist_u.index(diameter)
        if restore:
            path = [v]
            while v != u:
                v = parent_u[v]
                path.append(v)
            path.reverse()  # [u,...,v]
            return diameter, path
        else:
            return diameter, u, v

# ---------------------- #

n = int(input())
edges = []
for _ in range(n-1):
    a, b, c = (int(x) for x in input().split())
    a -= 1
    b -= 1
    edges.append((a, b, c))
q, k = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
tree = Tree_with_edge_cost(n, edges)
tree.set_root(k-1)

for x, y in queries:
    x -= 1
    y -= 1
    print(tree.dist[x] + tree.dist[y])

Submission status: Accepted

Solution code:
class RadixHeap:
    __slots__ = ["data", "last", "siz", "used"]

    # (max_key - min_key) <= C
    def __init__(self, N, C):
        self.data = [[] for i in range(C.bit_length() + 1000)]
        self.last = self.siz = 0
        self.used = [0] * N

    def push(self, x, key):
        # assert self.last <= x
        self.siz += 1
        self.data[(x ^ self.last).bit_length()].append((x, key))

    def pop(self):
        data = self.data
        used = self.used
        # assert self.siz > 0
        if not data[0]:
            i = 1
            while not data[i]:
                i += 1
            d = data[i]
            new_last, new_key = min(d)
            used[new_key] = 1
            for val in d:
                x, key = val
                if used[key]:
                    self.siz -= 1
                    continue
                data[(x ^ new_last).bit_length()].append(val)
            self.last = new_last
            data[i] = []
        else:
            new_last, new_key = data[0].pop()
            used[new_key] = 1
            self.siz -= 1
        return new_last, new_key

    def __len__(self):
        return self.siz

def dijkstra(N, G, s):
    que = RadixHeap(N, 10**9 + 1)

    dist = [10**18] * N
    dist[s] = 0
    que.push(0, s)
    while que:
        cost, v = que.pop()
        if dist[v] < cost:
            continue
        for w, c in G[v]:
            if cost + c < dist[w]:
                dist[w] = r = cost + c
                que.push(r, w)
    return dist

# ----------- #

n = int(input())
ABC = [tuple(int(x) for x in input().split()) for _ in range(n - 1)]
q, k = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
G = [[] for _ in range(n)]
for a, b, c in ABC:
    a -= 1
    b -= 1
    G[a].append((b, c))
    G[b].append((a, c))
dist = dijkstra(n, G, k-1)
for x, y in queries:
    x -= 1
    y -= 1
    print(dist[x] + dist[y])

Submission status: Accepted

Solution code:
import sys
def input():return sys.stdin.readline().strip()
from collections import deque

def main():
    N = int(input())
    info = [tuple(map(int, input().split())) for _ in range(N-1)]
    Q, K = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    to = [[] for _ in range(N)]
    for a, b, c in info:
        a -= 1
        b -= 1
        to[a].append((b, c))
        to[b].append((a, c))
    
    INF = 10**18
    dist = [INF]*N
    def dfs(s):
        stack = deque()
        push = stack.append
        pop = stack.pop

        dist[s] = 0
        push(s)

        while stack:
            now = pop()
            now_cost = dist[now]

            for nv, c in to[now]:
                if dist[nv] != INF:
                    continue
                dist[nv] = now_cost + c
                push(nv)


    # query
    K -= 1
    dfs(K)
    ans = []
    for x, y in queries:
        x -= 1
        y -= 1
        xy = dist[x] + dist[y]
        ans.append(xy)

    print(*ans, sep="\n")
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque


def input():
    return sys.stdin.readline().strip()


def bfs(start):
    q = deque([start])
    dist = [-1] * (N + 1)
    dist[start] = 0
    while q:
        v = q.popleft()
        for nv, nw in g[v]:
            if dist[nv] > 0:
                continue
            dist[nv] = dist[v] + nw
            q.append(nv)
    return dist


N = int(input())
g = [[] for _ in range(N + 1)]
for _ 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 = bfs(K)
ans = []
for _ in range(Q):
    x, y = map(int, input().split())
    print(d[x] + d[y])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import heappush, heappop


def input():
    return sys.stdin.readline().strip()


def dijkstra(adj_list, start):
    n = len(adj_list)
    dist = [float("inf")] * n
    dist[start] = 0

    pq = []
    heappush(pq, (0, start))
    visited = set()
    while pq:
        w, v = heappop(pq)
        if dist[v] < w:
            continue
        visited.add(v)
        for nv, nw in adj_list[v]:
            if nv in visited:
                continue
            if dist[nv] > dist[v] + nw:
                dist[nv] = dist[v] + nw
                heappush(pq, (dist[nv], nv))
    return dist


N = int(input())
g = defaultdict(list)
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
d = dijkstra(g, K)
ans = []
for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(d[x] + d[y])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)


N=int(input())
G=[[] for _ 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())

SD=[0]*N
def DFS(v,p,d):
    SD[v]=d
    for i,co in G[v]:
        if i==p:continue
        DFS(i,v,d+co)
    return

DFS(K-1,-1,0)

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

Submission status: Accepted

Solution code:
N=int(input())
G=[[] for _ 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())

SD=[0]*N
seen=[0]*N
stack=[]
stack.append([K-1,0])
seen[K-1]=1
while stack:
    x,d=stack.pop()
    for y,d0 in G[x]:
        if seen[y]==0:
            SD[y]=d+d0
            stack.append([y,d+d0])
            seen[y]=1
for i in range(Q):
    x,y=map(int,input().split())
    ans=SD[x-1]+SD[y-1]
    print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque

    n = int(readline())
    edge = defaultdict(list)

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

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

    que = deque()
    que.append((k, 0))
    dists = dict()

    while que:
        u, dist = que.popleft()
        for v, w in edge[u]:
            if v not in dists:
                dists[v] = dist + w
                que.append((v, dist + w))

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N = int(input())
connected = [[]for _ in range(N+1)]
for i in range(N-1):
    a, b, c = (int(x) for x in input().split())
    connected[a].append((b,c))
    connected[b].append((a,c))
Q, K = (int(x) for x in input().split())
distk = [-1] * (N+1)
d = deque([K])
distk[K] = 0
while d:
    temp = d.popleft()
    for vert, dist in connected[temp]:
        if distk[vert] == -1:
            d.append(vert)
            distk[vert] = distk[temp] + dist
for i in range(Q):
    x, y = (int(x) for x in input().split())
    print(distk[x]+distk[y])

Submission status: Accepted

Solution code:
#グラフの連結成分を調べる
def Graph(ab):
    G = [[] for i in range(n)]
    for a, b, c in ab:
        G[a - 1].append([b, c])
        G[b - 1].append([a, c])
    return G

from collections import deque
def bfs(k):
    q = deque()
    q.append((k, - 1, 0))
    dis = [0] * n 
    while q:
        V, P, cnt = q.popleft()
        for nv, d in G[V - 1]:
            if nv == P:continue
            dis[nv - 1] = cnt + d
            q.append((nv, V, cnt + d))
    
    return dis 

n = int(input())
abc = [list(map(int,input().split())) for _ in range(n - 1)]
G = Graph(abc)
q, k = map(int,input().split())
dis = bfs(k)

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
  e[v].append((u, c))
Q, K = map(int, input().split())

dp = [10 ** 15] * (N + 1)
dp[K] = 0
s = [K]
while len(s):
  x = s.pop()
  for y, d in e[x]:
    if dp[y] > dp[x] + d:
      s.append(y)
      dp[y] = dp[x] + d

for _ in range(Q):
  u, v = map(int, input().split())
  print(dp[u] + dp[v])

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import defaultdict
ns = defaultdict(set)
for i in range(n-1):
    u,v,c = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    ns[v].add((c,u))
# print(ns)
k = len(bin(n-1))-2
# 深さ
def cdepth(root=0):
    # rootを根としたときの深さ
    ps = [None] * n
    ps[0] = -1
    q = [0]
    while q:
        u = q.pop()
        for c,v in ns[u]:
            if ps[v] is None:
                ps[v] = u
                q.append(v)
    # psを元から持っている場合、引数のnsをpsにしてこの下だけで良い
    depth = [None] * n
    depth[root] = 0
    q = [root]
    while q:
        u = q.pop()
        for c,v in ns[u]:
            if depth[v] is None:
                depth[v] = depth[u] + 1
                q.append(v)
    return depth, ps
def dijkstra(start):
    import heapq
    vals = [None] * n
    h = [(0, start)] # (距離, ノード番号)
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if vals[v] is None or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals

# ダブリング
def double(ps):
    # global: n=psのサイズ
    k = 0
    while pow(2,k)<n:
        k += 1
    prev = [[None]*n for _ in range(k)] # ノードjから2^i個上の上司
    for j in range(n):
        prev[0][j] = ps[j]
    for i in range(1,k):
        for j in range(n):
            p = prev[i-1][j]
            if p>=0:
                prev[i][j] = prev[i-1][p]
            else:
                prev[i][j] = p
    return prev
            

# k: 必要桁数を定める必要アリ
def cprev(u,i):
    """uからi個上の頂点を返す
    """
    for j in range(k):
        if i>>j&1:
            u = prev[j][u]
    return u

# k: 必要桁数を定める必要アリ
def lca(u,v):
    if depth[u]<depth[v]:
        v = cprev(v, depth[v]-depth[u])
    else:
        u = cprev(u, depth[u]-depth[v])
    if u==v:
        return u
    for i in range(k-1, -1, -1):
        if prev[i][u]!=prev[i][v]:
            u = prev[i][u]
            v = prev[i][v]
    return prev[0][u]

q,K = map(int, input().split())
K -= 1
dist = dijkstra(K)
ans = [None]*q
for i in range(q):
    x,y = map(int, input().split())
    x -= 1
    y -= 1
    ans[i] = dist[x] + dist[y]
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import defaultdict
ns = defaultdict(set)
for i in range(n-1):
    u,v,c = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    ns[v].add((c,u))
# print(ns)
k = len(bin(n-1))-2
# 深さ
def cdepth(root=0):
    # rootを根としたときの深さ
    ps = [None] * n
    ps[0] = -1
    q = [0]
    while q:
        u = q.pop()
        for c,v in ns[u]:
            if ps[v] is None:
                ps[v] = u
                q.append(v)
    # psを元から持っている場合、引数のnsをpsにしてこの下だけで良い
    depth = [None] * n
    depth[root] = 0
    q = [root]
    while q:
        u = q.pop()
        for c,v in ns[u]:
            if depth[v] is None:
                depth[v] = depth[u] + 1
                q.append(v)
    return depth, ps
def dijkstra(start):
    import heapq
    vals = [None] * n
    h = [(0, start)] # (距離, ノード番号)
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if vals[v] is None or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals

# ダブリング
def double(ps):
    # global: n=psのサイズ
    k = 0
    while pow(2,k)<n:
        k += 1
    prev = [[None]*n for _ in range(k)] # ノードjから2^i個上の上司
    for j in range(n):
        prev[0][j] = ps[j]
    for i in range(1,k):
        for j in range(n):
            p = prev[i-1][j]
            if p>=0:
                prev[i][j] = prev[i-1][p]
            else:
                prev[i][j] = p
    return prev
            

# k: 必要桁数を定める必要アリ
def cprev(u,i):
    """uからi個上の頂点を返す
    """
    for j in range(k):
        if i>>j&1:
            u = prev[j][u]
    return u

# k: 必要桁数を定める必要アリ
def lca(u,v):
    if depth[u]<depth[v]:
        v = cprev(v, depth[v]-depth[u])
    else:
        u = cprev(u, depth[u]-depth[v])
    if u==v:
        return u
    for i in range(k-1, -1, -1):
        if prev[i][u]!=prev[i][v]:
            u = prev[i][u]
            v = prev[i][v]
    return prev[0][u]

dist = dijkstra(0)
depth, ps = cdepth(0)
prev = double(ps)
q,K = map(int, input().split())
K -= 1
ans = [None]*q
for i in range(q):
    x,y = map(int, input().split())
    x -= 1
    y -= 1
    l1 = lca(x,K)
    l2 = lca(y,K)
#     print(x,y,l1,l2)
    ans[i] = (dist[x]+dist[K]-2*dist[l1]) + (dist[y]+dist[K]-2*dist[l2])
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    way = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a,b,c = map(int,ipt().split())
        way[a].append((b,c))
        way[b].append((a,c))
    q,k = map(int,ipt().split())
    l = [-1]*(n+1)
    l[k] = 0
    Q = queue.Queue()
    Q.put(k)
    while not Q.empty():
        qi = Q.get()
        lq = l[qi]
        for bi,ci in way[qi]:
            if l[bi] == -1:
                l[bi] = lq+ci
                Q.put(bi)

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

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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 = tuple(map(int, input().split()))
INF = 10**9*n + 1
dists = [INF] * n
dists[k-1] = 0

from collections import deque
q = deque([k-1])

while q:
    node = q.popleft()
    for to, c in G[node]:
        if dists[to] > dists[node] + c:
            dists[to] = dists[node] + c
            q.append(to)

for _ in range(Q):
    s, g = tuple(map(int, input().split()))
    print(dists[s-1] + dists[g-1])

Submission status: Accepted

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 = tuple(map(int, input().split()))
INF = 10**9*n + 1
dists = [INF] * n
dists[k-1] = 0

from collections import deque
q = deque([k-1])
visited = [0] * n
visited[k-1] = 1

while q:
    node = q.popleft()
    for to, c in G[node]:
        if visited[to] == 1:
            continue

        if dists[to] > dists[node] + c:
            dists[to] = dists[node] + c
            q.append(to)

for _ in range(Q):
    s, g = tuple(map(int, input().split()))
    print(dists[s-1] + dists[g-1])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop


def dijkstra(path, N, start):
    """
    Args:
        path (list): [[(cost, node), (cost, node), ...], [], [], ...]
    """
    visited = [False] * N
    que = [(0, start)]
    heapify(que)  # 始点aから各頂点への(距離, 頂点ID)
    dist = [-1] * N  # 始点aから各頂点への距離
    dist[start] = 0  # 始点aからaへの距離は0
    while que:
        d, v = heappop(que)  # 始点から最短距離の頂点を(確定ノード)を取り出す
        visited[v] = True  # 確定フラグを立てる
        # 接続先ノードの情報を更新する
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))

    return dist


def main():
    N = int(readline())
    path = [[] for _ in range(N)]

    for _ in range(N-1):
        a, b, c = map(int, readline().rstrip().split())
        path[a-1].append((c, b-1))
        path[b-1].append((c, a-1))
    
    Q, K = map(int, readline().rstrip().split())
    dist = dijkstra(path, N, K-1)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)


n = int(input())
query = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    query[a-1].append((b-1, c))
    query[b-1].append((a-1, c))
q, k = map(int, input().split())
stack = deque([(k-1, 0, -1)])
dist = [0] * n
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in lis:
        if nx == per:
            continue
        if c != 0:
            stack.append((nx, cnt+c, now))
for i in range(q):
    x, y = map(int, input().split())
    print(dist[x-1] + dist[y-1])

Submission status: Accepted

Solution code:
from collections import *
import sys
S=sys.stdin.readlines()
N=int(S[0])
G=[[] for i in range(N)]
a,b,c=0,0,0
for i in range(N-1):
  a,b,c=map(int,S[i+1].split())
  a,b=a-1,b-1
  G[a].append((b,c))
  G[b].append((a,c))
Q,K=map(int,S[N].split())
D,Z=deque(),set()
def qao(x):
  global D,Z
  if x in Z:
    return False
  Z.add(x)
  D.append(x)
  return True

dist=[0]*N
def bfs():
  global dist,D,G
  v=0
  for i in range(len(D)):
    v=D.popleft()
    for j in range(len(G[v])):
      if qao(G[v][j][0]):
        dist[G[v][j][0]]=G[v][j][1]+dist[v]
  return len(D)

qao(K-1)
while bfs():
  pass
for i in range(Q):
  a,b=map(int,S[N+1+i].split())
  print(dist[a-1]+dist[b-1])

Submission status: Accepted

Solution code:
n = int(input())
V = [[] for i in range(n+1)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    V[a].append([b,c])
    V[b].append([a,c])
q,k = map(int,input().split())
from collections import deque
dis = [-1]*(n+1)
Q = deque([])
Q.append(k)
dis[k] = 0
while Q:
    r = Q.popleft()
    for A,D in V[r]:
        if dis[A] == -1:
            Q.append(A)
            dis[A] = dis[r] + D
x = [0]*q
for i in range(q):
    x,y = map(int,input().split())
    print(dis[x]+dis[y])

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

N = int(input())

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


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

visits = [False]*(N+1)
costs = defaultdict(int)
q = deque()
q.append((K, 0))
visits[K] = True
while q:
    u, c1 = q.popleft()
    for v, c2 in e[u]:
        if not visits[v]:
            costs[(K, v)] = c1+c2
            visits[v] = True
            q.append((v, c1+c2))

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import defaultdict

n = int(input())
graph = defaultdict(list)

# グラフにコストを格納
for _ 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())


# コストの初期化
INF = 1 << 60
dist = [INF] * (n + 1)
dist[k] = 0

#　スタート地点
que = [(0, k)]

# ３からの距離
while que:
    cost, curr = heappop(que)
    if cost > dist[curr]:
        continue
    for after, nc in graph[curr]:
        if cost + nc < dist[after]:
            dist[after] = cost + nc
            heappush(que, (cost + nc, after))
            
print(*([dist[x] + dist[y] for x, y in (map(int, input().split()) for _ in range(q))]), sep="\n")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def dfs(now, vis, dis):
    for to,c in edge[now]:
        if not vis[to]:
            if dis[to] == 0:
                dis[to] = dis[now] + c
            else:
                dis[to] = min(dis[now] + c, dis[to])
            vis[now] = 1
            dfs(to, vis, dis)

N = int(input())

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

visited = [0]*N
distance = [0]*N

Q, K = map(int, input().split())
dfs(K-1, visited, distance)

#print(distance)

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

Submission status: Accepted

Solution code:
N=int(input())
import sys
sys.setrecursionlimit(10**6)
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())
D=[-1]*N
D[K-1]=0
def dfs(start, nowd):
    to=T[start]
    for t in to:
        next_node,c=t
        if D[next_node]!=-1:
            continue
        nextd=nowd+c
        D[next_node]=nextd
        dfs(next_node, nextd)
dfs(K-1,0)
# print(D)
for i in range(Q):
    x,y=map(int, input().split())
    print(D[x-1]+D[y-1])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

Q, K = mapint()
from collections import deque
stack = deque([(K-1, 0, -1)])
dist = [0]*N
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in lis:
        if nx==per:
            continue
        if c!=0:
            stack.append((nx, cnt+c, now))

for _ in range(Q):
    x, y = mapint()
    print(dist[x-1]+dist[y-1])

Submission status: Accepted

Solution code:
import heapq
n = int(input())
edge = [[] for _ in range(n)]
for i in range(n-1):
  a,b,c = map(int,input().split())
  a-=1;b-=1 #0index
  edge[a].append([c,b])
  edge[b].append([c,a])
#print(edge)
Q,K = map(int,input().split())
K-=1 #0index

#d = [INF for _ in range(N)]
#d[K] = 0

def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定。始点として探索されたか。というかdが更新されたか。
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中からスタートから最小の距離のものを探す
        if not used[minedge[1]]: #すでに探索済みの場合にはスキップして次のプライオリティーキューへ。
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False #ここで始点として探索済みにする。
        for e in edge[v]:
            if used[e[1]]: #行き先がすでに始点として探索済みでない場合には値を更新。
                heapq.heappush(edgelist,[e[0]+d[v],e[1]]) #重みをスタートからの最短重みにするため+d[v]
    return d ##始点sから各頂点への最短距離がアウトプットとなる。

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
def dfs(parent,current,distance):
  global m
  m[current]=distance
  for child in graph[current]:
    if child[0]==parent:
      continue
    dfs(current,child[0],distance+child[1])
n=int(input())
graph=[]
for i in range(n+1):
  graph.append([])
m=[0]*(n+1)
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())
dfs(k,k,0)
for i in range(q):
  x,y=map(int,input().split())
  print(m[x]+m[y])

Submission status: Accepted

Solution code:
import sys
# from collections import defaultdict, deque
import math
# import copy
# from bisect import bisect_left, bisect_right
import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 1000000007


def dijkstra(graph, start, n):
    h = []
    heapq.heappush(h, (0, start))
    costs = [INF for _ in range(n)]
    while h:
        cost, cur = heapq.heappop(h)
        if costs[cur] != INF:
            continue
        costs[cur] = cost
        for edge in graph[cur]:
            ecost, tgt = edge
            if costs[tgt] == INF:
                heapq.heappush(h, (cost + ecost, tgt))

    return costs

def solve():
    n = getN()
    graph = [[] for _ in range(n)]
    for i in range(n-1):
        a,b,c = getList()
        a,b = a-1, b-1

        graph[a].append([c, b])
        graph[b].append([c, a])
    q, k = getList()
    costs = dijkstra(graph, k-1, n)
    # print(costs)
    for i in range(q):
        s, e = getZList()

        print(costs[s] + costs[e])

    return

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

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

N = int(input())
tree = [[] for _ 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))

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

dis = [-1]*N
dis[K-1] = 0
def dfs(v,d):
    for i in tree[v]:
        d = dis[v]
        next,c = i
        if dis[next] == -1:
            d += c
            dis[next] = d
            dfs(next,d)
dfs(K-1,0)

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

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
ab = [[]for i in range(10**5)]
v=[0]*(10**5)
d=[float('INF')]*(10**5)
for i in range(n-1):
    a , b , c = map(int, input().split())
    ab[a-1].append((b-1,c))
    ab[b-1].append((a-1,c))
q , k = map(int, input().split())

k-=1
de=deque()
de.append((k,0))

d[k]=0
while de:
    now , dis = de.popleft()
    if dis > d[now]:
        continue

    for next , cost in ab[now]:
        if dis + cost < d[next]:
            d[next]= dis + cost
            de.append((next,dis+cost))

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

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]*n
dist[k] = 0
def dfs(now):
    for nxt,d in G[now]:
        if dist[nxt] != -1: continue
        dist[nxt] = dist[now] + d
        dfs(nxt)
dfs(k)

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

for i in range(q): print(ans[i])