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: Runtime Error

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

def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = [None] * N
    d = [float("inf")] * N
    Q.append(start)
    d[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if b != prev[a]:
                Q.append(b)
                prev[b] = a
                d[b] = d[a] + c
    return d

def DFS(N, graph, a, p, d):
    dd[a] = d
    for b, c in graph[a]:
        if b == p or dd[b] != 0:
            continue
        else:
            DFS(N, graph, b, a, d + c)

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

Q, K =(int(i) for i in input().split())
dd = [0] * N
DFS(N, graph, K-1, -1, 0)
for i in range(Q):
    x, y = (int(a) for a in input().split())
    print(dd[x-1] + dd[y-1])

Submission status: Runtime Error

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

def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = [None] * N
    d = [float("inf")] * N
    Q.append(start)
    d[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if b != prev[a]:
                Q.append(b)
                prev[b] = a
                d[b] = d[a] + c
    return d

def DFS(N, graph, a, p, d):
    dd[a] = d
    for b, c in graph[a]:
        if b == p or dd[b] != None:
            continue
        else:
            DFS(N, graph, b, a, d + c)

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

Q, K =(int(i) for i in input().split())
dd = [None] * N
DFS(N, graph, K-1, -1, 0)
for i in range(Q):
    x, y = (int(a) for a in input().split())
    print(dd[x-1] + dd[y-1])

Submission status: Runtime Error

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

def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = [None] * N
    d = [float("inf")] * N
    Q.append(start)
    d[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if b != prev[a]:
                Q.append(b)
                prev[b] = a
                d[b] = d[a] + c
    return d

def DFS(N, graph, a, p, d):
    dd[a] = d
    for b, c in graph[a]:
        if b == p:
            continue
        else:
            DFS(N, graph, b, a, d + c)

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

Q, K =(int(i) for i in input().split())
dd = [None] * N
DFS(N, graph, K-1, -1, 0)
for i in range(Q):
    x, y = (int(a) for a in input().split())
    print(dd[x-1] + dd[y-1])

Submission status: Runtime Error

Solution code:
def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    d = [float("inf")] * N
    Q.append(start)
    d[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if not b in V:
                Q.append(b)
                d[b] = d[a] + c
    return d

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

Q, K =(int(i) for i in input().split())

d = BFS(N, graph, K-1)
for i in range(Q):
    x, y = (int(a) for a in input().split())
    print(d[x-1] + d[y-1])

Submission status: Runtime Error

Solution code:
import sys
#limit=sys.getrecursionlimit()
sys.setrecursionlimit(100000)
#sys.setrecursionlimit(1000000000)

V=int(input().strip())
E=V-1
inf=3*10**15
G=[]
dist=[inf]*V

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1])

visited=[False]*V
def dfs(v,p,d):
    #global d
    dist[v]=d
    for q in G[v]:
        if q[1]==p:
            continue
        dfs(q[1],v,d+q[0])

Q, K=map(int,input().strip().split(' '))
K-=1 #0-indexedに直す

dfs(K,-1,0)

x=[]
y=[]

for i in range(Q):
    xt, yt=map(int,input().strip().split(' '))
    x.append(xt-1)#0-indexedに直して入れる
    y.append(yt-1)#0-indexedに直して入れる
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])

Submission status: Runtime Error

Solution code:
import sys
#limit=sys.getrecursionlimit()
sys.setrecursionlimit(100000)
#sys.setrecursionlimit(1000000000)

fileobj=open('subtask_1_28.txt','rt')

V=int(fileobj.readline().strip())
E=V-1
inf=3*10**15
G=[]
dist=[inf]*V
visited=[False]*V

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,fileobj.readline().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1])

def dfs(v,p,d):
    #global d
    dist[v]=d
    visited[v]=True
    for q in G[v]:
        if q[1]==p:
            continue
        elif visited[q[1]]!=True:
            dfs(q[1],v,d+q[0])

Q, K=map(int,fileobj.readline().strip().split(' '))
K-=1 #0-indexedに直す

dfs(K,-1,0)

x=[]
y=[]

for i in range(Q):
    xt, yt=map(int,fileobj.readline().strip().split(' '))
    x.append(xt-1)#0-indexedに直して入れる
    y.append(yt-1)#0-indexedに直して入れる
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])

Submission status: Runtime Error

Solution code:
V=int(input().strip())
E=V-1
inf=3*10**15
G=[]
dist=[inf]*V

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1])

visited=[False]*V
def dfs(v,p,d):
    #global d
    dist[v]=d
    for q in G[v]:
        if q[1]==p:
            continue
        dfs(q[1],v,d+q[0])

Q, K=map(int,input().strip().split(' '))
K-=1 #0-indexedに直す

dfs(K,-1,0)

x=[]
y=[]

for i in range(Q):
    xt, yt=map(int,input().strip().split(' '))
    x.append(xt-1)#0-indexedに直して入れる
    y.append(yt-1)#0-indexedに直して入れる
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])

Submission status: Runtime Error

Solution code:
N = int(input())
X, Y = [], []

tree = {key+1: [] for key in range(N)}  # 木構造はノードをキーにする辞書にしておく
# 必要なのは、あるノードを指定したときに、隣り合うノードと、コスト
#[(隣のノード, コスト)]の順で格納する

for n in range(N - 1):
    a, b, c = list(map(int, input().split()))
    tree[a].append((b, c))
    tree[b].append((a, c))  # 方向に依存しない格納

for n in tree.keys():
    tree[n] = list(set(tree[n]))

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

cost = {}  # Kがkeyに行くまでにかかるコストの辞書


def dfs(v, p, d):
    """
    深さ優先探索
    再帰的に処理する
    args:
        v: 現在の頂点
        p: vの親(訪問元)
        d: 現在の距離
    """
    cost[v] = d
    for i, co in tree[v]:
        if i == p:
            continue
        dfs(i, v, d + co)


dfs(K, 0, 0)

ans = []
for q in range(Q):
    x, y = list(map(int, input().split()))
    ans.append(cost[x] + cost[y])

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
X, Y = [], []

tree = {key+1: [] for key in range(N)}  # 木構造はノードをキーにする辞書にしておく
# 必要なのは、あるノードを指定したときに、隣り合うノードと、コスト
#[(隣のノード, コスト)]の順で格納する

for n in range(N - 1):
    a, b, c = list(map(int, input().split()))
    tree[a].append((b, c))
    tree[b].append((a, c))  # 方向に依存しない格納

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

cost = {}  # Kがkeyに行くまでにかかるコストの辞書


def dfs(v, p, d):
    """
    深さ優先探索
    再帰的に処理する
    args:
        v: 現在の頂点
        p: vの親(訪問元)
        d: 現在の距離
    """
    cost[v] = d
    for i, co in tree[v]:
        if i == p:
            continue
        dfs(i, v, d + co)


dfs(K, 0, 0)


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

Submission status: Runtime Error

Solution code:
N = int(input())
X, Y = [], []

tree = {key+1: [] for key in range(N)}  # 木構造はノードをキーにする辞書にしておく
# 必要なのは、あるノードを指定したときに、隣り合うノードと、コスト
#[(隣のノード, コスト)]の順で格納する

for n in range(N - 1):
    a, b, c = list(map(int, input().split()))
    tree[a].append((b, c))
    tree[b].append((a, c))  # 方向に依存しない格納

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

cost = {}  # Kがkeyに行くまでにかかるコストの辞書


def dfs(v, p, d):
    """
    深さ優先探索
    再帰的に処理する
    args:
        v: 現在の頂点
        p: vの親(訪問元)
        d: 現在の距離
    """
    cost[v] = d
    for i, co in tree[v]:
        if i == p:
            continue
        dfs(i, v, d + co)


dfs(K, 0, 0)

ans = []
for q in range(Q):
    x, y = list(map(int, input().split()))
    ans.append(cost[x] + cost[y])

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
X, Y = [], []

tree = {key+1: [] for key in range(N)}  # 木構造はノードをキーにする辞書にしておく
# 必要なのは、あるノードを指定したときに、隣り合うノードと、コスト
#[(隣のノード, コスト)]の順で格納する

for n in range(N - 1):
    a, b, c = list(map(int, input().split()))
    tree[a].append((b, c))
    tree[b].append((a, c))  # 方向に依存しない格納

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

cost = {}  # Kがkeyに行くまでにかかるコストの辞書


def dfs(v, p, d):
    """
    深さ優先探索
    再帰的に処理する
    args:
        v: 現在の頂点
        p: vの親(訪問元)
        d: 現在の距離
    """
    cost[v] = d
    for i, co in tree[v]:
        if i == p:
            continue
        dfs(i, v, d + co)


dfs(K, -1, 0)

ans = []
for q in range(Q):
    x, y = list(map(int, input().split()))
    ans.append(cost[x] + cost[y])

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
def get_path(start, goal, prev):
    path = []
    now = goal
    path.append(now)
    while True:
        path.append(prev[now])
        if prev[now] == start: break
        now = prev[now]
    path.reverse()
    return path

def search(glaph, start, goal):
    MAX_VAL = 0x10000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    return [get_path(start, goal, prev), cost[goal]]

N = int(input())
route = [[0 for i in range(N)] for j in range(N)]
for i in range(N - 1):
    a, b, d = map(int, input().split())
    route[a-1][b-1] = d
    route[b-1][a-1] = d
Q, K = map(int, input().split())

for i in range(Q):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    path, cost1 = search(route, x, K - 1)
    path, cost2 = search(route, K - 1, y)
    cost = cost1 + cost2
    print(cost)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

#define MAX_N 100000

vector<vector<pair<int,int>>> p;
vector<pair<int,int>> xy;
vector<ll> d;

void solver(int a, int b, ll c){
  for(pair<int, int> q : p[a]) {
    if(q.first != b){
      d[q.first] = c + q.second;
      solver(q.first, a, d[q.first]);
    }
  }
}

int main(){
  ll n, q, k;
  cin >> n;

  p.resize(n);
  REP(i,n-1){
    ll a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    p[a].push_back(make_pair(b,c));
    p[b].push_back(make_pair(a,c));
  }

  cin >> q >> k;
  k--;

  REP(i,q){
    int x, y;
    cin >> x >> y;
    xy.push_back(make_pair(x-1,y-1));
  }

  d.resize(n);
  solver(k, -1, 0);

  REP(i,q){
    cout << d[xy[i].first] + d[xy[i].second] << endl;
  }

  return 0;
}

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

path = defaultdict(lambda: [])
N = int(input())
for _ in range(N-1):
    a, b, c = inpl()
    path[a].append((b,c))
    path[b].append((a,c))

ctr = 1
Q, K = inpl()
now = [K]
dist = [0 for _ in range(N+1)]
while True:
    for na in now.copy():
        na = now.pop()
        for nb, nc in path[na]:
            dist[nb] = dist[na] + nc
            path[nb].remove((na,nc))
            now.add(nb)
            ctr += 1
    if ctr >=  N:
        break
for i in range(Q):
    x, y = inpl()
    print(dist[x]+dist[y])

Submission status: Runtime Error

Solution code:
n=int(input())
abc=[list(map(int,input().split())) for _ in range(n-1)]
q,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(q)]

z=[[] for _ in range(n)]
for a,b,c in abc:
    z[a-1].append([b-1,c])
    z[b-1].append([a-1,c])

depth=[0 for _ in range(100010)]
def dfs(v,p,d):
    depth[v]=d
    for t in z[v]:
        if t[0]==p:
            continue
        dfs(t[0],v,d+t[1])
dfs(k-1,-1,0)
for x,y in xy:
    print(depth[x-1]+depth[y-1])

Submission status: Runtime Error

Solution code:
n=int(input())
abc=[list(map(int,input().split())) for _ in range(n-1)]
q,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(q)]

z=[[] for _ in range(n)]
for a,b,c in abc:
    z[a-1].append([b-1,c])
    z[b-1].append([a-1,c])

depth=[0 for _ in range(n)]
def dfs(v,p,d):
    depth[v]=d
    for t in z[v]:
        if t[0]==p:
            continue
        dfs(t[0],v,d+t[1])
dfs(k-1,-1,0)
for x,y in xy:
    print(depth[x-1]+depth[y-1])

Submission status: Runtime Error

Solution code:
import copy
import sys

class Node:
    def __init__(self, id):
        self.id = id
        self.path = {}
    def __str__(self):
        return "id: " + str(self.id) + " path: " + str(self.path)

N = int(input())
nodes = []
for i in range(N):
    nodes.append(Node(i))

for i in range(N-1):
    from_id, to_id, weight = [ int(x) - 1 for x in input().split() ]
    weight += 1
    nodes[from_id].path[to_id] = weight
    nodes[to_id].path[from_id] = weight

Q, K = [ int(x) for x in input().split() ]
K -= 1

smallest_path_weights_from_K = []
for i in range(N):
    smallest_path_weights_from_K.append(sys.maxsize)
smallest_path_weights_from_K[K] = 0

def find_smallest_path_from_K(node_current):
#    for i, w in nodes[node_current].path.items():
    for i, w in sorted(nodes[node_current].path.items(), key=lambda x: x[1]):
        old_cost = smallest_path_weights_from_K[i]
        new_cost = smallest_path_weights_from_K[node_current] + w
        if old_cost > new_cost:
            smallest_path_weights_from_K[i] = new_cost
            find_smallest_path_from_K(i)

find_smallest_path_from_K(K)

for i in range(Q):
    start, goal = [ int(x) - 1 for x in input().split()]
    print(smallest_path_weights_from_K[start] + smallest_path_weights_from_K[goal])

Submission status: Runtime Error

Solution code:
import copy
import sys

class Node:
    def __init__(self, id):
        self.id = id
        self.path = {}
    def __str__(self):
        return "id: " + str(self.id) + " path: " + str(self.path)

N = int(input())
nodes = []
for i in range(N):
    nodes.append(Node(i))

for i in range(N-1):
    from_id, to_id, weight = [ int(x) - 1 for x in input().split() ]
    weight += 1
    nodes[from_id].path[to_id] = weight
    nodes[to_id].path[from_id] = weight

Q, K = [ int(x) for x in input().split() ]
K -= 1

smallest_path_weights_from_K = []
for i in range(N):
    smallest_path_weights_from_K.append(sys.maxsize)
smallest_path_weights_from_K[K] = 0

def find_smallest_path_from_K(node_current):
    for i, w in nodes[node_current].path.items():
        old_cost = smallest_path_weights_from_K[i]
        new_cost = smallest_path_weights_from_K[node_current] + w
        if old_cost > new_cost:
            smallest_path_weights_from_K[i] = new_cost
            find_smallest_path_from_K(i)

find_smallest_path_from_K(K)

for i in range(Q):
    start, goal = [ int(x) - 1 for x in input().split()]
    print(smallest_path_weights_from_K[start] + smallest_path_weights_from_K[goal])

Submission status: Runtime Error

Solution code:
import copy
import sys

class Node:
    def __init__(self, id):
        self.id = id
        self.path = {}
    def __str__(self):
        return "id: " + str(self.id) + " path: " + str(self.path)

N = int(input())
nodes = []
for i in range(N):
    nodes.append(Node(i))

for i in range(N-1):
    from_id, to_id, weight = [ int(x) - 1 for x in input().split() ]
    weight += 1
    nodes[from_id].path[to_id] = weight
    nodes[to_id].path[from_id] = weight

Q, K = [ int(x) for x in input().split() ]
K -= 1

def find_smallest_path(id_new, goal, passed_nodes):
    passed_nodes.append(id_new)
    if id_new == goal:
        return 0

    smallest = -1
    cost = 0
    for i, w in nodes[id_new].path.items():
        if not i in passed_nodes:
            cost = w + find_smallest_path(i, goal, copy.deepcopy(passed_nodes))
            if smallest == -1:
                smallest = cost
            else:
                if cost < smallest:
                    smallest = cost
    if smallest == -1:
        return sys.maxsize
    return smallest

smallest_path_weights = []
for i in range(N):
    smallest_path_weights.append(find_smallest_path(i, K, []))

# print("smallest", smallest_path_weights)

for i in range(Q):
    start, goal = [ int(x) - 1 for x in input().split()]
    print(smallest_path_weights[start] + smallest_path_weights[goal])

Submission status: Runtime Error

Solution code:
# coding:utf-8
# https://beta.atcoder.jp/contests/abc075/tasks/abc075_c
from collections import defaultdict
import sys
# import numpy as np  # importするだけで200msくらいかかる！！！！！！！！！！！！１１

N = [int(i) for i in sys.stdin.readline().strip().split()]
N = N[0]

edges = defaultdict(int)
hopable = defaultdict(list)
for _ in range(N-1):
  l = sys.stdin.readline().strip()
  l = [int(i) for i in l.split()]
  a, b, c = l[0]-1, l[1]-1, l[2]
  edges[(a, b)] = c
  edges[(b, a)] = c
  hopable[a].append(b)
  hopable[b].append(a)

Q, K = [int(i) for i in sys.stdin.readline().strip().split()]
K = K - 1
query = []
for _ in range(Q):
  x, y = [int(i) for i in sys.stdin.readline().strip().split()]
  query.append((x-1, y-1))

def trace(current, path_and_weight):
  path, weight = path_and_weight
  unfinished_nodes = set([target for target in hopable[current] if  target not in path])
  subtrees = [path_and_weight]
  for target in unfinished_nodes:
    subtrees += trace(target, [path + [target], weight + edges[(current, target)]])
  return subtrees
dist_map = [0 for _ in range(N)]
distances = trace(K, [[K], 0])

for path, weight in distances:
  dist_map[path[-1]] = int(weight)
for x, y in query:
  print(dist_map[x] + dist_map[y])

Submission status: Runtime Error

Solution code:
# coding:utf-8
# https://beta.atcoder.jp/contests/abc075/tasks/abc075_c

import sys
import itertools
import numpy as np
N = [int(i) for i in sys.stdin.readline().split()]
N = N[0]
edges = [[] for _ in range(N)]
edge_mat = np.zeros((N, N))

def flatten(l):
  return list(itertools.chain.from_iterable(l))

for _ in range(N-1):
  l = sys.stdin.readline()
  l = [int(i) for i in l.strip().split()]
  a, b, c = l[0]-1, l[1]-1, l[2]
  edge_mat[a][b] = c
  edge_mat[b][a] = c

Q, K = [int(i) for i in sys.stdin.readline().split()]
K = K - 1
query = []
for _ in range(Q):
  x, y = [int(i) for i in sys.stdin.readline().split()]
  query.append((x-1, y-1))

def trace(current, path_and_weight):
  path, weight = path_and_weight
  unfinished_nodes = [target for target in range(N) if edge_mat[current][target] and target not in path]
  subtrees = [path_and_weight]
  for target in unfinished_nodes:
    subtrees += trace(target, [path + [target], weight + edge_mat[current][target]])
  return subtrees
dist_map = [0 for _ in range(N)]
distances = trace(K, [[K], 0])

for path, weight in distances:
  dist_map[path[-1]] = int(weight)
for x, y in query:
  print(dist_map[x] + dist_map[y])

Submission status: Runtime Error

Solution code:
# coding:utf-8
# https://beta.atcoder.jp/contests/abc075/tasks/abc075_c


import sys
import itertools
import numpy as np

N = [int(i) for i in sys.stdin.readline().split()]
N = N[0]
edges = [[] for _ in range(N)]
edge_mat = np.zeros((N, N))

def flatten(l):
  return list(itertools.chain.from_iterable(l))

for _ in range(N-1):
  l = sys.stdin.readline()
  l = [int(i) for i in l.strip().split()]
  a, b, c = l[0]-1, l[1]-1, l[2]
  edge_mat[a][b] = c
  edge_mat[b][a] = c

Q, K = [int(i) for i in sys.stdin.readline().split()]
K = K - 1
query = []
for _ in range(Q):
  x, y = [int(i) for i in sys.stdin.readline().split()]
  query.append((x-1, y-1))

def trace(current, path_and_weight):
  path, weight = path_and_weight
  unfinished_nodes = [target for target in range(N) if edge_mat[current][target] and target not in path]
  subtrees = [path_and_weight]
  for target in unfinished_nodes:
    subtrees += trace(target, [path + [target], weight + edge_mat[current][target]])
  return subtrees
dist_map = [0 for _ in range(N)]
distances = trace(K, [[K], 0])

for path, weight in distances:
  dist_map[path[-1]] = int(weight)
for x, y in query:
  print(dist_map[x] + dist_map[y])

Submission status: Runtime Error

Solution code:
# coding:utf-8
# https://beta.atcoder.jp/contests/abc075/tasks/abc075_c

import sys
import itertools
import numpy as np

N = [int(i) for i in sys.stdin.readline().split()]
N = N[0]
edges = [[] for _ in range(N)]
edge_mat = np.zeros((N, N))

def flatten(l):
  return list(itertools.chain.from_iterable(l))

for _ in range(N-1):
  l = sys.stdin.readline()
  l = [int(i) for i in l.strip().split()]
  a, b, c = l[0]-1, l[1]-1, l[2]
  edge_mat[a][b] = c
  edge_mat[b][a] = c

Q, K = [int(i) for i in sys.stdin.readline().split()]
K = K - 1
query = []
for _ in range(Q):
  x, y = [int(i) for i in sys.stdin.readline().split()]
  query.append((x-1, y-1))

def trace(current, path_and_weight):
  path, weight = path_and_weight
  unfinished_nodes = [target for target in range(N) if edge_mat[current][target] and target not in path]
  subtrees = [path_and_weight]
  for target in unfinished_nodes:
    subtrees += trace(target, [path + [target], weight + edge_mat[current][target]])
  return subtrees
dist_map = np.zeros(N, dtype=np.int32)
distances = trace(K, [[K], 0])

for path, weight in distances:
  dist_map[path[-1]] = int(weight)

for x, y in query:
  print(dist_map[x] + dist_map[y])

Submission status: Runtime Error

Solution code:
import numpy as np
import math

# K = int(input())
# N, K = map(int, input().split())
# A = list(map(int, input().split()))

N = int(input())

E = dict()

cost = dict()

for n in range(N-1):
    s, t, c = map(int, input().split())
    s = s-1
    t = t-1
    if s not in E:
        E[s] = []
    if t not in E:
        E[t] = []
    E[s].append(t)
    E[t].append(s)
    if s <= t:
        cost[(s, t)] = c
    else:
        cost[(t, s)] = c

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


D = np.full(N, -1, dtype='q')

D[K-1] = 0

def calc(v, cv):
    for n in E[v]:
        if D[n] == -1:
            if n <= v:
                c = cost[(n, v)]
            else:
                c = cost[(v, n)]
            D[n] = c + cv
            calc(n, D[n])

calc(K-1, 0)

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

Submission status: Runtime Error

Solution code:
import numpy as np
import math

# K = int(input())
# N, K = map(int, input().split())
# A = list(map(int, input().split()))

N = int(input())

E = dict()

cost = dict()

for n in range(N-1):
    s, t, c = map(int, input().split())
    s = s-1
    t = t-1
    if s not in E:
        E[s] = []
    if t not in E:
        E[t] = []
    E[s].append(t)
    E[t].append(s)
    if s <= t:
        cost[(s, t)] = c
    else:
        cost[(t, s)] = c

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


D = np.full(N, -1, dtype='q')

D[K-1] = 0

def calc(v, cv):
    for n in range(N):        
        if n in E[v] and D[n] == -1:
            if n <= v:
                c = cost[(n, v)]
            else:
                c = cost[(v, n)]
            D[n] = c + cv
            calc(n, D[n])

calc(K-1, 0)

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

Submission status: Runtime Error

Solution code:
import numpy as np
import math

# K = int(input())
# N, K = map(int, input().split())
# A = list(map(int, input().split()))

N = int(input())

E = np.full((N, N), -1, dtype='q')

for n in range(N-1):
    s, t, c = map(int, input().split())
    s = s-1
    t = t-1
    E[s][t] = c
    E[t][s] = c

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


D = np.full(N, -1, dtype='q')

D[K-1] = 0

def calc(v, cv):
    for n in range(N):
        if E[v][n] >= 0 and D[n] == -1:
            D[n] = E[v][n] + cv
            calc(n, D[n])

calc(K-1, 0)

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

Submission status: Runtime Error

Solution code:
n = int(input())

edges = [[] for _ in xrange(n)]
distance = [-1 for _ in xrange(n)]

for _ in xrange(n-1):
	f,t,c = map(int,raw_input().split())

	f -= 1
	t -= 1

	edges[f].append((t,c))
	edges[t].append((f,c))

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

def dfs(v,c):
	if distance[v] == -1:
		distance[v] = c
		for to,cost in edges[v]:
			dfs(to,c+cost)

dfs(k,0)

for _ in xrange(q):
	x,y = map(int,raw_input().split())
	x -= 1
	y -= 1
	print distance[x] + distance[y]

Submission status: Runtime Error

Solution code:
n = int(input())

edges = [[] for i in range(n)]
distance = [-1 for i in range(n)]

for i in range(n-1):
	f,t,c = map(int,raw_input().split())

	f -= 1
	t -= 1

	edges[f].append([t,c])
	edges[t].append([f,c])

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

def dfs(v,c):
	if distance[v] == -1:
		distance[v] = c
		for to,cost in edges[v]:
			dfs(to,c+cost)

dfs(k,0)

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

Submission status: Runtime Error

Solution code:
n = int(input())

edges = [[] for i in range(n)]
distance = [-1 for i in range(n)]

for i in range(n-1):
	f,t,c = map(int,raw_input().split())

	f -= 1
	t -= 1

	edges[f].append([t,c])
	edges[t].append([f,c])

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

def dfs(v,c):
	if distance[v] == -1:
		distance[v] = c
		for to,cost in edges[v]:
			print to,cost
			dfs(to,c+cost)

dfs(k,0)

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

Submission status: Runtime Error

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

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

Q, K = [int(t) for t in input().split()]

def dfs(s):
    '''深さ優先探索でKからの距離を計算'''
    global dist
    for t, c in edge[s]:
        if dist[t] == None:
            dist[t] = dist[s] + c
            dfs(t)

dist = [None] * (N + 1)  # Kからの距離
dist[K] = 0
dfs(K)

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

Submission status: Runtime Error

Solution code:
N = int(input())
adj_list = [[] for _ in range(N)]
depth = [float('inf')] * 100010


def dfs(v, p, d):
    depth[v] = d
    for adj in adj_list[v]:
        if adj[0] == p:
            continue
        dfs(adj[0], v, d + adj[1])


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

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

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

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

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


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


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

Submission status: Runtime Error

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


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


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