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:
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 = [point_node(start_point, 0)]
    while 1:
        new_node_list = []
        for i in range(len(node_list)):
            now_node = node_list[i]
            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
                    new_node_list.append(point_node(c[0], c[1] + now_node.cost))
        if len(new_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: Time Limit Exceeded

Solution code:
import heapq
import copy
inf =10**20+7
N = int(input())
A = [ [inf for i in range(N)] for j in range(N)]
for n in range(N-1):
  a,b,c=map(int,input().split())
  A[a-1][b-1] = c
  A[b-1][a-1] = c
 
Q,K = map(int,input().split())
 
def Tree_search(A,start,goal_list):
  num = len(A)
  dist = [inf for i in range(N)] 
  prev = [inf for i in range(N)] 
  
  dist[start] = 0
  
  
  def check(dist,prev,start,goal_list):
    length = {}
    q = []
    heapq.heappush(q,(0,start))
    while len(q) != 0:
      c,src = heapq.heappop(q)
      if dist[src] < c:
        continue
      for dst in range(num):
        check = A[src][dst]
        if check != inf and dist[dst]>dist[src] + check:
          dist[dst]=dist[src] + check
          heapq.heappush(q,(dist[dst],dst))
          prev[dst] = src
    
    for goal in goal_list:
      length_min=0
      tmp_pos = copy.copy(goal)
      while prev[tmp_pos] != inf:
        length_min += A[tmp_pos][prev[tmp_pos]]
        tmp_pos = prev[tmp_pos]
      length[goal] =length_min
    
    return length
    
  
  return check(dist,prev,start,goal_list)

tmp=[]
tmptmp=[]

for q in range(Q):
  x,y = map(int,input().split())
  tmptmp.append(x-1)
  tmptmp.append(y-1)
  tmp.append([x-1,y-1])

tmptmp = list(set(tmptmp))
Length = Tree_search(A,K-1,tmptmp) 
for q in range(Q):
  print(Length[tmp[q][0]]+Length[tmp[q][1]])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
g = {}
for i in range(1,N+1):
    g[i] = []
def dfs(g,start,end):
    stack = [(start, [start],0)]
    while stack:
        (v, path, length) = stack.pop()
        for next,l in g[v]:
            if next in path: continue
            if next == end:
                return length + l
            else:
                stack.append((next, path + [next], length + l))

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

for q in range(Q):
    x, y = map(int,input().split())
    print(dfs(g,x,K) + dfs(g,K,y))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy
inf =10**20
N = int(input())
A = [ [inf for i in range(N)] for j in range(N)]
for n in range(N-1):
  a,b,c=map(int,input().split())
  A[a-1][b-1] = c
  A[b-1][a-1] = c
 
Q,K = map(int,input().split())
 
def Tree_search(A,start):
  num = len(A)
  dist = [inf for i in range(N)] 
  prev = [inf for i in range(N)] 
  
  dist[start] = 0
  
  
  def check(dist,prev,start):
    length = {}
    q = []
    heapq.heappush(q,(0,start))
    while len(q) != 0:
      c,src = heapq.heappop(q)
      if dist[src] < c:
        continue
      for dst in range(num):
        check = A[src][dst]
        if check != inf and dist[dst]>dist[src] + check:
          dist[dst]=dist[src] + check
          heapq.heappush(q,(dist[dst],dst))
          prev[dst] = src
    
    for n in range(N):
      length_min=0
      tmp_pos = copy.copy(n)
      while prev[tmp_pos] != inf:
        length_min += A[tmp_pos][prev[tmp_pos]]
        tmp_pos = prev[tmp_pos]
      length[n] =length_min
    
    return length
    
  
  return check(dist,prev,start)

Length = Tree_search(A,K-1) 

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
g = {}
for i in range(1,N+1):
    g[i] = []
def dfs(g,start,end):
    stack = [(start, [start],0)]
    while stack:
        (v, path, length) = stack.pop()
        for next,l in g[v]:
            if next in path:
                continue
            if next == end:
                yield length + l
            else:
                stack.append((next, path + [next], length + l))

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

for q in range(Q):
    x, y = map(int,input().split())
    a = list(dfs(g,x,K))[0]
    b = list(dfs(g,K,y))[0]
    print(a+b)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

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=Queue()
que.put((k-1,0))
while not que.empty():
    u,d=que.get()
    if ds[u] != INF:
        continue
    ds[u]=d
    for v,w in g[u]:
        que.put((v,d+w))

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

Submission status: Time Limit Exceeded

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

def main():
  N = int(input())
  m = dict()
  distK = dict()
  v = [0]*(N+1)
  for i in range(1,N+1):
    m[i] = []
    distK[i] = N*10**9
  for _ in range(N-1):
    a,b,c = map(int,input().split())
    m[a].append((b,c))
    m[b].append((a,c))
  Q,K = map(int,input().split())
  distK[K] = 0
  ToVisit = [K]
  while ToVisit:
    tov = ToVisit.pop(0)
    if v[tov] == 0:
      v[tov] = 1
      for b,c in m[tov]:
        distK[b] = min(distK[b],distK[tov]+c)
        ToVisit.append(b)
  for _ in range(Q):
    x,y = map(int,input().split())
    print(distK[x]+distK[y])

main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
m = dict()
distK = dict()
v = [0]*(N+1)
for i in range(1,N+1):
  m[i] = []
  distK[i] = N*10**9
for _ in range(N-1):
  a,b,c = map(int,input().split())
  m[a].append((b,c))
  m[b].append((a,c))
Q,K = map(int,input().split())
distK[K] = 0
ToVisit = [K]
while ToVisit:
  tov = ToVisit.pop(0)
  if v[tov] == 0:
    v[tov] = 1
    for b,c in m[tov]:
      distK[b] = min(distK[b],distK[tov]+c)
      ToVisit.append(b)
for _ in range(Q):
  x,y = map(int,input().split())
  print(distK[x]+distK[y])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

BIG = 2**40

n = int(input().strip())
d = [[BIG for _ in range(n + 1)] for _ in range(n + 1)]

for _ in range(n - 1):
    a, b, c = [int(x) for x in input().strip().split()]
    d[a][b] = c
    d[b][a] = c

nodes = range(1, n+1)

for node in nodes:
    d[node][node] = 0

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

done = {k}
dist = {t: BIG for t in nodes}
dist[k] = 0
lastdone = k
while 1:
    nextdone, cost = -1, BIG
    for node in nodes:
        if node in done:
            continue
        if dist[lastdone] + d[lastdone][node] < dist[node]:
            dist[node] = dist[lastdone] + d[lastdone][node]
        if dist[node] < cost:
            nextdone = node
            cost = dist[node]
    if nextdone == -1:
        break
    done.add(nextdone)
    lastdone = nextdone

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

BIG = 2**40

n = int(input().strip())
d = defaultdict(lambda: defaultdict(lambda: BIG))

for _ in range(n - 1):
    a, b, c = [int(x) for x in input().strip().split()]
    d[a][b] = c
    d[b][a] = c

nodes = list(d.keys())
#for node in nodes:
#    d[node][node] = 0

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

done = {k}
dist = {t: BIG for t in nodes}
dist[k] = 0
lastdone = k
while 1:
    nextdone, cost = -1, BIG
    for node in nodes:
        if node in done:
            continue
        if dist[lastdone] + d[lastdone][node] < dist[node]:
            dist[node] = dist[lastdone] + d[lastdone][node]
        if dist[node] < cost:
            nextdone = node
            cost = dist[node]
    if nextdone == -1:
        break
    done.add(nextdone)
    lastdone = nextdone

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

Submission status: Time Limit Exceeded

Solution code:
n=input()
adj=[[] for j in range(n+2)]
rank=[0 for i in range(n+2)]
cost=[[0 for i in range(n+2)] for j in range(n+2)]
visited=[]
c=[0 for i in range(n+2)]
t=0

cnt=0
for i in xrange(n-1):
    c,d,e=map(int,raw_input().split())
    adj[c].append(d)
    adj[d].append(c)
    cost[c][d]=e
    cost[d][c]=e

qu,st=map(int,raw_input().split())
rank[st]=1
l=[st]
visited=[st]
while l!=[]:
    b=l.pop()
    for i in xrange(len(adj[b])):
        if adj[b][i] not in visited:
            visited.append(adj[b][i])
            l.append(adj[b][i])
            rank[adj[b][i]]=rank[b]+cost[b][adj[b][i]]
            t=max(rank[adj[b][i]],t)
visited=[]
for i in range(qu):
    t,y=map(int,raw_input().split())
    print rank[t]+rank[y]-2

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

BIG = 2**64-1

n = int(input().strip())
d = defaultdict(lambda: defaultdict(lambda: BIG))

for _ in range(n - 1):
    a, b, c = [int(x) for x in input().strip().split()]
    d[a][b] = c
    d[b][a] = c

nodes = list(d.keys())
for node in nodes:
    d[node][node] = 0


for a in nodes:
    for b in nodes:
        for c in nodes:
            if d[b][c] > d[b][a] + d[a][c]:
                d[b][c] = d[c][b] = d[b][a] + d[a][c]

q, k = [int(x) for x in input().strip().split()]
for _ in range(q):
    x, y = [int(_x) for _x in input().strip().split()]
    print(d[x][k] + d[k][y])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
gr = {i:[] for i in range(1, n + 1)}
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    gr[a].append((b, c))
    gr[b].append((a, c))
q, k = map(int, input().split())
dmax = 10**14 + 1
dist = [dmax for _ in range(n + 1)]
dist[k] = 0
ls = [k]
while 0 < len(ls):
    u = ls[0]
    for v, c in gr[u]:
        if dist[v] == dmax:
            dist[v] = dist[u] + c
            ls.append(v)
    ls = ls[1:]

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

Submission status: Memory Limit Exceeded

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

TO_K = []
TREE = []

def dfs(parent, distance):
    for i_node in TREE[parent]:
        if TO_K[i_node[0]] != -1:
            continue

        next_dt = distance + i_node[1]
        TO_K[i_node[0]] = next_dt
        dfs(i_node[0], next_dt)

    return


def main():
    n = int(input())
    abc = [[int(_) for _ in input().split()] for i in range(n-1)]
    q, k = map(int, input().split())
    xy = [[int(_) for _ in input().split()] for i in range(q)]

    global TO_K
    # index '0' is not used.
    TO_K = [-1]*(n+1)

    global TREE
    # index '0' is not used.
    TREE = [[] for _ in range(n+1)]
    for a, b, c in abc:
        TREE[a].append([b, c])
        TREE[b].append([a, c])

    TO_K[k] = 0
    dfs(k, 0)

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


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Memory Limit Exceeded

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

TO_K = []
TREE = []

def dfs(parent, distance):
    for i_node in TREE[parent]:
        child, dd = i_node
        if TO_K[child] != -1:
            continue

        next_dt = distance + dd
        TO_K[child] = next_dt
        dfs(child, next_dt)

    return


def main():
    n = int(input())
    abc = [[int(_) for _ in input().split()] for i in range(n-1)]
    q, k = map(int, input().split())
    xy = [[int(_) for _ in input().split()] for i in range(q)]

    global TO_K
    # index '0' is not used.
    TO_K = [-1]*(n+1)

    global TREE
    # index '0' is not used.
    TREE = [[] for _ in range(n+1)]
    for a, b, c in abc:
        TREE[a].append([b, c])
        TREE[b].append([a, c])

    TO_K[k] = 0
    dfs(k, 0)

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


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Memory Limit Exceeded

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


def main():
    n = int(input())
    abc = [[int(_) for _ in input().split()] for i in range(n-1)]
    q, k = map(int, input().split())
    xy = [[int(_) for _ in input().split()] for i in range(q)]

    # index '0' is not used.
    to_k = [-1]*(n+1)

    # index '0' is not used.
    tree = [[] for _ in range(n+1)]
    for a, b, c in abc:
        tree[a].append([b, c])
        tree[b].append([a, c])

    def dfs(parent, distance):
        for i_node in tree[parent]:
            child, dd = i_node
            if to_k[child] != -1:
                continue

            next_dt = distance + dd
            to_k[child] = next_dt
            dfs(child, next_dt)

        return

    to_k[k] = 0
    dfs(k, 0)

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


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Memory Limit Exceeded

Solution code:
from functools import lru_cache as cache
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)
@cache(maxsize=None)
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: Memory Limit Exceeded

Solution code:
import sys;g=6**8;sys.setrecursionlimit(g);G=[[]for I in[lambda:map(int,raw_input().split())]*g];n=I()[0]
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 i in[0]*q:x,y=I();print G[x]+G[y]

Submission status: Memory Limit Exceeded

Solution code:
import sys;g=8**7;sys.setrecursionlimit(g);G=[[]for I in[lambda:map(int,raw_input().split())]*g];n=I()[0]
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 i in[0]*q:x,y=I();print G[x]+G[y]

Submission status: Accepted

Solution code:
N = int(input())

tree = {}

for _ in range(N-1):
  A, B, C = [int(i) for i in input().split()]
  if A not in tree:
    tree[A] = []
  if B not in tree:
    tree[B] = []
  tree[A].append((B, C))
  tree[B].append((A, C))


c = {}
q = []
visited = set()

def dfs(a, acc):
  q.append((a, acc))

  while q:
    n, r = q.pop()
    c[n] = r
    visited.add(n)
    for b, cost in ((b, cost) for b, cost in tree[n] if b not in visited):
      q.append((b, cost + r))


Q, K = [int(i) for i in input().split()]
dfs(K, 0)

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

Submission status: Accepted

Solution code:
N = int(input())
f = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    f[a-1].append([b-1,c])
    f[b-1].append([a-1,c])
from collections import deque
d = deque()
s = [-1]*N
Q,K = map(int,input().split())
d.append(K-1)
s[K-1] = 0
while len(d) > 0:
    z = d.popleft()
    for i,j in f[z]:
        if s[i] == -1:
            s[i] = j+s[z]
            d.append(i)
for i in range(Q):
    x,y = map(int,input().split())
    print(s[x-1]+s[y-1])

Submission status: Accepted

Solution code:
from collections import deque

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

d = [[] for _ in range(N)]
for a, b, c in A:
    d[a-1].append([b-1, c])
    d[b-1].append([a-1, c])

c = [0]*N
f = [False]*N
f[K-1] = True

q = deque([K-1])
while q:
    now = q.popleft()
    for nex, cost in d[now]:
        if f[nex]:
            continue
        c[nex] = c[now]+cost
        f[nex] = True
        q.append(nex)

for x, y in X:
    print(c[x-1]+c[y-1])

Submission status: Accepted

Solution code:
N = int(input())

#隣接リスト
ad = {}
for n in range(N):
    ad[n+1]=[]
    
for n in range(N-1):
    a,b,c = list(map(int,input().split()))
    ad[a].append([b,c])
    ad[b].append([a,c])
    
Query = []
Q,K = list(map(int,input().split()))
for q in range(Q):
    x,y = list(map(int,input().split()))
    Query.append([x,y])

# ダイクストラ（優先度キュー）
import heapq
INF = 10 ** 20

color = {}
for n in range(N):
    color[n+1] = -1
    
dist = {}
for n in range(N):
    dist[n+1] = INF

def dijkstra(start, node_num): 
    HP = []
    dist[start] = 0

    heapq.heappush(HP,[start,0])

    while HP:
        u = heapq.heappop(HP)[0]

        color[u] = 1

        for to, cost in ad[u]:
            if color[to] == -1 and dist[u] + cost < dist[to]:
                dist[to] = dist[u] + cost
                heapq.heappush(HP, (to, dist[to]))
    return dist

start = K
node_num = N
dist = dijkstra(start, node_num)

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7
def intread():
    return int(sysread())
def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def dfs(current, to, dists):
    c, c_cost = current
    dists[c] = c_cost
    for n, n_cost in to[c]:
        if dists[n] == -1:
            dfs((n, c_cost + n_cost), to, dists)
    return dists


def run():
    N = intread()
    to = [[] for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = mapline()
        to[a].append((b, c))
        to[b].append((a, c))
    Q, K = mapline()

    dists = [-1] * (N+1)
    dists = dfs((K, 0), to, dists)
    for i in range(Q):
        x,y= mapline()
        print(dists[x] + dists[y])

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

N=intput()
node=[list() for _ in range(N+1)]
for _ in range(N-1):
    a,b,c=mint()
    node[a].append([b,c])
    node[b].append([a,c])
Q,K=mint()
cost=[-1]*(N+1)
cost[K]=0
q=deque([K])
while q:
    u=q.popleft()
    for v,c in node[u]:
        if cost[v]<0:
            cost[v]=cost[u]+c
            q.append(v)
for _ in range(Q):
    x,y=mint()
    print(cost[x]+cost[y])

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=map(int,input().split())
K-=1
dist=[-1 for _ in range(N)]
dist[K]=0
q=[K]
while len(q)>0:
    v=q.pop()
    for p in G[v]:
        nv=p[0]
        if dist[nv]!=-1:
            continue
        dist[nv]=dist[v]+p[1]
        q.append(nv)
for _ in range(Q):
    x,y=map(int,input().split())
    print(dist[x-1]+dist[y-1])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
from heapq import heappush, heappop

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

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces


def dijkstra(s, n): # (始点, ノード数)
    dist = [inf] * n
    hq = [(0, s)] # (distance, node)
    dist[s] = 0
    seen = [False] * n # ノードが確定済みかどうか
    while hq:
        v = heappop(hq)[1] # ノードを pop する
        seen[v] = True
        for to, cost in adj[v]: # ノード v に隣接しているノードに対して
            if seen[to] == False and dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(hq, (dist[to], to))
    return dist

N = ni()
adj = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = na()
    adj[a-1].append((b-1, c))
    adj[b-1].append((a-1, c))

Q, K = na()
ans = []
d = dijkstra(K-1, N)

for i in range(Q):
    x, y = na()
    x -= 1
    y -= 1
    ans.append(d[x] + d[y])

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

Submission status: Accepted

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

N = int(readline())
G = [[] for i in range(N)]

for i in range(N - 1):
  a,b,c = map(int,readline().split())
  G[a - 1].append((b - 1, c))
  G[b - 1].append((a - 1, c))
  
Q,K = map(int,readline().split())

dist = [0] * N
stack = [(K - 1, -1, 0)]
while stack:
  v,parent,cost = stack.pop()
  dist[v] = cost
  for child, c in G[v]:
    if child == parent:
      continue
    stack.append((child, v, cost + c))
    
for i in range(Q):
  x,y = map(int,readline().split())
  print(dist[x - 1] + dist[y - 1])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

graph = [[] for _ in range(N+1)]

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

visited = [-1 for _ in range(N+1)]

visited[K] = 0
que = deque()
que.append(K)

while (len(que)):
    now = que.popleft()
    
    for nxt, c in graph[now]:
        if(visited[nxt] != -1):
            continue
        visited[nxt] = visited[now]+c
        que.append(nxt)
        
for i in range(Q):
    x, y = map(int, input().split())
    print(visited[x]+visited[y])

Submission status: Accepted

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

N = int(input())

graph = [[] for _ in range(N)]

for _ in range(N-1):
    a, b, c = map(int, input().split())
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))
    
Q, K = map(int, input().split())
visited = [0 for _ in range(N)]

def DFS(a, b, c):
    for i, j in graph[b]:
        if(i != a):
            visited[i] = c+j
            DFS(b, i, c+j)
DFS(-1, K-1, 0)
             
for _ in range(Q):
    x, y = map(int, input().split())
    print(visited[x-1]+visited[y-1])

Submission status: Accepted

Solution code:
from collections import namedtuple, deque
N = int(input())

connection = [[] for _ in range(N)]
branch = namedtuple('branch',['id', 'dist'])
for _ in range(N-1):
    a, b, c = map(int, input().split())
    connection[a-1].append(branch(b-1, c))
    connection[b-1].append(branch(a-1, c))

dist = [0] * N #dist from root(K)
Q, K = map(int, input().split())
#bfs
reserved = deque([K-1])
seen = {K-1}
while len(reserved) > 0:
    current = reserved.popleft()
    for next in connection[current]:
        if next.id in seen:
            continue
        seen.add(next.id)
        reserved.append(next.id)
        dist[next.id] = dist[current] + next.dist

#deal with query
Query = [map(int, input().split()) for _ in range(Q)]
for x,y in Query:
    print(dist[x-1] + dist[y-1])

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
num=[[] for _ in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    num[a-1].append([b,c])
    num[b-1].append([a,c])
q,k=map(int,input().split())
seen=[False]*n
queue=deque()
queue.append(k)
ans=[0]*n
seen[k-1]=True
for i in range(n):
    if len(queue)==0:
        break
    num1=queue.popleft()
    for j in range(len(num[num1-1])):
        num2=num[num1-1][j][0]
        if seen[num2-1]==False:
            queue.append(num2)
            seen[num2-1]=True
            ans[num2-1]=ans[num1-1]+num[num1-1][j][1]
for i in range(q):
    x,y=map(int,input().split())
    print(ans[x-1]+ans[y-1])

Submission status: Accepted

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

N = k()
edge = [[] for _ in range(N+1)]

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

Q,K = I()

dist = [None]*(N+1)

def dfs(x,d):
    dist[x] = d
    for y,dd in edge[x]:
        if dist[y] is not None:
            continue
        dfs(y,d+dd)

dfs(K,0)
for _ in range(Q):
    x,y = I()
    print(dist[x]+dist[y])

Submission status: Accepted

Solution code:
N=int(input())
tree=[[] for i 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))
from collections import deque
visited=[-1 for i in range(N)]
Q,K=map(int,input().split())
visited[K-1]=0
q=deque([])
q.append(K-1)
while q:
  u=q.popleft()
  for v,d in tree[u]:
    if visited[v]==-1:
      visited[v]=visited[u]+d
      q.append(v)
    
for i in range(Q):
  x,y=map(int,input().split())
  print(visited[x-1]+visited[y-1])

Submission status: Accepted

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


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

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

Q, K = map(int, input().split())
K -= 1
query = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(Q)]
depth = [0] * N

def dfs(v, d, p=-1):
    depth[v] = d
    for cost, nv in to[v]:
        if nv == p:
            continue
        dfs(nv, d + cost, v)


def main():
    dfs(K, 0)
    for x, y in query:
        print(depth[x] + depth[y])


if __name__ == "__main__":
    main()