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:
n = int(input())
a = [0]*n
b = [0]*n
c = [0]*n

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

def askdis(st,cur,en,d=0):
    if cur == en:
        dp[st-1][en-1]=dp[en-1][st-1]=min(dp[st-1][en-1],d)
        return

    for i in range(n-1):
        if a[i]==cur and flag[i]:
            flag[i]=False
            askdis(st,b[i],en,d+c[i])
            flag[i]=True
        if b[i]==cur and flag[i]:
            flag[i]=False
            askdis(st,a[i],en,d+c[i])
            flag[i]=True

dp = [ [10**10]*(n) for _ in range(n)]

for i in range(1,n+1):
    for j in range(i+1,n+1):
        askdis(i,i,j)

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

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

Submission status: Time Limit Exceeded

Solution code:
import collections

N = int(input())

Tree = collections.defaultdict(list)

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

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

def bfs(tree, s, distance):
    queue = [s]
    visit = [s]
    distance[s] = 0

    while queue:
        v = queue.pop(0)
        for child in tree[v]:
            if child[0] not in visit:
                distance[child[0]] = distance[v] + child[1]
                visit.append(child[0])
                queue.append(child[0])

distance = {}
bfs(Tree, k, distance)

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

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
import sys

def main():
    L = []
    S = [x for x in sys.stdin]
    N = int(S.pop(0))
    D = [0] * (N+1)
    k = [1] * (N+1)
    sumk = 0
    for i in range(N-1):
        a, b, c = map(int, S[i].split())
        D[b] = (i, a)
        L.append(c)
    Q, K = map(int, S[N-1].split())
    while D[K]:
        a, K = D[K]
        k[a] = -1
        sumk += L[a]
    memo = {}
    for i in range(N, N+Q):
        x, y = map(int, S[i].split())
        tx, ty = x, y
        xsum = ysum = sumk
        if x not in memo:
            while D[tx]:
                a, tx = D[tx]
                xsum += L[a] * k[a]
            memo[x] = xsum
        if y not in memo:
            while D[ty]:
                a, ty = D[ty]
                ysum += L[a] * k[a]
            memo[y] = ysum
        sys.stdout.write(str(memo[x] + memo[y]) + '\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
import sys

def main():
    L = []
    N = int(sys.stdin.readline())
    D = [0] * (N+1)
    k = [1] * (N+1)
    sumk = 0
    for i in range(N-1):
        a, b, c = map(int, sys.stdin.readline().split())
        D[b] = (i, a)
        L.append(c)
    Q, K = map(int, sys.stdin.readline().split())
    while D[K]:
        a, K = D[K]
        k[a] = -1
        sumk += L[a]
    sumk *= 2
    for i in range(N, N+Q):
        x, y = map(int, sys.stdin.readline().split())
        ans = sumk
        while D[x]:
            a, x = D[x]
            ans += L[a] * k[a]
        while D[y]:
            a, y = D[y]
            ans += L[a] * k[a]
        sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
import sys

def main():
    L = []
    S = [x for x in sys.stdin]
    N = int(S.pop(0)) + 1
    D = [0] * N
    k = [1] * N
    sumk = 0
    for i in range(N-2):
        a, b, c = S[i].split()
        D[int(b)] = (i, int(a))
        L.append(int(c))
    Q, K = map(int, S[N-2].split())
    while D[K]:
        a, K = D[K]
        k[a] = -1
        sumk += L[a]
    sumk *= 2
    for i in range(N-1, N-1+Q):
        xs, ys = S[i].split()
        x, y = int(xs), int(ys)
        ans = sumk
        while D[x]:
            a, x = D[x]
            ans += L[a] * k[a]
        while D[y]:
            a, y = D[y]
            ans += L[a] * k[a]
        sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
import sys

def main():
    L = []
    S = [x for x in sys.stdin]
    N = int(S.pop(0)) + 1
    D = [0] * N
    k = [1] * N
    sumk = 0
    for i in range(N-2):
        a, b, c = S.pop(0).split()
        D[int(b)] = (i, int(a))
        L.append(int(c))
    Q, K = map(int, S.pop(0).split())
    while D[K]:
        a, K = D[K]
        k[a] = -1
        sumk += L[a]
    sumk *= 2
    for i in range(Q):
        xs, ys = S.pop(0).split()
        x, y = int(xs), int(ys)
        ans = sumk
        while D[x]:
            a, x = D[x]
            ans += L[a] * k[a]
        while D[y]:
            a, y = D[y]
            ans += L[a] * k[a]
        sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
import sys

def main():
    L = []
    S = [x for x in sys.stdin]
    N = int(S[0])
    S.pop(0)
    D = [0] * (N+1)
    k = [1] * (N+1)
    sk = 0
    for i in range(N-1):
        a, b, c = map(int, S[i].split())
        D[b] = (i, a)
        L.append(c)
    Q, K = map(int, S[N-1].split())
    while D[K]:
        a, K = D[K]
        k[a] = -1
        sk += L[a]
    sk *= 2
    for i in range(N, N+Q):
        x, y = map(int, S[i].split())
        ans = sk
        while D[x]:
            a, x = D[x]
            ans += L[a] * k[a]
        while D[y]:
            a, y = D[y]
            ans += L[a] * k[a]
        sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
import sys

def main():
    L = []
    S = [x for x in sys.stdin]
    N = int(S[0])
    D = [0] * (N+1)
    k = [1] * (N+1)
    sk = 0
    for i in range(N-1):
        a, b, c = map(int, S[1+i].split())
        D[b] = (i, a)
        L.append(c)
    Q, K = map(int, S[N].split())
    while D[K]:
        a, K = D[K]
        k[a] = -1
        sk += L[a]
    sk *= 2
    for i in range(N+1, N+1+Q):
        x, y = map(int, S[i].split())
        ans = sk
        while D[x]:
            a, x = D[x]
            ans += L[a] * k[a]
        while D[y]:
            a, y = D[y]
            ans += L[a] * k[a]
        sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
import sys

def main():
    L = []
    S = [x for x in sys.stdin]
    N = int(S[0])
    D = [0] * (N+1)
    k = [0] * (N+1)
    for i in range(N-1):
        a, b, c = map(int, S[1+i].split())
        D[b] = (i, a)
        L.append(c)
    def f(n):
        s = 0
        while D[n]:
            a, n = D[n]
            k[a] = 1
            s += L[a]
        return s
    Q, K = map(int, S[N].split())
    sk = f(K)
    def f2(n, s):
        while D[n]:
            a, n = D[n]
            if k[a]:
                s -= L[a]
            else:
                s += L[a]
        return s
    for i in range(N+1, N+1+Q):
        x, y = map(int, S[i].split())
        sys.stdout.write(str(f2(x, sk) + f2(y, sk)) + '\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
import sys

def main():
    q = (1, -1)
    L = []
    D = {}
    S = [x for x in sys.stdin]
    N = int(S[0])
    for i in range(N-1):
        a, b, c = map(int, S[1+i].split())
        D[b] = (i, a)
        L.append(c)
    def f(n):
        r = []
        while n in D:
            a, n = D[n]
            r.append(a)
        return sum(L[i] for i in r), set(r)
    Q, K = map(int, S[N].split())
    sk, k = f(K)
    def f2(n, s):
        while n in D:
            a, n = D[n]
            s += L[a] * q[a in k]
        return s
    for i in range(N+1, N+1+Q):
        x, y = map(int, S[i].split())
        sys.stdout.write(str(f2(x, sk) + f2(y, sk)) + '\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
import sys

def main():
    L = []
    D = {}
    S = [x for x in sys.stdin]
    N = int(S[0])
    for i in range(N-1):
        a, b, c = map(int, S[1+i].split())
        D[b] = (i, a)
        L.append(c)
    def f(n):
        r = []
        while n in D:
            a, b = D[n]
            r.append(a)
            n = b
        return sum(L[i] for i in r), set(r)
    Q, K = map(int, S[N].split())
    sk, k = f(K)
    def f2(n, s):
        while n in D:
            a, b = D[n]
            n = b
            if a not in k:
                s += L[a]
            else:
                s -= L[a]
            
        return s
    for i in range(N+1, N+1+Q):
        x, y = map(int, S[i].split())
        sys.stdout.write(str(f2(x, sk) + f2(y, sk)) + '\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
import sys

def main():
    L = []
    D = {}
    S = [x for x in sys.stdin]
    N = int(S[0])
    for i in range(N-1):
        a, b, c = map(int, S[1+i].split())
        D[b] = (i, a)
        L.append(c)
    def f(n):
        r = []
        while n in D:
            a, b = D[n]
            r.append(a)
            n = b
        return set(r)
    Q, K = map(int, S[N].split())
    k = f(K)
    for i in range(N+1, N+1+Q):
        x, y = map(int, S[i].split())
        sys.stdout.write(str(sum(L[j] for j in f(x) ^ k) + sum(L[j] for j in f(y) ^ k)))
        sys.stdout.write('\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
import sys

def main():
    L = []
    D = {}
    S = [x for x in sys.stdin]
    N = int(S[0])
    for i in range(N-1):
        a, b, c = map(int, S[1+i].split())
        D[b] = (i, a)
        L.append(c)
    def f(n):
        r = []
        while n in D:
            a, b = D[n]
            r.append(a)
            n = b
        return set(r)
    Q, K = map(int, S[N].split())
    k = f(K)
    for i in range(N+1, N+1+Q):
        x, y = map(int, S[i].split())
        sys.stdout.write(str(sum(L[j] for j in f(x) ^ k) + sum(L[j] for j in f(y) ^ k)) + '\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3

def main():
    L = []
    D = {}
    N = int(input())
    for i in range(N-1):
        a, b, c = map(int, input().split())
        D[b] = (i, a)
        L.append(c)
    def f(n):
        r = []
        while n in D:
            a, b = D[n]
            r.append(a)
            n = b
        return set(r)
    Q, K = map(int, input().split())
    k = f(K)
    for i in range(Q):
        x, y = map(int, input().split())
        print(sum(L[j] for j in f(x) ^ k) + sum(L[j] for j in f(y) ^ k))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3

def main():
    L = []
    D = {}
    N = int(input())
    for i in range(N-1):
        a, b, c = map(int, input().split())
        D[b] = (i, a)
        L.append(c)
    m = list(set(range(1, N)) - set(D))[0]
    def f(n):
        r = []
        while n != m:
            a, b = D[n]
            r.append(a)
            n = b
        return set(r)
    
    Q, K = map(int, input().split())
    k = f(K)
    for i in range(Q):
        x, y = map(int, input().split())
        print(sum(L[j] for j in f(x) ^ k) + sum(L[j] for j in f(y) ^ k))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
D = {}
L = []

def f(n):
    r = []
    while n in D:
        a, b = D[n]
        r.append(a)
        n = b
    return set(r)

def d(a, b):
    return sum(L[x] for x in a.symmetric_difference(b))

def main():
    N = int(input())
    for i in range(N-1):
        a, b, c = map(int, input().split())
        D[b] = (i, a)
        L.append(c)
    Q, K = map(int, input().split())
    k = f(K)
    for i in range(Q):
        x, y = map(int, input().split())
        print(d(f(x), k) + d(f(y), k))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
D = {}
L = []

def f(n):
    r = []
    while n in D:
        a, b = D[n]
        r = [a] + r
        n = b
    return r

def d(a, b):
    c = 0
    for i in range(min(len(a), len(b))):
        if a[i] == b[i]:
            c += 1
        else:
            break
    return sum(L[x] for x in a[c:]) + sum(L[x] for x in b[c:])

def main():
    N = int(input())
    for i in range(N-1):
        a, b, c = map(int, input().split())
        D[b] = (i, a)
        L.append(c)
    Q, K = map(int, input().split())
    k = f(K)
    for i in range(Q):
        x, y = map(int, input().split())
        print(d(f(x), k) + d(f(y), k))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
D = {}
L = []

def f(n):
    r = []
    while n in D:
        a, b = D[n]
        r = [a] + r
        n = b
    return r

def d(a, b):
    c = 0
    for i, j in zip(a, b):
        if i == j:
            c += 1
        else:
            break
    return sum(L[x] for x in a[c:]) + sum(L[x] for x in b[c:])

def main():
    N = int(input())
    for i in range(N-1):
        a, b, c = map(int, input().split())
        D[b] = (i, a)
        L.append(c)
    Q, K = map(int, input().split())
    k = f(K)
    s = ''
    for i in range(Q):
        x, y = map(int, input().split())
        s += str(d(f(x), k) + d(f(y), k)) + '\n'
    print(s[:-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3

def f(diu, n):
    r = []
    while n in diu:
        r = [diu[n][0]] + r
        n = diu[n][1]
    return r

def d(p, a, b):
    c = 0
    for i, j in zip(a, b):
        if i == j:
            c += 1
        else:
            break
    return sum(p[x][2] for x in a[c:]) + sum(p[x][2] for x in b[c:])

def main():
    N = int(input())
    P = [tuple(map(int, input().split())) for x in range(N-1)]
    diu = {v[1] : (i, v[0])  for i, v in enumerate(P)}
    Q, K = map(int, input().split())
    k = f(diu, K)
    for i in range(Q):
        x, y = map(int, input().split())
        print(d(P, f(diu, x), k) + d(P, f(diu, y), k))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
g = {i: [] for i in range(1, N+1)}    

l = [0] * (N + 1)

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

stack = [K]
visited = []
while len(stack):
    v = stack.pop()
    visited.append(v)
    for c,ln in g[v]:
        if c in visited:
            continue
        l[c] = l[v] + ln
        stack.append(c)

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

Submission status: Time Limit Exceeded

Solution code:
import sys


# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


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

    d = [0] * (n+1)
    q, k = read_int_list()

    Q = [(k, 0, 0)]
    while Q:
        u, parent, dist = Q.pop(0)
        Q.extend([(v, u, dist+w) for v, w in adj[u] if v != parent])
        d[u] = dist

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


main()

Submission status: Time Limit Exceeded

Solution code:
import sys


# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    n = read_int()
    adj = [[] for u in range(n)]
    for i in range(n - 1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append((b, c))
        adj[b].append((a, c))

    d = [0] * n
    q, k = read_int_list()
    k -= 1

    Q = [(k, -1, 0)]
    while Q:
        u, parent, dist = Q.pop(0)
        Q.extend([(v, u, dist+w) for v, w in adj[u] if v != parent])
        d[u] = dist

    res = [0] * q
    for i in range(q):
        x, y = map(int, input().split())
        res[i] = d[x-1] + d[y-1]
    print(*res, sep='\n')


main()

Submission status: Time Limit Exceeded

Solution code:
import sys


# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    inf = 10 ** 20
    n = read_int()
    adj = [[] for u in range(n)]
    for i in range(n - 1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append((b, c))
        adj[b].append((a, c))

    q, k = read_int_list()
    k -= 1
    d = [inf for u in range(n)]

    d[k] = 0
    Q = [(k, -1)]
    while Q:
        u, parent = Q.pop(0)
        for v, w in adj[u]:
            if v == parent:
                continue
            d[v] = d[u] + w
        Q.extend([(v, u) for v, w in adj[u] if v != parent])

    res = [0] * q
    for i in range(q):
        x, y = map(int, input().split())
        res[i] = d[x-1] + d[y-1]
    print(*res, sep='\n')


main()

Submission status: Time Limit Exceeded

Solution code:
import sys


# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    inf = 10 ** 20
    n = read_int()
    adj = [[] for u in range(n)]
    for i in range(n - 1):
        a, b, c = read_int_list()
        a -= 1
        b -= 1
        adj[a].append((b, c))
        adj[b].append((a, c))

    q, k = read_int_list()
    k -= 1
    d = [inf for u in range(n)]

    d[k] = 0
    Q = [(k, -1)]
    while Q:
        u, parent = Q.pop(0)
        for v, w in adj[u]:
            if v == parent:
                continue
            d[v] = d[u] + w
        Q.extend([(v, u) for v, w in adj[u] if v != parent])

    res = [0] * q
    for i in range(q):
        x, y = read_int_list()
        x -= 1
        y -= 1
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()

Submission status: Time Limit Exceeded

Solution code:
import sys


# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    inf = 10 ** 20
    n = read_int()
    adj = [[] for u in range(n)]
    for i in range(n - 1):
        a, b, c = read_int_list()
        a -= 1
        b -= 1
        adj[a].append((b, c))
        adj[b].append((a, c))

    q, k = read_int_list()
    k -= 1
    state = [0 for u in range(n)]
    d = [inf for u in range(n)]

    state[k] = 1
    d[k] = 0
    Q = [(k, -1)]
    while Q:
        u, parent = Q.pop(0)
        for v, w in adj[u]:
            if v == parent:
                continue
            if state[v] == 0:
                state[v] = 1
                d[v] = d[u] + w
                Q.append((v, u))
                # state[u] = 2

    res = [0] * q
    for i in range(q):
        x, y = read_int_list()
        x -= 1
        y -= 1
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()

Submission status: Time Limit Exceeded

Solution code:
import sys


# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    inf = 10 ** 20
    n = read_int()
    adj = [[] for u in range(n)]
    for i in range(n - 1):
        a, b, c = read_int_list()
        a -= 1
        b -= 1
        adj[a].append((b, c))
        adj[b].append((a, c))

    q, k = read_int_list()
    k -= 1
    state = [0 for u in range(n)]
    d = [inf for u in range(n)]

    state[k] = 1
    d[k] = 0
    Q = [k]
    while Q:
        u = Q.pop(0)
        for v, w in adj[u]:
            if state[v] == 0:
                state[v] = 1
                d[v] = d[u] + w
                Q.append(v)
                # state[u] = 2

    res = [0] * q
    for i in range(q):
        x, y = read_int_list()
        x -= 1
        y -= 1
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()

Submission status: Time Limit Exceeded

Solution code:
import sys

# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    inf = 10 ** 20
    n = read_int()
    weight = {}
    adj = [[] for u in range(n)]
    for i in range(n - 1):
        a, b, c = read_int_list()
        a -= 1
        b -= 1
        adj[a].append(b)
        adj[b].append(a)
        weight[(a, b)] = c
        weight[(b, a)] = c

    q, k = read_int_list()
    k -= 1
    state = [0 for u in range(n)]
    d = [inf for u in range(n)]

    state[k] = 1
    d[k] = 0
    Q = [k]
    while Q:
        u = Q.pop(0)
        for v in adj[u]:
            if state[v] == 0:
                state[v] = 1
                d[v] = d[u] + weight[(u, v)]
                Q.append(v)
        # state[u] = 2

    res = [0] * q
    for i in range(q):
        x, y = read_int_list()
        x -= 1
        y -= 1
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()

Submission status: Time Limit Exceeded

Solution code:
import sys

# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    inf = 10 ** 20
    n = read_int()
    weight = {}
    adj = {u: [] for u in range(1, n + 1)}
    for i in range(n - 1):
        a, b, c = read_int_list()
        adj[a].append(b)
        adj[b].append(a)
        weight[(a, b)] = c
        weight[(b, a)] = c

    q, k = read_int_list()
    state = {u: 0 for u in range(1, n + 1)}
    d = {u: inf for u in range(1, n + 1)}

    state[k] = 1
    d[k] = 0
    Q = [k]
    while Q:
        u = Q.pop(0)
        for v in adj[u]:
            if state[v] == 0:
                state[v] = 1
                d[v] = d[u] + weight[(u, v)]
                Q.append(v)
        # state[u] = 2

    res = [0] * q
    for i in range(q):
        x, y = read_int_list()
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()

Submission status: Time Limit Exceeded

Solution code:
import sys

# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    inf = 10 ** 20
    n = read_int()
    weight = {}
    adj = {u: [] for u in range(1, n + 1)}
    for i in range(n - 1):
        a, b, c = read_int_list()
        adj[a].append(b)
        adj[b].append(a)
        weight[(a, b)] = c
        weight[(b, a)] = c

    q, k = read_int_list()
    state = {u: 0 for u in range(1, n + 1)}
    d = {u: inf for u in range(1, n + 1)}

    state[k] = 1
    d[k] = 0
    Q = [k]
    while Q:
        u = Q.pop(0)
        for v in adj[u]:
            if state[v] == 0:
                state[v] = 1
                d[v] = d[u] + weight[(u, v)]
                Q.append(v)
        state[u] = 2

    res = [0] * q
    for i in range(q):
        x, y = read_int_list()
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()

Submission status: Time Limit Exceeded

Solution code:
import sys

# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    inf = 10 ** 20
    n = read_int()
    weight = {}
    adj = {u: [] for u in range(1, n + 1)}
    for i in range(n - 1):
        a, b, c = read_int_list()
        adj[a].append(b)
        adj[b].append(a)
        weight[(a, b)] = c
        weight[(b, a)] = c

    q, k = read_int_list()
    state = {u: 0 for u in range(1, n + 1)}
    d = {u: inf for u in range(1, n + 1)}

    state[k] = 1
    d[k] = 0
    Q = [k]
    while Q:
        u = Q.pop(0)
        for v in adj[u]:
            if state[v] == 0:
                state[v] = 1
                d[v] = d[u] + weight[(u, v)]
                Q.append(v)
        state[u] = 2

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


main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

n = raw_input()
n = int(n)

tree = []
for i in range(n):
    tree.append([])

for i in range(n-1):
    abc = raw_input()
    abc = abc.split()
    abc = map(int, abc)
    tree[abc[0]-1].append([abc[1]-1,abc[2]])
    tree[abc[1]-1].append([abc[0]-1,abc[2]])


qk = raw_input()
qk = qk.split()
q,k = map(int,qk)

question = []
for i in range(q):
    xy = raw_input()
    xy = xy.split()
    xy = map(int,xy)
    question.append(xy)

distance = []
for i in range(n):
    distance.append(-1)

distance[k-1] = 0

while 1:
    status = 0
    for i in range(n):
        if distance[i] == -1:
            status = 1
        else:
            for j in tree[i]:
                if distance[j[0]] == -1:
                    distance[j[0]] = distance[i] + j[1]
    if status == 0:
        break

for line in question:
    print distance[line[0]-1] + distance[line[1]-1]

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
g = {i: []for i in range(1, N+1)}    

cache = {}
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 v in range(1,N+1):
    cache[v] = dfs(g,v,K)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
g = {}
for i in range(1, N+1):
    g[i] = []

cache = {}
def dfs(g,start,end):
    if cache.get((start,end),None) != None or cache.get((end,start),None) != None:
        return cache[(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:
                cache[(start,end)] = length + l
                cache[(end,start)] = length + l
                return cache[(start,end)]
            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:
N = int(input())
g = {}
for i in range(1, N+1):
    g[i] = []

cache = {}
def dfs(g,start,end):
    if cache.get((start,end),None) != None:
        #print(start,end)
        return cache[(start,end)]
        pass
    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:
                cache[(start,end)] = length + l
                return cache[(start,end)]
            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))
    if (a,c) not in g[b]:
        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))