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: Time Limit Exceeded

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

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

q, k = map(int, input().split())
list_dist_k = []
for i in range(n):
  d = Dijkstra(g, i)
  list_dist_k.append(d.shortest_distance(k - 1))
for _ in range(q):
  x, y = map(int, input().split())
  dist_1 = list_dist_k[x-1]
  dist_2 = list_dist_k[y-1]
  print(dist_1 + dist_2)

Submission status: Time Limit Exceeded

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

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

q, k = map(int, input().split())
for _ in range(q):
  x, y = map(int, input().split())
  d1 = Dijkstra(g, x-1)
  dist_1 = d1.shortest_distance(k-1)
  d2 = Dijkstra(g, k-1)
  dist_2 = d2.shortest_distance(y-1)
  print(dist_1 + dist_2)

Submission status: Time Limit Exceeded

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

n=int(input())

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

dis=[None]*(n+1)
def set_dist(x,d):
    dis[x]=d
    for y,f in edge[x]:
        if dis[y] is not None:
            continue
        set_dist(y,d+f)
set_dist(k,0)

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

Submission status: Time Limit Exceeded

Solution code:

from heapq import heappush, heappop
 
 
class Dijk:
    def __init__(self, n):
        self.table = [[] for i in range(n+1)]
        self.n = n+1
 
    def add(self, x, y, f):
        self.table[x].append((y, f))
 
    def di(self, s):
        inf = float('inf')
        self.val = [inf] * self.n
        self.val[s] = 0
        h = []
        heappush(h, (0, s))
        while h:
            q, i = heappop(h)
            if self.val[i] < q:
                continue
            for x, c in self.table[i]:
                if self.val[x] > self.val[i] + c:
                    self.val[x] = self.val[i] + c
                    heappush(h, (self.val[x], x))
 
    def dist(self, s, t):
        return self.val[t]

n= int(input())
dijk=Dijk(n)

for i in range(n-1):
    a,b,c=map(int,input().split())
    dijk.add(a,b,c)
    dijk.add(b,a,c)
q,k=map(int,input().split())
for i in range(q):
    x,y=map(int,input().split())
    dijk.di(x)
    ans=dijk.dist(x,k)
    dijk.di(k)
    ans+=dijk.dist(k,y)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(v,d,p):
    memo[v] = d
    for i in graph[v]:
        if memo[i[0]] != -1:continue
        dfs(i[0],d+i[1],v)
    sub_tree[v].append(v)
    for j in graph[v]:
        if j[0] == p:continue
        sub_tree[v] += sub_tree[j[0]]
    if p == k-1:arr.append(sub_tree[v])
n = int(input())
graph = [[] for _ in range(n)]
memo = [-1]*n

for i in range(n-1):
    x,y,z = map(int,input().split())
    graph[x-1].append([y-1,z])
    graph[y-1].append([x-1,z])
q,k = map(int,input().split())
sub_tree = [[] for _ in range(n)]
arr = []
ary = [list(map(int,input().split())) for _ in range(q)]
dfs(k-1,0,0)
arr.pop()
print(*[memo[x-1]+memo[y-1] for x,y in ary],sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(v,d,p):
    memo[v] = d
    flag = False
    for i in graph[v]:
        if memo[i[0]] != -1:continue
        dfs(i[0],d+i[1],v)
    sub_tree[v].append(v)
    for j in graph[v]:
        if j[0] == p:continue
        sub_tree[v] += sub_tree[j[0]]
    if p == k-1:arr.append(sub_tree[v])
n = int(input())
graph = [[] for _ in range(n)]
memo = [-1]*n

for i in range(n-1):
    x,y,z = map(int,input().split())
    graph[x-1].append([y-1,z])
    graph[y-1].append([x-1,z])
q,k = map(int,input().split())
sub_tree = [[] for _ in range(n)]
arr = []
ary = [list(map(int,input().split())) for _ in range(q)]
dfs(k-1,0,0)
arr.pop()
a = [0,0]
for i in range(q):
    for j in range(len(arr)):
        if ary[i][0] in arr[j]:
            a[0] = j
        if ary[i][1] in arr[j]:
            a[1] = j
    if a[0] == a[1]:
        print(memo[ary[i][0]-1]+memo[ary[i][1]-1])
    else:
        print(memo[ary[i][0]-1]+memo[ary[i][1]-1])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from math import isinf


class Edge(object):

    def __init__(self, src, dst, cost):
        self.src = src
        self.dst = dst
        self.cost = cost


class Dijkstra(object):

    def __init__(self, v_len, edges, start, directed=False):
        """
        ダイクストラ法で最短経路を求める。

        :param v_len: グラフのノード数 通常は|V|、1-indexedなグラフなら |V| + 1
        :param edges: グラフの構造
        :param start: 始点 単一視点最短経路問題として解くので必要
        :param directed: 有向グラフの場合True 隣接行列を対称行列にするかが変わる
        """

        # 隣接行列 (adjacency matrix)
        # adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        self._adj = [[float('inf') for _ in range(v_len)] for _ in range(v_len)]
        for e in edges:
            self._adj[e.src][e.dst] = e.cost
            if not directed:
                self._adj[e.dst][e.src] = e.cost
        self._dist = [float('inf') for i in range(v_len)]  # 始点から各頂点までの最短距離
        self._prev = [float('inf') for i in range(v_len)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        self._solve(start)

    def _solve(self, start):
        # 「最短距離が確定した頂点」に隣接する点からBFSするにあたり、それをどう探すかが問題になる
        # 安直に実装すればここで O(|V|) かかってしまうが、優先度キューを使えば O(log|V|) になる
        self._dist[start] = 0
        q = list()
        heappush(q, (0, start))  # キューの要素は (始点から頂点v_iへの仮の距離, v_iのID)

        while len(q) != 0:
            c, src = heappop(q)
            if self._dist[src] < c:
                continue

            # 隣接行列から隣接するノードを全て調べる = BFS
            for dst in range(len(self._adj)):
                cost = self._adj[src][dst]
                if isinf(cost):
                    continue
                if self._dist[src] + cost < self._dist[dst]:
                    self._dist[dst] = self._dist[src] + cost
                    heappush(q, (self._dist[dst], dst))
                    self._prev[dst] = src

    def distance(self, goal):
        return self._dist[goal]

    def path(self, goal):
        path = list()
        path.append(goal)
        cursor = goal

        while not isinf(self._prev[cursor]):
            path.append(self._prev[cursor])
            cursor = self._prev[cursor]

        return list(reversed(path))


N = int(input())
edges = list()
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    edges.append(Edge(a, b, c))

Q, K = map(int, input().split())
dijkstra = Dijkstra(N + 1, edges, K)
for x, y in [tuple(map(int, input().split())) for _ in range(Q)]:
    print(dijkstra.distance(x) + dijkstra.distance(y))

Submission status: Time Limit Exceeded

Solution code:
#%%
n = int(input())
a, b, c = [0] * n, [0] * n, [0] * n
for i in range(n-1):
    a[i], b[i], c[i] = map(int, input().split())

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

l = [[] for _ in range(n+1)]
for i in range(n-1):
    l[a[i]].append([b[i],c[i]])
    l[b[i]].append([a[i],c[i]])

d = [0] * (n+1)
check = [0] * (n+1)
check[k] = 1
que = [k]

while len(que) > 0:
    tmp = que.pop(0)
    for i in l[tmp]:
        if check[i[0]] == 0:
            que.append(i[0])
            check[i[0]] = 1
            d[i[0]] = d[tmp] + i[1]
        else:
            pass

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

Submission status: Time Limit Exceeded

Solution code:
#%%
n = int(input())
a, b, c = [0] * n, [0] * n, [0] * n
for i in range(n-1):
    a[i], b[i], c[i] = map(int, input().split())

q, k = map(int, input().split())
x, y = [0] * q, [0] * q
for i in range(q):
    x[i], y[i] = map(int, input().split())

l = [[] for _ in range(n+1)]
for i in range(n-1):
    l[a[i]].append((b[i],c[i]))
    l[b[i]].append((a[i],c[i]))

d = [0] * (n+1)
check = [0] * (n+1)
check[k] = 1
que = [k]

while len(que) > 0:
    tmp = que.pop(0)
    for i in l[tmp]:
        if check[i[0]] == 0:
            que.append(i[0])
            check[i[0]] = 1
            d[i[0]] = d[tmp] + i[1]
        else:
            pass

for i in range(q):
    ans = d[x[i]] + d[y[i]]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#%%
n = int(input())
a, b, c = [0] * n, [0] * n, [0] * n
for i in range(n-1):
    a[i], b[i], c[i] = map(int, input().split())

q, k = map(int, input().split())
x, y = [0] * q, [0] * q
for i in range(q):
    x[i], y[i] = map(int, input().split())

l = [[] for _ in range(n+1)]
for i in range(n-1):
    l[a[i]].append((b[i],c[i]))
    l[b[i]].append((a[i],c[i]))

d = [0] * (n+1)
check = [0] * (n+1)
check[k] = 1
que = [k]

while len(que) > 0:
    tmp = que.pop(0)
    tmp_list = l[tmp]
    for i in tmp_list:
        if check[i[0]] == 0:
            que.append(i[0])
            check[i[0]] = 1
            d[i[0]] = d[tmp] + i[1]
        else:
            pass

for i in range(q):
    ans = d[x[i]] + d[y[i]]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[[0,0,0] for _ in range(n-1)]
for i in range(n-1):
    l[i][0],l[i][1],l[i][2]=map(int,input().split())
l.sort()
q,k=map(int,input().split())
r=[[0,0] for _ in range(q)]
for i in range(q):
    r[i][0],r[i][1]=map(int,input().split())
c=[0]*n
for i in range(n-1):
    if l[i][0]==k:
        c[l[i][1]-1]=l[i][2]
    elif l[i][1]==k:
        c[l[i][0]-1]=l[i][2]

for _ in range(100):
    for i in range(n-1):
        if c[l[i][0]-1]!=0 and c[l[i][1]-1]==0:
            c[l[i][1]-1]+=c[l[i][0]-1]+l[i][2]
        if c[l[i][1]-1]!=0 and c[l[i][0]-1]==0:
            c[l[i][0]-1]+=c[l[i][1]-1]+l[i][2]
#print(c)
for i in range(q):
    print(c[r[i][0]-1]+c[r[i][1]-1])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[[0,0,0] for _ in range(n-1)]
for i in range(n-1):
    l[i][0],l[i][1],l[i][2]=map(int,input().split())
l.sort()
q,k=map(int,input().split())
r=[[0,0] for _ in range(q)]
for i in range(q):
    r[i][0],r[i][1]=map(int,input().split())
c=[0]*n
for i in range(n-1):
    if l[i][0]==k:
        c[l[i][1]-1]=l[i][2]
    elif l[i][1]==k:
        c[l[i][0]-1]=l[i][2]

for _ in range(500):
    for i in range(n-1):
        if c[l[i][0]-1]!=0 and c[l[i][1]-1]==0:
            c[l[i][1]-1]+=c[l[i][0]-1]+l[i][2]
        if c[l[i][1]-1]!=0 and c[l[i][0]-1]==0:
            c[l[i][0]-1]+=c[l[i][1]-1]+l[i][2]
#print(c)
for i in range(q):
    print(c[r[i][0]-1]+c[r[i][1]-1])

Submission status: Time Limit Exceeded

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

# 頂点 s からの最短距離を求める (存在しないときはinf) O(|w|log|n|)
# n: 頂点数, w: 辺の数, cost[u][v]: 辺uvのコスト (cost が dict の場合 cost[(u,v)] など適宜)
# 前提条件: u < v
def dijkstra(s,n,w,cost):
    d = [float("inf")] * n # s からの距離
    d[s] = 0
    used = [False] * n # 使用済みの頂点か
    
    while True:
        v = -1
        # 未使用の頂点のうち、最小の距離のものを探す
        for i in range(n):
            if used[i]:
                continue
            if v == -1 or d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
               
        for j in range(n):
            e = (min(v,j), max(v,j))
            c = cost[e] if e in cost else float("inf")
            # cost が list のときは普通に c = cost[v][j] などとする
            d[j] = min(d[j], d[v] + c)
    return d

def main():
    N = int(input())
    E = dict()
    for _ in range(N-1):
        a,b,c = map(int, input().split())
        a0 = min(a,b)-1
        b0 = max(a,b)-1
        E[(a0, b0)] = c
    Q,K = map(int, input().split())
    D = dijkstra(K-1, N, N-1, E)
    for _ in range(Q):
        x,y = map(int, input().split())
        print(D[x-1] + D[y-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
import sys 
input = sys.stdin.readline
import numpy as np
def solve():
  n = int(input())
  d = [[float("inf")]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
  q,k = (int(i) for i in input().split())
  d = np.array(d)
  d = dijkstra(d,indices = k-1)

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

solve()

Submission status: Time Limit Exceeded

Solution code:

import sys 
input = sys.stdin.readline
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d
def solve():
  n = int(input())
  d = [[float("inf")]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

  q,k = (int(i) for i in input().split())
  
  d = dijkstra(k-1,n,n-1,d)

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

solve()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
import sys 
input = sys.stdin.readline

def solve():
  n = int(input())
  d = [[float("inf")]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1][b-1] = c

  q,k = (int(i) for i in input().split())
  
  d = dijkstra(d,directed=False,indices=k-1)

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

solve()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
import sys 
input = sys.stdin.readline

def solve():
  n = int(input())
  d = [[float("Inf")]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
  q,k = (int(i) for i in input().split())
  d = dijkstra(d,indices=k-1)

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

solve()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
import sys 
input = sys.stdin.readline

def solve():
  n = int(input())
  d = [[float("Inf")]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
  d = dijkstra(d)
  q,k = (int(i) for i in input().split())
  for i in range(q):
    res = 0
    x,y = (int(i) for i in input().split())
    res = d[x-1][k-1] + d[k-1][y-1]
    print(int(res))
solve()

Submission status: Time Limit Exceeded

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]
for _ in range(N-1):
    v, c, p = iter(queue.pop(0))
    shortest_path[v] = c
    queue += [[u, T[v][u] + c, v] for u in T[v].keys() if u != p]

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

Submission status: Time Limit Exceeded

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]

for _ in range(Q):
    x, y = map(int, input().split())
    while len(queue) > 0 and (shortest_path[x] == 0 or shortest_path[y] == 0):
        v = queue.pop(0)
        shortest_path[v[0]] = v[1]
        queue += [[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]]
    print(shortest_path[x] + shortest_path[y])

Submission status: Time Limit Exceeded

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]

for _ in range(N-1):
    v = queue.pop(0)
    shortest_path[v[0]] = v[1]
    queue += [[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]]

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

Submission status: Time Limit Exceeded

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]

while len(queue) > 0:
    v = queue.pop(0)
    shortest_path[v[0]] = v[1]
    queue += [[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]]

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
T = [[] for i in range(N+1)]
for _ 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())
shortest_path = [0 for _ in range(N+1)]
queue = [t + [K] for t in T[K]]

while len(queue) > 0:
    v = queue.pop(0)
    shortest_path[v[0]] = v[1]
    queue += [[u[0], u[1] + v[1], v[0]] for u in T[v[0]] if u[0] != v[2]]

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
T = [[] for i in range(N+1)]
for _ 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())
shortest_path = [0 for _ in range(N+1)]
queue = [t + [K] for t in T[K]]


for _ in range(Q):
    x, y = map(int, input().split())

    while len(queue) > 0 and (shortest_path[x] == 0 or shortest_path[y] ==0):
        v = queue.pop(0)
        shortest_path[v[0]] = v[1]
        for u in T[v[0]]:
            if u[0] != v[2]:
                queue.append([u[0], u[1] + v[1], v[0]])
    
    print(shortest_path[x] + shortest_path[y])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
T = [[] for i in range(N+1)]
for _ 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())
shortest_path = [0 for _ in range(N+1)]
queue = [t + [K] for t in T[K]]
while len(queue) > 0:
    v = queue.pop(0)
    shortest_path[v[0]] = v[1]
    for u in T[v[0]]:
        if u[0] != v[2]:
            queue.append([u[0], u[1] + v[1], v[0]])

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
T = [[] for i in range(N+1)]
for _ 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())
shortest_path = [0 for _ in range(N+1)]
V, queue = set([K]), T[K]
while len(queue) > 0:
    v = queue.pop(0)
    shortest_path[v[0]] = v[1]
    for u in T[v[0]]:
        if u[0] not in V:
            queue.append([u[0], u[1] + v[1]])
    V.add(v[0])

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
T = [[] for i in range(N+1)]
for _ 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())
shortest_path = [0 for _ in range(N+1)]
V, queue = set([K]), T[K]
while len(queue) > 0:
    v = queue.pop(queue.index(min(queue, key = lambda x: x[1])))
    shortest_path[v[0]] = v[1]
    for u in T[v[0]]:
        if u[0] not in V:
            queue.append([u[0], u[1] + v[1]])
    V.add(v[0])

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

Submission status: Time Limit Exceeded

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

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

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


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

def dfs(v,p,d):
  lk[v-1]=d

  for l in dct[v]:
    if l[0]==p or lk[l[0]-1]!=0:
      continue
    else:
      dfs(l[0],v,d+l[1])
  return

dfs(k,-1,0)



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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

n = int(input())
ls = [list(map(int, input().split())) for _ in range(n - 1)]

cs = [[0] * (n + 1) for _ in range(n + 1)]
es = [[] for _ in range(n + 1)]
for a, b, c in ls:
    cs[a][b] = cs[b][a] = c
    es[a].append(b)
    es[b].append(a)
ds = [0] * (n + 1)


def dfs(cur, prev):
    ds[cur] = ds[prev] + cs[prev][cur]
    for e in es[cur]:
        if e != prev:
            dfs(e, cur)


q, k = map(int, input().split())
qs = [list(map(int, input().split())) for _ in range(q)]

dfs(k, k)
for x, y in qs:
    print(ds[x] + ds[y])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
cs = [[0] * (n + 1) for _ in range(n + 1)]
es = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    cs[a][b] = cs[b][a] = c
    es[a].append(b)
    es[b].append(a)
ds = [0] * (n + 1)


def dfs(cur, prev):
    ds[cur] = ds[prev] + cs[prev][cur]
    for e in es[cur]:
        if e != prev:
            dfs(e, cur)


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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
cs = [[0] * (n + 1) for _ in range(n + 1)]
es = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    cs[a][b] = cs[b][a] = c
    es[a].append(b)
    es[b].append(a)
ds = [0] * (n + 1)
qs = []


def bfs():
    cur, prev = qs.pop()
    ds[cur] = ds[prev] + cs[prev][cur]
    for e in es[cur]:
        if e != prev:
            qs.append((e, cur))


q, k = map(int, input().split())
qs.append((k, k))
while qs:
    bfs()

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
cs = [[0] * (n + 1) for _ in range(n + 1)]
es = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    cs[a][b] = cs[b][a] = c
    es[a].append(b)
    es[b].append(a)
ds = [0] * (n + 1)


def bfs(cur, prev):
    ds[cur] = ds[prev] + cs[prev][cur]
    for e in es[cur]:
        if e != prev:
            bfs(e, cur)


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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
con=[[] for _ in range(n)]
dist=[[None]*n for _ in range(n)]
dist_f_k=[0]*n

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

q,k=map(int,input().split())
dist_f_k[k-1]=None
que=deque([(k-1,0)])
while que:
	cur,d=que.popleft()
	for nxt in con[cur]:
		if dist_f_k[nxt]==0:
			tmp=d+dist[cur][nxt]
			que.append((nxt,tmp))
			dist_f_k[nxt]=tmp

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

Submission status: Time Limit Exceeded

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

N = int(input())
E = [set() for _ in range(N)]
C = {}
for i in range(N-1):
  a,b,c = map(int,input().split())
  E[a-1].add(b-1)
  E[b-1].add(a-1)
  C[min(a-1,b-1)*N+max(a-1,b-1)] = c
  
Q,K = map(int,input().split())
K -= 1
Query = []
for i in range(Q):
  x,y = map(int,input().split())
  Query.append([x-1,y-1])
#print(E)
#print(C)
#print(K)
#print(Query)

Kcost = [0 for _ in range(N)]
def dfs(u,v):
  if v != -1:
    Kcost[u] = Kcost[v] + C[min(u,v)*N+max(u,v)]
  for t in E[u]:
    if t != K and Kcost[t] == 0:
      dfs(t,u)
dfs(K,-1)

for x,y in Query:
  print(Kcost[x]+Kcost[y])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
E = [set() for _ in range(N)]
C = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N-1):
  a,b,c = map(int,input().split())
  E[a-1].add(b-1)
  E[b-1].add(a-1)
  C[a-1][b-1] = c
  C[b-1][a-1] = c
Q,K = map(int,input().split())
K -= 1
Query = []
for i in range(Q):
  x,y = map(int,input().split())
  Query.append([x-1,y-1])
#print(E)
#print(C)
#print(K)
#print(Query)

Kcost = [0 for _ in range(N)]
def dfs(u,v):
  if v != -1:
    Kcost[u] = Kcost[v] + C[u][v]
  for t in E[u]:
    if t != K and Kcost[t] == 0:
      dfs(t,u)
dfs(K,-1)

for x,y in Query:
  print(Kcost[x]+Kcost[y])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())

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

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

visited = [False] * N
visited[K-1] = True

distance = [-1]*N

que = deque([(K, 0)])
while que:
    cur, d = que.popleft()
    distance[cur-1] = d

    for a, b, c in G:
        if a == cur and visited[b-1] is False:
            visited[b-1] = True
            que.append((b, d+c))
        elif b == cur and visited[a-1] is False:
            visited[a-1] = True
            que.append((a, d+c))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())

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

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

visited = [False] * N
visited[K-1] = True

distance = [-1]*N

que = deque([(K-1, 0)])
while que:
    cur, d = que.popleft()
    distance[cur] = d

    for nx, nd in enumerate(G[cur]):
        if nd != -1 and visited[nx] is False:
            visited[nx] = True
            que.append((nx, d+nd))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6) 
N = int(input())
ds = [[0]*N for i in range(N)]
for i in range(N-1):
  a, b, c = list(map(int, input().split(" ")))
  ds[a-1][b-1] = c
  ds[b-1][a-1] = c
q, k = list(map(int, input().split(" ")))
 
def dfs(path, dist, c):
  if c==g:
    return dist
  dists = []
  for i in range(N):
    if ds[i][c]>0 and i not in path:
      dists.append(dfs(path+[c],dist+ds[i][c],i))
  if len(dists)>0:
	  return min(dists)
  else:
      return 10**15
 
ky = []
for i in range(N):
  if i==k-1:
    ky.append(0)
  else:
    g = i
    ky.append(dfs([],0,k-1))
    
for i in range(q):
  x, y = list(map(int, input().split(" ")))
  print(ky[x-1]+ky[y-1])