Problem:


Score : 400 points

Problem Statement

You are given a tree with N vertices.

Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N-1 edges, where N is the number of its vertices.

The i-th edge (1≤i≤N-1) connects Vertices a_i and b_i, and has a length of c_i.

You are also given Q queries and an integer K. In the j-th query (1≤j≤Q):

find the length of the shortest path from Vertex x_j and Vertex y_j via Vertex K.

Constraints

3≤N≤10^5 

1≤a_i,b_i≤N (1≤i≤N-1) 

1≤c_i≤10^9 (1≤i≤N-1) 

The given graph is a tree.

1≤Q≤10^5 

1≤K≤N 

1≤x_j,y_j≤N (1≤j≤Q) 

x_j≠y_j (1≤j≤Q) 

x_j≠K,y_j≠K (1≤j≤Q) 

Input

Input is given from Standard Input in the following format:  

N  
a_1 b_1 c_1  
:  
a_{N-1} b_{N-1} c_{N-1}
Q K
x_1 y_1
:  
x_{Q} y_{Q}

Output

Print the responses to the queries in Q lines.

In the j-th line j(1≤j≤Q), print the response to the j-th query.

Sample Input 1

5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5

Sample Output 1

3
2
4

The shortest paths for the three queries are as follows:

Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3 

Query 2: Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2 

Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4 

Sample Input 2

7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7

Sample Output 2

5
14
22

The path for each query must pass Vertex K=2.

Sample Input 3

10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10

Sample Output 3

17000000000



Sample input:
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5


Sample output:
3
2
4

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
g=[[]for _ in range(n)]
for _ in range(n-1):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    g[a].append((b,c))
    g[b].append((a,c))


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

dist=[float("inf")]*n
dist[k]=0
def dfs(s):
    for v,c in g[s]:
        if dist[v]==float("inf"):
            dist[v]=dist[s]+c
            dfs(v)


dfs(k)

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

Submission status: Accepted

Solution code:
from collections import*
from heapq import*
import sys
input=sys.stdin.readline
 
def BFS(point,d):
    cost=[1e18]*(n+1)
    cost[point]=0
    Q=deque()
    Q.appendleft((0,point))
    
    while Q:
        c,p=Q.pop()
        for np,co in d[p]:
            if cost[np]==1e18:
                cost[np]=c+co
                Q.appendleft((c+co,np))
    return cost

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

Submission status: Accepted

Solution code:

from heapq import*
import sys
input=sys.stdin.readline
 
def DIJKSTRA(point,d):
    cost      = [1e18]*(n+1)
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

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

q,k=map(int,input().split())
y=DIJKSTRA(k,d)
 
for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Submission status: Accepted

Solution code:
from collections import deque

def f(k,edge,n):
    root = [[] for _ in range(n)]
    for i in range(n-1):
        a,b,c = edge[i][0],edge[i][1],edge[i][2]
        root[a-1].append([b-1,c])
        root[b-1].append([a-1,c])
    
    que = deque()
    for l in root[k]:
        que.append(l)
    
    dist = [float("inf")]*n
    dist[k] = 0
    visited = [False]*n
    que = deque([k])

    while que:
        pos = que.popleft()
        if not visited[pos]:
            visited[pos] = True
        for x,y in root[pos]:
            if not visited[x]:
                dist[x] = dist[pos] + y
                visited[x] = True
                que.append(x)
    return dist

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

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

ans = []
d = f(k-1,edge,n)
for i in range(q):
    x,y = map(int,input().split())
    ans.append(d[x-1] + d[y-1])

print(*ans , sep = "\n")

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    ts = collections.defaultdict(list)
    tc = collections.defaultdict(int)
    for i in range(n-1):
        ta, te, ttc = list(map(int, input().rstrip('\n').split()))
        ts[ta - 1] += [te - 1]
        ts[te - 1] += [ta - 1]
        tc[ta - 1, te - 1] = ttc
        tc[te - 1, ta - 1] = ttc

    q, k = list(map(int, input().rstrip('\n').split()))
    ql = [[0, k-1]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    while True:
        if len(ql) != 0:
            cost, p = ql.popleft()
            for v in ts[p]:
                if v not in fq:
                    n_cost = tc[p, v]
                    ql.append([cost + n_cost, v])
                    fq[v] = cost + n_cost
                else:
                    n_cost = tc[p, v]
                    if n_cost + cost < fq[v]:
                        ql.append([cost + n_cost, v])
                        fq[v] = cost + n_cost
        else:
            break
    for i in range(q):
        x, y = list(map(int, input().rstrip('\n').split()))
        print(fq[x-1] + fq[y-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n=int(input())
from collections import defaultdict 
d=defaultdict(list)
for i in range(n-1):
    a,b,c=map(int,input().split())
    a-=1 
    b-=1 
    d[a].append([b,c])
    d[b].append([a,c])
qry,k=map(int,input().split())
k-=1 
dist=[0]*n 
dist[k]=-0 
vis=[0]*n 
vis[k]=1 
from collections import deque
q=deque() 
q.append(k)
while q: 
    t=q.popleft() 
    for node,weight in d[t]: 
        if not vis[node]:
            vis[node]=1 
            q.append(node)
            dist[node]=dist[t]+weight
while qry:
    qry-=1 
    a,b=map(int,input().split())
    a-=1 
    b-=1 
    print(dist[a]+dist[b])

Submission status: Accepted

Solution code:
import sys
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
import heapq


n = int(input())
graph = {j:[] for j in range(n)}
for j in range(n-1):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append([b,c])
    graph[b].append([a,c])
q, k = [int(i) for i in sys.stdin.readline().split()]
k -= 1
#res = dijkstra(csr_matrix(graph), indices=k)
candidates = [(k,0)]
res = [-1 for i in range(n)]
res[k] = 0
already = set()
while len(candidates) > 0 or len(already) < n:
    candidate, cost = heapq.heappop(candidates)
    already.add(candidate)
    res[candidate] = cost
    for goal, distance in graph[candidate]:
        if res[goal] < 0:
            heapq.heappush(candidates, (goal, cost + distance))

for i in range(q):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    print(int(res[x] + res[y]))

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
n=int(input())
d=[10**20 for i in range(n)] 
g=[[] for i in range(n)]
for _ in range(n-1):
    a,b,c = map(int,input().split())
    g[a-1].append([b-1,c])
    g[b-1].append([a-1,c])
q,k = map(int,input().split())
k-=1
f=[False for i in range(n)]
d[k]=0

def dfs(s,c):
    f[s]=True
    d[s]=c
    for sg in g[s]:
        if not f[sg[0]]:
            dfs(sg[0],c+sg[1])
dfs(k,0)

lq=[]
for _ in range(q):
    lq.append(list(map(int,input().split())))
for sq in lq:
    print(d[sq[0]-1]+d[sq[1]-1])

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
l=[list() for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    l[a-1].append((b-1,c))
    l[b-1].append((a-1,c))
Q,K=map(int,input().split())
L=[None]*N
L[K-1]=0
t=1
s={K-1}
while t<N:
    g=set()
    for i in s:
        for j in l[i]:
            if L[j[0]]==None:
                L[j[0]]=L[i]+j[1]
                g.add(j[0])
                t+=1
    s=g
for _ in range(Q):
    x,y=map(int,input().split())
    print(L[x-1]+L[y-1])

Submission status: Accepted

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
q,k=map(int,input().split())
ql=[list(map(int,input().split())) for i in range(q)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append([l[i][1]-1,l[i][2]])
  connection[l[i][1]-1].append([l[i][0]-1,l[i][2]])

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j][0]]==-1:
            distance[connection[next[i]][j][0]]=distance[next[i]]+connection[next[i]][j][1]
            next2.add(connection[next[i]][j][0])
    next=list(next2)
    next2=set()
  return distance
x=bfs(k-1)
for i in range(q):
  print(x[ql[i][0]-1]+x[ql[i][1]-1])

Submission status: Accepted

Solution code:
from collections import deque
INFTY = 10**14
N = int(input())
G = {}
for _ in range(N-1):
    a,b,c = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append((b,c))
    if b not in G:
        G[b] = []
    G[b].append((a,c))
Q,K = map(int,input().split())
d = [INFTY for _ in range(N+1)]
d[K] = 0
hist = [0 for _ in range(N+1)]
heap = deque([K])
hist[K] = 1
while heap:
    cur = heap.popleft()
    for x in G[cur]:
        if hist[x[0]]==0:
            d[x[0]] = d[cur]+x[1]
            heap.append(x[0])
            hist[x[0]] = 1
for _ in range(Q):
    x,y = map(int,input().split())
    print(d[x]+d[y])

Submission status: Accepted

Solution code:
N=int(input())
edges=[list(map(int,input().split())) for i in range(N-1)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
root=[[] for _ in range(N)]
for a,b,c in edges:
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))
d=[-1]*N
s=[K-1]
d[K-1]=0
while s:
        l=s.pop()

        for i,c in root[l]:
                if d[i]==-1:
                        d[i]=d[l]+c
                        s.append(i)
for i in range(Q):
        print(d[xy[i][0]-1]+d[xy[i][1]-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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: 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([b, c])
    to[b].append([a, c])

Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

dist = [0] * N

def dfs(v, pv, dis):
    for i in to[v]:
        if i[0] != pv:
            dfs(i[0], v, dis+i[1])
    dist[v] = dis

dfs(K-1, -1, 0)

for x, y in xy:
    print(dist[x-1] + dist[y-1])

Submission status: Accepted

Solution code:
N = int(input())
Edge = [list(map(int,input().split())) for i in range(N-1)]
Q,K = map(int,input().split())
Query = [list(map(int,input().split())) for i in range(Q)]

Graph = [[] for i in range(N)]
for edge in Edge:
    Graph[edge[0]-1].append([edge[1]-1,edge[2]])
    Graph[edge[1]-1].append([edge[0]-1,edge[2]])

Distance = [-1 for i in range(N)]
Distance[K-1] = 0

stack = [K-1]
while stack:
    node = stack.pop()
    for adj in Graph[node]:
        if Distance[adj[0]] == -1:
            Distance[adj[0]] = Distance[node] + adj[1]
            stack.append(adj[0])

for query in Query:
    print(Distance[query[0]-1]+Distance[query[1]-1])

Submission status: Accepted

Solution code:
from collections import *
from heapq import*
import sys
input=sys.stdin.readline
d=defaultdict(list)
n=int(input())
 
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})
 
def DIJKSTRA(point,d):
    cost      = {node:1e18 for node in d.keys()}
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost
 
q,k=map(int,input().split())
y=DIJKSTRA(k,d)
 
for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Submission status: Accepted

Solution code:
from collections import *
from heapq import*
import sys
input=sys.stdin.readline
d=defaultdict(list)
n=int(input())
 
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})
 
def DIJKSTRA(point,d):
    cost      = {node:float("inf") for node in d.keys()}
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost
 
q,k=map(int,input().split())
y=DIJKSTRA(k,d)
 
for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(v,d):
    memo[v] = d
    for i in graph[v]:
        if memo[i[0]] != -1:continue
        dfs(i[0],d+i[1])

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())
ary = [list(map(int,input().split())) for _ in range(q)]
dfs(k-1,0)
for x,y in ary:
    print(memo[x-1]+memo[y-1])

Submission status: Accepted

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

def dfs(prev, now, fromK, t, d):
  d[now] = fromK
  for nl in (t[now]):
    if nl[0] != prev:
      dfs(now, nl[0], fromK+nl[1], t, d)

N = int(input())
T  = [[] for _ in range(N+1)]
for _ in range(N-1):
  a, b, l = map(int, input().split())
  T[a].append([b,l])
  T[b].append([a, l])
Q, K = map(int, input().split())
D = [0] * (N+1)
dfs(-1, K, 0, T, D)
for _ in range(Q):
  x, y = map(int, input().split())
  print(D[x]+D[y])

Submission status: Accepted

Solution code:
n=int(input())
abc=[list(map(int,input().split())) for _ in [0]*(n-1)]
q,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in [0]*q]
k-=1
tree=[[] for _ in [0]*n]
dist=[-1]*n
dist[k]=0
[tree[a-1].append([b-1,c]) for a,b,c in abc]
[tree[b-1].append([a-1,c]) for a,b,c in abc]

q=[k]

while(q):
	qq=[]
	for i in q:
		for j,k in tree[i]:
			if dist[j]<0:
				dist[j]=dist[i]+k
				qq.append(j)
	q=qq

for x,y in xy:
	print(dist[x-1]+dist[y-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(v,d):
    memo[v] = d
    for i in graph[v]:
        if memo[i[0]] != -1:continue
        dfs(i[0],d+i[1])
        
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())
ary = [list(map(int,input().split())) for _ in range(q)]
dfs(k-1,0)
print(*[memo[x-1]+memo[y-1] for x,y in ary],sep="\n")

Submission status: Accepted

Solution code:
n=int(input())
l=[[]for _ in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  l[a-1]+=[[b-1,c]]
  l[b-1]+=[[a-1,c]]
q,k=map(int,input().split())
k-=1
Q=[[k,0]]
c=[0]*n;c[k]=-1
while Q:
  p=[]
  for i,j in Q:
    for x,y in l[i]:
      if c[x]==0:
        c[x]=j+y
        p+=[[x,c[x]]]
  Q=p
c[k]=0
for i in range(q):
  x,y=map(int,input().split())
  print(c[x-1]+c[y-1])

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())

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

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

dist=[-1 for i in range(n)]
dist[k]=0
que=deque()
que.append(k)
while que:
    x=que.popleft()
    for p in tree[x]:
        if dist[p[0]]==-1:
            que.append(p[0])
            dist[p[0]]=dist[x]+p[1]
ans=[]
for i in range(q):
    x,y=map(int,input().split())
    x-=1;y-=1
    ans.append(dist[x]+dist[y])

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
N = int(input())
nl = [list() for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    nl[a].append((b, c))
    nl[b].append((a, c))
Q, K = map(int, input().split())

ans = [-1 for _ in range(N + 1)]
stack = [(K, -1, 0)]  # v, p, c
while len(stack) > 0:
    v, p, c = stack.pop()
    ans[v] = c
    for next_v, next_c in nl[v]:
        if next_v == p:
            continue
        stack.append((next_v, v, c + next_c))
for x, y in [tuple(map(int, input().split())) for _ in range(Q)]:
    print(ans[x] + ans[y])

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from collections import deque as dq
N = int(input())
e = dd(list)
inf = 10 ** 15
for _ in range(N - 1):
  u, v, d = map(int, input().split())
  e[u].append((v, d))
  e[v].append((u, d))
Q, K = map(int, input().split())
d = [inf] * (N + 1)
d[K] = 0
q = dq([])
q.append(K)
while len(q):
  p = q.popleft()
  for t in e[p]:
    temp = d[p] + t[1]
    if d[t[0]] > temp:
      d[t[0]] = temp
      q.append(t[0])
for _ in range(Q):
  u, v = map(int, input().split())
  print(d[u] + d[v])

Submission status: Accepted

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]
count = 1

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]
            count += 1
        else:
            pass
    if count >= n:
        break

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

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(3*10**5) # 大丈夫か？

N = int(input())
edge = [[] for i in range(N)]
# edge[i] : 頂点 i から出る経路の [距離,行先] の隣接リスト
for _ in range(N-1):
    a,b,c = map(int, input().split())
    edge[a-1].append([c,b-1])
    edge[b-1].append([c,a-1])

D = [-1]*N # K からの距離. 未訪問の場合 -1.
# 今回の問題の場合、木なので経路は 1 通りしか無く、
# K から頂点を順に辿りながらコストを足していくだけで良い
def dfs(src, cost):
    D[src] = cost
    for e in edge[src]:
        if D[e[1]] == -1:
            dfs(e[1], cost + e[0])

def main():
    Q,K = map(int, input().split())
    dfs(K-1, 0)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

# 頂点 s からの最短距離を求める (存在しないときはinf)
# n: 頂点数, edge[i]: 頂点 i からの [cost, dst] の list (heapq のため cost が先)
# O(|E|log|V|)
import heapq
def dijkstra(s,n,edge):
    d = [float("inf")] * n # s からの距離
    d[s] = 0
    q = [] # 頂点への距離を管理する。ヒープにする
    for e in edge[s]:
        heapq.heappush(q, e)
    
    while q:
        minedge = heapq.heappop(q)
        v = minedge[1]
        if d[v] < minedge[0]:
            continue # 最小のもの以降はスルー
        d[v] = minedge[0]
        for e in edge[v]:
            heapq.heappush(q, [e[0]+d[v], e[1]])

    return d

def main():
    N = int(input())
    edge = [[] for i in range(N)]
    # edge[i] : 頂点 i から出る経路の [重み,行先] の配列
    for _ in range(N-1):
        a,b,c = map(int, input().split())
        edge[a-1].append([c,b-1])
        edge[b-1].append([c,a-1])

    Q,K = map(int, input().split())
    D = dijkstra(K-1, N, edge)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

import sys 
input = sys.stdin.readline
from collections import deque
def solve():
  n = int(input())
  d = [[]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1].append((b-1,c))
    d[b-1].append((a-1,c))
  q,k = (int(i) for i in input().split())
  #kからの距離を計算する
  d2 = [10**10]*n
  visit = [False]*n
  query = deque([(k-1,0)]) #始点、距離
  while query:
    place,dist = query.pop()
    if visit[place]:
      continue
    else:
      visit[place] = visit
      d2[place] = dist
      for i in range(len(d[place])):
        np,nc = d[place][i]
        if not visit[np]:
          query.append((np,nc+dist))
  for i in range(q):
    x,y = (int(i) for i in input().split())
    print(int(d2[x-1] + d2[y-1]))

solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

n = int(input())
graph = [list() for i in range(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())

def dfs(pre, now, c):
    len_list[now] = min(len_list[now], len_list[pre] + c)

    while graph[now]:
        n, c = graph[now].pop()
        dfs(now, n, c)

len_list = [float("inf")] * (n + 1)
len_list[k] = 0
dfs(k, k, 0)

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

Submission status: Accepted

Solution code:
from collections import deque

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 = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[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: Accepted

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

flag = [True]*N
ques = [[0,K-1]]
D = [0]*N
while ques:
  d1,l1 = heapq.heappop(ques)
  if flag[l1]:
    flag[l1]=False
    D[l1] = d1
    for d2,l2 in node[l1]:
      if flag[l2]:
        heapq.heappush(ques,[d1+d2,l2])
for _ in range(Q):
  x,y = map(int,input().split())
  print(D[x-1]+D[y-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

tmp = []
tree = []

def dfs(node, depth, fr):
    global tmp, tree
    tree[node] = (fr, depth)
    for i, c in tmp[node]:
        if i != fr:
            dfs(i, depth+c, node)

def main():
    global tmp, tree
    n = int(input().strip())
    tmp = [[] for _ in range(n)]
    tree = [0] * n
    for _ in range(n-1):
        a, b, c = map(int, input().strip().split())
        a -= 1
        b -= 1

        if b > a:
            a, b = b, a
        tmp[a].append((b, c))
        tmp[b].append((a, c))

    q, k = map(int, input().strip().split())
    k -= 1
    dfs(k, 0, -1)
    # print(tmp)
    # print(tree)
    for _ in range(q):
        x, y = map(lambda x: x-1, map(int, input().strip().split()))
        print(tree[x][1] + tree[y][1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

depth = [""] * N

lis = [0] * N

dic = {}

for i in range(N-1):

    a,b,c = map(int,input().split())

    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append([b,c])
    dic[b].append([a,c])

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

queue = deque([])
queue.append(K)
depth[K] = 0

while len(queue) > 0:

    now = queue.pop()

    if now not in dic:
        continue

    for bc in dic[now]:

        b = bc[0]
        c = bc[1]
        
        if depth[b] != "":
            continue

        depth[b] = depth[now] + 1
        lis[b] = lis[now] + c
        queue.append(b)

for i in range(Q):

    x,y = map(int,input().split())

    x -= 1
    y -= 1

    print (lis[x] + lis[y])

Submission status: Accepted

Solution code:
# 隣接リスト表現　with weight
from collections import deque

def DFS(ls,start):
    que = deque([])
    que.append(start)
    visited = [0 for _ in range(len(ls))]

    while len(que):
        now = que.popleft()
        for nex in ls[now]:

            if visited[nex[0]]==0:
                que.append(nex[0])
                visited[nex[0]] = visited[now] + nex[1]

    return visited




def main():
    n = int(input())
    ls = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a,b,c = map(int,input().split())
        ls[a].append([b,c])
        ls[b].append([a,c])
    q,k = map(int,input().split())
    x,y = [0 for _ in range(q)],[0 for _ in range(q)]
    for i in range(q):
        x[i],y[i] = map(int,input().split())
    
    memo = DFS(ls,k)

    for i in range(q):
        print(memo[x[i]]+memo[y[i]])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append((b, c))
    tree[b].append((a, c))
q, k = map(int, input().split())
k -= 1

visited = [-1]*n
todo = deque()
visited[k] = 0
todo.append(k)

while todo:
    v = todo.pop()
    d = visited[v]
    for to, cost in tree[v]:
        if visited[to] == -1:
            visited[to] = d+cost
            todo.append(to)
            
ans = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans.append(visited[x] + visited[y])

print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
d_list = [[] for _ in range(N+1)]
costs = [0] * (N+1)
for _ in range(N-1):
  a, b, c = map(int, input().split())
  d_list[a].append((a, b, c))
  d_list[b].append((b, a, c))
Q, K = map(int, input().split())
que = deque([])
for e in d_list[K]:
  que.append(e)
while len(que) > 0:
  _from, _to,  _cost = que.popleft()
  costs[_to] += costs[_from] + _cost
  for e in d_list[_to]:
    if e[1] != _from:
      que.append(e)
for _ in range(Q):
  f, t = map(int, input().split())
  print(costs[f] + costs[t])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

input = sys.stdin.readline

n = int(input())

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


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


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

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

input = sys.stdin.readline

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

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


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


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

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

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

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

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

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

que = deque([])
que.append(K - 1)
dist = [-1 for _ in range(N)]
dist[K - 1] = 0
while len(que) > 0:
	node = que.popleft()
	for edge in tree[node]:
		if dist[edge[0]] == -1:
			que.append(edge[0])
			dist[edge[0]] = dist[node] + edge[1]

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

Submission status: Accepted

Solution code:
import heapq as hp

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

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

INF = int(1E17)

D = [INF for _ in range(N)] # 頂点iへの最短距離がD[i]
D[K-1] = 0 
q = [] # しまっていく優先度付きキュー
hp.heappush(q, (0, K-1))

while q:
    nd, np = hp.heappop(q) # 一番距離が近いものを取ってくる
    if D[np] < nd: # 追加した後の残骸は見ない
        continue
    for d, p in graph[np]:
        if D[p] > D[np] + d: # 隣接するやつの中で今よりも近くなれるなら更新
            D[p] = D[np] + d
            hp.heappush(q, (D[p], p))

for x, y in XY:
    print(D[x-1]+D[y-1])

Submission status: Accepted

Solution code:
from collections import deque
n,*t=map(int,open(0).read().split())
con=[[] for _ in range(n)]
dist_f_k=[0]*n
l1,l2=t[:3*n-3],t[3*n-1:]

for a,b,c in zip(*[iter(l1)]*3):
	con[a-1].append((b-1,c))
	con[b-1].append((a-1,c))

k=t[3*n-2]
que=deque([k-1])
while que:
	cur=que.popleft()
	for nxt,dd in con[cur]:
		if dist_f_k[nxt]==0 and nxt!=k-1:
			que.append(nxt)
			dist_f_k[nxt]=dist_f_k[cur]+dd

for x,y in zip(*[iter(l2)]*2):
	print(dist_f_k[x-1]+dist_f_k[y-1])

Submission status: Accepted

Solution code:
def solve():
	from collections import deque
	n,*t=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	dist_f_k=[0]*n
	l1,l2=t[:3*n-3],t[3*n-1:]

	for a,b,c in zip(*[iter(l1)]*3):
		con[a-1].append((b-1,c))
		con[b-1].append((a-1,c))

	k=t[3*n-2]
	que=deque([k-1])
	while que:
		cur=que.popleft()
		for nxt,dd in con[cur]:
			if dist_f_k[nxt]==0 and nxt!=k-1:
				que.append(nxt)
				dist_f_k[nxt]=dist_f_k[cur]+dd

	for x,y in zip(*[iter(l2)]*2):
		print(dist_f_k[x-1]+dist_f_k[y-1])
		
if __name__=="__main__":
	solve()