Problem: 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.

Submission attempts (in order):
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
sys.setrecursionlimit(10**6)
INF = float("inf")


class Graph(object):
    

    def __init__(self, N):
        self.N = N
        self.edges = defaultdict(list)
        pass

    def add_edges(self, from_, to_, weight):
        
        self.edges[from_].append([to_, weight])
        self.edges[to_].append([from_, weight])
        pass


def solve(N: int,
          a: "List[int]",
          b: "List[int]",
          c: "List[int]",
          Q: int,
          K: int,
          x: "List[int]",
          y: "List[int]"):

    g = Graph(N)
    for aa, bb, cc in zip(a, b, c):
        g.add_edges(aa-1, bb-1, cc)

    N = g.N

    depth = [INF]*N

    def dfs(curr, pre, dep):         
        depth[curr] = dep
        for n, w in g.edges[curr]:
            if n != pre:
                dfs(n, curr, dep+w)
    dfs(K, None, 0)

    for i in range(Q):
        print(depth[x[i]-1]+depth[y[i]-1])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]"
    b = [int()] * (N-1)  # type: "List[int]"
    c = [int()] * (N-1)  # type: "List[int]"
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (Q)  # type: "List[int]"
    y = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, a, b, c, Q, K, x, y)


if __name__ == '__main__':
    main()


#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
INF = float("inf")


class Graph(object):
    

    def __init__(self, N):
        self.N = N
        self.edges = defaultdict(list)
        pass

    def add_edges(self, from_, to_, weight):
        
        self.edges[from_].append([to_, weight])
        self.edges[to_].append([from_, weight])
        pass


def solve(N: int,
          a: "List[int]",
          b: "List[int]",
          c: "List[int]",
          Q: int,
          K: int,
          x: "List[int]",
          y: "List[int]"):

    g = Graph(N)
    for aa, bb, cc in zip(a, b, c):
        g.add_edges(*[aa-1, bb-1, cc])

    N = g.N

    par = [INF]*N
    depth = [INF]*N

    def dfs(curr, pre, dep):         
        par[curr] = pre
        depth[curr] = dep
        for n, w in g.edges[curr]:
            if n != pre:
                dfs(n, curr, dep+w)
    dfs(K, None, 0)

    
    #     print(depth[x[i]-1]+depth[y[i]-1])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]"
    b = [int()] * (N-1)  # type: "List[int]"
    c = [int()] * (N-1)  # type: "List[int]"
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (Q)  # type: "List[int]"
    y = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, a, b, c, Q, K, x, y)


if __name__ == '__main__':
    main()


#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
from collections import deque
sys.setrecursionlimit(10**6)
INF = float("inf")


class Graph(object):
    

    def __init__(self, N):
        self.N = N
        self.edges = defaultdict(list)
        pass

    def add_edges(self, from_, to_, weight):
        
        self.edges[from_].append([to_, weight])
        self.edges[to_].append([from_, weight])
        pass


def LCA_constract(g: Graph, root=0):
    
    N = g.N
    LN = int(math.log2(g.N))

    ###
    
    ###
    par = [INF]*N
    depth = [INF]*N

    que = deque()
    que.append([root, 0, None])
    while len(que) > 0:
        curr, dep, pre = que.popleft()
        par[curr] = pre
        depth[curr] = dep
        for n, w in g.edges[curr]:
            if n != pre:
                que.append([n, dep+w, curr])

    ###
    
    ###

    anc = [par]

    for i in range(LN):
        buf = [None]*N
        for j in range(N):
            if anc[i][j] == None:
                continue
            buf[j] = anc[i][anc[i][j]]
        anc.append(buf)
    return anc, depth


def LCA_query(anc, depth, u: int, v: int):
    ###
    
    ###
    N = len(depth)
    LN = int(math.log2(g.N))

    dd = depth[v] - depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd

    
    for k in range(LN):
        if dd & 1:
            v = anc[k][v]
        dd >>= 1

    
    if u == v:
        return u

    for k in range(LN-1, -1, -1):
        pu = anc[k][u]
        pv = anc[k][v]
        if pu != pv:
            u = pu
            v = pv

    
    return anc[0][u]


def solve(N: int,
          a: "List[int]",
          b: "List[int]",
          c: "List[int]",
          Q: int,
          K: int,
          x: "List[int]",
          y: "List[int]"):

    g = Graph(N)
    for aa, bb, cc in zip(a, b, c):
        g.add_edges(*[aa-1, bb-1, cc])

    anc, depth = LCA_constract(g, root=K-1)

    for i in range(Q):
        print(depth[x[i]-1]+depth[y[i]-1])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]"
    b = [int()] * (N-1)  # type: "List[int]"
    c = [int()] * (N-1)  # type: "List[int]"
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (Q)  # type: "List[int]"
    y = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, a, b, c, Q, K, x, y)


if __name__ == '__main__':
    main()


Verdicts: Runtime Error

Runtime Error

Accepted