Problem:


Score : 600 points

Problem Statement

There is a tree with N vertices numbered 1 to N.
The i-th edge in this tree connects Vertex a_i and Vertex b_i, and the color and length of that edge are c_i and d_i, respectively.
Here the color of each edge is represented by an integer between 1 and N-1 (inclusive). The same integer corresponds to the same color, and different integers correspond to different colors.

Answer the following Q queries:

Query j (1 \leq j \leq Q): assuming that the length of every edge whose color is x_j is changed to y_j, find the distance between Vertex u_j and Vertex v_j. (The changes of the lengths of edges do not affect the subsequent queries.)

Constraints

2 \leq N \leq 10^5

1 \leq Q \leq 10^5

1 \leq a_i, b_i \leq N

1 \leq c_i \leq N-1

1 \leq d_i \leq 10^4

1 \leq x_j \leq N-1

1 \leq y_j \leq 10^4

1 \leq u_j < v_j \leq N

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1 c_1 d_1
:
a_{N-1} b_{N-1} c_{N-1} d_{N-1}
x_1 y_1 u_1 v_1
:
x_Q y_Q u_Q v_Q

Output

Print Q lines. The j-th line (1 \leq j \leq Q) should contain the answer to Query j.

Sample Input 1

5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4

Sample Output 1

130
200
60

The graph in this input is as follows:

Here the edges of Color 1 are shown as solid red lines, the edge of Color 2 is shown as a bold green line, and the edge of Color 4 is shown as a blue dashed line.

Query 1: Assuming that the length of every edge whose color is 1 is changed to 100, the distance between Vertex 1 and Vertex 4 is 100 + 30 = 130.

Query 2: Assuming that the length of every edge whose color is 1 is changed to 100, the distance between Vertex 1 and Vertex 5 is 100 + 100 = 200.

Query 3: Assuming that the length of every edge whose color is 3 is changed to 1000 (there is no such edge), the distance between Vertex 3 and Vertex 4 is 20 + 10 + 30 = 60. Note that the edges of Color 1 now have their original lengths.



Sample input:
5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4


Sample output:
130
200
60

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
class LCA:
    def __init__(self,V,edges,root=0):
        self.edges=edges
        self.maxLog=18
        self.parent=[[-1]*V for _ in range(self.maxLog+1)]
        self.depth=[0]*V
        self.__dfs(-1,root,0)
        for i in range(self.maxLog):
            for j in range(V):
                if self.parent[i][j]!=-1:
                    self.parent[i+1][j]=self.parent[i][self.parent[i][j]]
    def __dfs(self,par,cur,dep):
        self.depth[cur]=dep
        self.parent[0][cur]=par
        for v in self.edges[cur]:
            if v==par:
                continue
            else:
                self.__dfs(cur,v,dep+1)
    def lca(self,a,b):
        if self.depth[a]>self.depth[b]:
            a,b=b,a
        for i in range(self.maxLog):
            if (self.depth[b]-self.depth[a])&(1<<i):
                b=self.parent[i][b]
        if a==b:
            return b
        for i in reversed(range(self.maxLog-1)):
            if self.parent[i][a]!=self.parent[i][b]:
                a=self.parent[i][a]
                b=self.parent[i][b]
        return self.parent[0][a]

from collections import deque
def Eulertour(Edges,n,root=0):
    Euler=[]
    Depth=[-1]*n
    Depth[root]=0
    que=deque([root])
    que2=deque()
    Visited=[False]*n
    while que:
        fr=que.pop()
        Euler.append((Depth[fr],fr))
        if Visited[fr]:
            continue
        for to in Edges[fr]:
            if Visited[to]:
                que.append(to)
            else:
                Depth[to]=Depth[fr]+1
                que2.append(to)
        que.extend(que2)
        que2=deque()
        Visited[fr]=True
    return Euler

n,q=map(int,input().split())
Edgedict=[dict() for _ in range(n)]
for _ in range(n-1):
    a,b,c,d=map(int,input().split())
    a-=1; b-=1
    Edgedict[a][b]=(c,d)
    Edgedict[b][a]=(c,d)
Queries=[tuple(map(int,input().split())) for _ in range(q)]
lca=LCA(n,Edgedict)
Euler=Eulertour(Edgedict,n)
Q=[[] for _ in range(n)]
for i,(x,y,u,v) in enumerate(Queries):
    u-=1; v-=1
    Q[u].append([i,x,y,True])
    Q[v].append([i,x,y,True])
    Q[lca.lca(u,v)].append([i,x,y,False])
Ans=[0]*q
dist=0
C_len=[0]*n
C_cnt=[0]*n
for i in range(1,len(Euler)):
    idx=Euler[i][1]
    c,l=Edgedict[Euler[i-1][1]][idx]
    if Euler[i-1][0]<Euler[i][0]:
        dist+=l
        C_len[c]+=l
        C_cnt[c]+=1
        for q_idx,x,y,flag in Q[idx]:
            if flag:
                Ans[q_idx]+=dist+C_cnt[x]*y-C_len[x]
            else:
                Ans[q_idx]-=(dist+C_cnt[x]*y-C_len[x])*2
    else:
        dist-=l
        C_len[c]-=l
        C_cnt[c]-=1
print(*Ans,sep='\n')

Submission status: Runtime Error

Solution code:
import sys

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

depth = [0] * (N+1)
U = 17
ancestor = [[0] * (U+1) for _ in range(N+1)]

q = [(1, 0, 0)]
while q:
        qq = []
        for x, d, parent in q:
                depth[x] = d
                ax = ancestor[x]
                ax[0] = parent
                for i in range(d.bit_length()-1):
                        ax[i+1] = ancestor[ax[i]][i]

                for y, _, _ in edge[x]:
                        if y == parent:
                                continue
                        qq.append((y, d+1, x))
        q = qq

def lca(x, y):
        dx = depth[x]
        dy = depth[y]
        if dx > dy:
                x, y = y, x
                dx, dy = dy, dx
        diff = dy - dx
        while diff:
                step = diff & (-diff)
                y = ancestor[y][step.bit_length()-1]
                diff -= step
        while x!=y:
                j = 0
                while ancestor[x][j] != ancestor[y][j]:
                        j += 1
                if j==0:
                        return ancestor[x][0]
                x = ancestor[x][j-1]
                y = ancestor[y][j-1]
        return x

task = [[] for _ in range(N+1)]
for i in range(Q):
        x, y, u, v = map(int, input().split())
        task[u].append((i, x, y, 1))
        task[v].append((i, x, y, 1))
        task[lca(u, v)].append((i, x, y, -2))

answer = [0] * Q

def dfs(x=1, sums=[0]*(N+1), nums=[0]*(N+1), total=0, parent=0):
        for i, c, d, coef in task[x]:
                answer[i] += coef * (total - sums[c] + nums[c]*d)
        for y, c, d in edge[x]:
                if y == parent:
                        continue
                sums[c] += d
                nums[c] += 1
                total += d
                dfs(y, sums, nums, total, x)
                sums[c] -= d
                nums[c] -= d
                total -= d
        return

dfs()

print('\n'.join(map(str, answer)))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import math

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

depth = [0] * (N+1)
dist_sum = [0] * (N+1)
parent = list(range(N+1))

#dfs
stack = []
stack.append((1, -1, 0, 0))
while stack:
        now, prev, dep, dist = stack.pop()
        depth[now] = dep
        parent[now] = prev
        dist_sum[now] = dist
        for e, c, d in edge[now]:
                if e == prev:
                        continue
                else:
                        stack.append((e, now, dep+1, dist+d))

doubling = [[1] * N for i in range(N+1)]
for i in range(N):
        for j in range(1, N+1):
                doubling[j][i] = parent[j]
        parent = [parent[parent[i]] for i in range(N+1)]

def lca(a, b):
        x, y = depth[a], depth[b]
        if x > y:
                x, y = y, x
                a, b = b, a        
        diff = y-x
        if diff > 0:
                for i in reversed(range(N)):
                        if diff > 2**i:
                                b = doubling[b][i]
                                diff -= 2**i
                b = doubling[b][0]
        if a == b:
                return a
        
        for i in reversed(range(int(math.log2(x)) + 2)):
                if doubling[a][i] != doubling[b][i]:
                        a, b = doubling[a][i], doubling[b][i]
        return doubling[a][0]

task = defaultdict(list)
for i in range(Q):
        x, y, u, v = map(int, input().split())
        task[u].append((i, x, y, 1))
        task[v].append((i, x, y, 1))
        task[lca(u, v)].append((i, x, y, -2))

stack = []
ans = [0] * Q
color_num = [0] * N
color_dist = [0] * N
stack.append((1, -1, color_num, color_dist))
while stack:
        now, prev, color_num, color_dist = stack.pop()
        if len(task[now]) > 0:
                for i, x, y, coeff in task[now]:
                        ans[i] += coeff * (dist_sum[now] - color_dist[x] + color_num[x] * y)
                        
        for e, c, d in edge[now]:
                if e == prev:
                        continue
                color_num[c] += 1
                color_dist[c] += d
                stack.append((e, now, color_num[:], color_dist[:]))
                color_num[c] -= 1
                color_dist[c] -= d

print('\n'.join([str(ans[i]) for i in range(Q)]))

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
from math import *
import sys
sys.setrecursionlimit(10**8)

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

query = []
for i in range(Q):
    x, y, u, v = map(int, input().split())
    query.append((x, y, u, v))

def dfs(prev, cur, cur_color_num, cur_color_total, cur_depth):
    parent[cur] = prev
    depth[cur] = cur_depth
    color_num[cur] = cur_color_num[:]
    color_total[cur] = cur_color_total[:]
    for e, c, d in edge[cur]:
        if e != prev:
            temp_num = cur_color_num[:]
            temp_total = cur_color_total[:]
            temp_num[c] += 1
            temp_total[c] += d
            dist[e] = dist[cur] + d
            dfs(cur, e, temp_num, temp_total, cur_depth+1)
    return

color_num =[[0] * N for i in range(N+1)]
color_total = [[0] * N for i in range(N+1)]
depth = [0] * (N+1)
dist = [0] * (N+1)
parent = list(range(N+1))
cur_color_num = [0] * N
cur_color_total = [0] * N
dfs(1, 1, cur_color_num, cur_color_total, 0)

doubling = [parent]
k = int(log2(N)) + 1
for i in range(k):
    parent = [parent[parent[i]] for i in range(N+1)]
    doubling.append(parent[:])

for i in range(Q):
    x, y, u, v = query[i]
    cur_u = u
    cur_v = v

    diff = depth[u] - depth[v]
    if diff > 0:
        for j in range(k):
            ind = k-j-1
            if 2**ind <= diff:
                cur_u = doubling[ind][cur_u]
                diff -= 2**ind
    else:
        diff = -diff
        for j in range(k):
            ind = k-j-1
            if 2**ind <= diff:
                cur_v = doubling[ind][cur_v]
                diff -= 2**ind

    for j in range(k):
        ind = k-j-1
        if doubling[ind][cur_u] != doubling[ind][cur_v]:
            cur_u = doubling[ind][cur_u]
            cur_v = doubling[ind][cur_v]

    lca = doubling[0][cur_u]
    dist_lca = dist[lca] - color_total[lca][x] + color_num[lca][x] * y
    dist_u = dist[u] - color_total[u][x] + color_num[u][x] * y
    dist_v = dist[v] - color_total[v][x] + color_num[v][x] * y
    #print(str(dist_u) + ' ' + str(dist_v) + ' '  +  str(dist_lca))
    #print(str(dist[v]) + ' ' + str(color_total[v][x]) + ' '  +  str(color_num[v][x]))
    print(dist_u + dist_v - dist_lca)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
from math import *

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

query = []
for i in range(Q):
    x, y, u, v = map(int, input().split())
    query.append((x, y, u, v))

def dfs(prev, cur, cur_color_num, cur_color_total, cur_depth):
    parent[cur] = prev
    depth[cur] = cur_depth
    color_num[cur] = cur_color_num
    color_total[cur] = cur_color_total
    for e, c, d in edge[cur]:
        if e != prev:
            temp_num = cur_color_num[:]
            temp_total = cur_color_total[:]
            temp_num[c] += 1
            temp_total[c] += d
            dist[e] = dist[cur] + d
            dfs(cur, e, temp_num, temp_total, cur_depth+1)
    return

color_num =[[0] * N for i in range(N+1)]
color_total = [[0] * N for i in range(N+1)]
depth = [0] * (N+1)
dist = [0] * (N+1)
parent = list(range(N+1))
cur_color_num = [0] * N
cur_color_total = [0] * N
dfs(1, 1, cur_color_num, cur_color_total, 0)

doubling = [parent]
k = int(log2(N)) + 1
for i in range(k):
    parent = [parent[parent[i]] for i in range(N+1)]
    doubling.append(parent)

for i in range(Q):
    x, y, u, v = query[i]
    cur_u = u
    cur_v = v

    diff = depth[u] - depth[v]
    if diff > 0:
        for j in range(k):
            ind = k-j-1
            if 2**ind <= diff:
                cur_u = doubling[ind][cur_u]
                diff -= 2**ind
    else:
        diff = -diff
        for j in range(k):
            ind = k-j-1
            if 2**ind <= diff:
                cur_v = doubling[ind][cur_v]
                diff -= 2**ind

    for j in range(k):
        ind = k-j-1
        if doubling[ind][cur_u] != doubling[ind][cur_v]:
            cur_u = doubling[ind][cur_u]
            cur_v = doubling[ind][cur_v]

    lca = doubling[0][cur_u]
    dist_lca = dist[lca] - color_total[lca][x] + color_num[lca][x] * y
    dist_u = dist[u] - color_total[u][x] + color_num[u][x] * y
    dist_v = dist[v] - color_total[v][x] + color_num[v][x] * y
    #print(str(dist_u) + ' ' + str(dist_v) + ' '  +  str(dist_lca))
    #print(str(dist[v]) + ' ' + str(color_total[v][x]) + ' '  +  str(color_num[v][x]))
    print(dist_u + dist_v - dist_lca)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

    def __len__(self):
        return len(self._vertice)

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))

class Graph(DGraph):
    def __init__(self, n, edges):
        nd_edges = edges + [(d, s, c) for s, d, c in edges]
        super().__init__(n, nd_edges)

    def transpose(self):
        return self

def dfs(g, src):
    visited = [False] * len(g)
    stack = [(src, (0, -1, {}))]
    while stack:
        n, (c, p, acc) = stack.pop()
        if visited[n]:
            continue
        visited[n] = True

        for _, d, (dd, cc) in g.edges(n):
            _acc = {**acc}
            if cc not in _acc:
                _acc[cc] = (0, 0)
            _acc[cc] = (_acc[cc][0] + 1, _acc[cc][1] + dd)
            stack.append((d, (c + 1, n, _acc)))
        yield n, c, p, acc


def solve(N: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]", x: "List[int]", y: "List[int]", u: "List[int]", v: "List[int]"):
    es = []
    for _a, _b, _c, _d in zip(a, b, c, d):
        es.append((_a - 1, _b - 1, (_d, _c)))

    h = int(ceil(log2(N)))
    g = Graph(N, es)
    ds = [-1] * N
    ps = [[-1] * h for _ in range(N)]
    accs = [{}] * N
    for i, d, p, acc in dfs(g, 0):
        ds[i] = d
        ps[i][0] = p
        accs[i] = acc

    for i in range(N):
        for j in range(h - 1):
            ps[i][j + 1] = ps[ps[i][j]][j]


    ret = []
    for _x, _y, _u, _v in zip(x, y, u, v):
        uu = _u - 1
        vv = _v - 1
        while ds[uu] < ds[vv]:
            vv = ps[vv][0]
        while ds[uu] < ds[vv]:
            uu = ps[uu][0]
        if uu == vv:
            lca = uu
        else:
            for i in range(h-1, 0, -1):
                if ps[uu][i] != ps[vv][i]:
                    uu = ps[uu][i]
                    vv = ps[vv][i]
            uu = ps[uu][0]
            vv = ps[vv][0]
            lca = uu

        du = sum([ddd for _, ddd in accs[_u - 1].values()])
        if _x in accs[_u - 1]:
            du += _y * accs[_u - 1][_x][0] - accs[_u - 1][_x][1]
        dv = sum([ddd for _, ddd in accs[_v - 1].values()])
        if _x in accs[_v - 1]:
            dv += _y * accs[_v - 1][_x][0] - accs[_v - 1][_x][1]
        dlca = sum([ddd for _, ddd in accs[lca].values()])
        if _x in accs[lca]:
            dv += _y * accs[lca][_x][0] - accs[lca][_x][1]
        dist = du + dv - 2 * dlca
        ret.append(dist)
    return ret


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
    Q = 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]" 
    d = [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))
        d[i] = int(next(tokens))
    x = [int()] * (Q)  # type: "List[int]" 
    y = [int()] * (Q)  # type: "List[int]" 
    u = [int()] * (Q)  # type: "List[int]" 
    v = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    result = solve(N, Q, a, b, c, d, x, y, u, v)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class Node:
    
    def __init__(self, v):
        self.value = v
        self.parent = None
        self.depth = None


def root(node):
    w = node
    r = []
    while w.parent is not None:
        r.append(w.parent)
        w = w.parent
    return r

N, Q = list(map(int, input().split()))
color, distance = {}, {}
nodes = {v: Node(v) for v in range(1, N + 1)}
links = {i: set() for i in range(1, N + 1)}
for _ in range(N - 1):
    a, b, c, d = list(map(int, input().split()))
    if a > b:
        a, b = b, a
    if c in color:
        color[c].add((a, b))
    else:
        color[c] = {(a, b)}
    distance[(a, b)] = d
    links[a].add(nodes[b])
    links[b].add(nodes[a])
q = [list(map(int, input().split())) for _ in range(Q)]

# nodeにリンクを張る。baseは1
parents = [nodes[1]]
nodes[1].depth = 1
for i in range(2, N + 1):
    next_parents = set()
    for parent in parents:
        children = links[parent.value]
        next_parents |= children
        for child in children:
            child.parent = parent
            child.depth = i
            links[child.value].remove(parent)
    if len(next_parents) == 0:
        break
    parents = next_parents

for x, y, u, v in q:
    if (u, v) in distance:
        print(link_distance(x, y, u, v))
        continue
    node1, node2 = nodes[u], nodes[v]
    if node1.depth > node2.depth:
        node1, node2 = node2, node1
    n = node2.depth - node1.depth
    root = [node2]
    w = node2
    for _ in range(n):
        root.append(w.parent)
        w = w.parent
    if node1 not in root:
        root_ = [node1]
        w1, w2 = root_[-1].parent, root[-1].parent
        while w1 is not w2:
            root_.append(w1)
            root.append(w2)
            w1, w2 = root_[-1].parent, root[-1].parent
        root.append(w2)
        root.extend(reversed(root_))
    d = 0
    w = root[0]
    for r in root[1:]:
        i, j = w.value, r.value
        if i > j:
            i, j = j, i
        if x in color and (i, j) in color[x]:
            d += y
        else:
            d += distance[(i, j)]
        w = r
    print(d)

Submission status: Runtime Error

Solution code:
class Node:
    
    def __init__(self, v):
        self.value = v
        self.parent = None


def root(node):
    w = node
    r = set()
    while w.parent is not None:
        r.add(w.parent)
        w = w.parent
    return r

N, Q = list(map(int, input().split()))
color, distance = {}, {}
nodes = {v: Node(v) for v in range(1, N + 1)}
links = {i: set() for i in range(1, N + 1)}
for _ in range(N - 1):
    a, b, c, d = list(map(int, input().split()))
    if a > b:
        a, b = b, a
    if c in color:
        color[c].add((a, b))
    else:
        color[c] = {(a, b)}
    distance[(a, b)] = d
    links[a].add(nodes[b])
    links[b].add(nodes[a])
q = [list(map(int, input().split())) for _ in range(Q)]

def link_distance(x, y, i, j):
    if i > j:
        i, j = j, i
    if x in color and (i, j) in color[x]:
        return y
    else:
        return distance[(i, j)]

# nodeにリンクを張る。baseは1
parents = [nodes[1]]
while True:
    next_parents = set()
    for parent in parents:
        print(parent.value)
        children = links[parent.value]
        next_parents |= children
        for child in children:
            child.parent = parent
            links[child.value].remove(parent)
    if len(next_parents) == 0:
        break
    parents = next_parents

for x, y, u, v in q:
    if (u, v) in distance:
        print(link_distance(x, y, u, v))
        continue
    node1, node2 = nodes[u], nodes[v]
    root1, root2 = root(node1), root(node2)
    root1, root2 = root1 - root2, root2 - root1
    d = 0
    w = node1
    for r in root1:
        d += link_distance(x, y, w.value, r.value)
        w = r
    if w in root2:
        root2.remove(w)
    else:
        r = w.parent
        d += link_distance(x, y, w.value, r.value)
        w = r
    for r in root2:
        d += link_distance(x, y, w.value, r.value)
        w = r
    if w is not node2:
        d += link_distance(x, y, node2.value, node2.parent.value)
    print(d)

Submission status: Runtime Error

Solution code:
class Node:
    
    def __init__(self, v):
        self.value = v
        self.depth = None
        self.parent = None


def root(node):
    w = node
    r = set()
    while w.parent is not None:
        r.add(w.parent)
        w = w.parent
    return r

N, Q = list(map(int, input().split()))
color, distance = {}, {}
nodes = {v: Node(v) for v in range(1, N + 1)}
links = {i: set() for i in range(1, N + 1)}
for _ in range(N - 1):
    a, b, c, d = list(map(int, input().split()))
    if a > b:
        a, b = b, a
    if c in color:
        color[c].add((a, b))
    else:
        color[c] = {(a, b)}
    distance[(a, b)] = d
    links[a].add(nodes[b])
    links[b].add(nodes[a])
q = [list(map(int, input().split())) for _ in range(Q)]

def link_distance(x, y, i, j):
    if i == j:
        return 0
    if i > j:
        i, j = j, i
    if x in color and (i, j) in color[x]:
        return y
    else:
        return distance[(i, j)]

# nodeにリンクを張る。baseは1
parents = [nodes[1]]
while True:
    next_parents = set()
    for parent in parents:
        children = links[parent.value]
        next_parents |= children
        for child in children:
            child.parent = parent
            links[child.value].remove(parent)
    if len(next_parents) == 0:
        break
    parents = next_parents

for x, y, u, v in q:
    node1, node2 = nodes[u], nodes[v]
    if (u, v) in distance:
        print(link_distance(x, y, u, v))
        continue
    root1, root2 = root(node1), root(node2)
    root1, root2 = root1 - root2, root2 - root1
    d = 0
    w = node1
    for r in root1:
        d += link_distance(x, y, w.value, r.value)
        w = r
    if node1 in root2:
        root2.remove(node1)
    else:
        r = w.parent
        d += link_distance(x, y, w.value, r.value)
        w = r
    for r in root2:
        d += link_distance(x, y, w.value, r.value)
        w = r
    if w is not node2:
        d += link_distance(x, y, node2.value, node2.parent.value)
    print(d)

Submission status: Runtime Error

Solution code:
class Node:
    
    def __init__(self, v):
        self.value = v
        self.depth = None
        self.parent = None


def root(node):
    w = node
    r = set()
    while w.parent is not None:
        r.add(w.parent)
        w = w.parent
    return r

N, Q = list(map(int, input().split()))
color, distance = {}, {}
nodes = {v: Node(v) for v in range(1, N + 1)}
links = {i: set() for i in range(1, N + 1)}
for _ in range(N - 1):
    a, b, c, d = list(map(int, input().split()))
    if a > b:
        a, b = b, a
    if c in color:
        color[c].add((a, b))
    else:
        color[c] = {(a, b)}
    distance[(a, b)] = d
    links[a].add(nodes[b])
    links[b].add(nodes[a])
q = [list(map(int, input().split())) for _ in range(Q)]

def link_distance(x, y, i, j):
    if i > j:
        i, j = j, i
    if x in color and (i, j) in color[x]:
        return y
    else:
        return distance[(i, j)]

# nodeにリンクを張る。baseは1
parents = [nodes[1]]
while True:
    next_parents = set()
    for parent in parents:
        children = links[parent.value]
        next_parents |= children
        for child in children:
            child.parent = parent
            links[child.value].remove(parent)
    if len(next_parents) == 0:
        break
    parents = next_parents

for x, y, u, v in q:
    node1, node2 = nodes[u], nodes[v]
    if (u, v) in distance:
        print(link_distance(x, y, u, v))
        continue
    root1, root2 = root(node1), root(node2)
    root1, root2 = root1 - root2, root2 - root1
    d = 0
    w = node1
    for r in root1:
        d += link_distance(x, y, w.value, r.value)
        w = r
    if node1 in root2:
        root2.remove(node1)
    else:
        r = w.parent
        d += link_distance(x, y, w.value, r.value)
        w = r
    for r in root2:
        d += link_distance(x, y, w.value, r.value)
        w = r
    if w is not node2:
        d += link_distance(x, y, node2.value, node2.parent.value)
    print(d)

Submission status: Runtime Error

Solution code:
class Node:
    
    def __init__(self, v):
        self.value = v
        self.depth = None
        self.parent = None


def root(node):
    w = node
    r = set()
    while w.parent is not None:
        r.add(w.parent)
        w = w.parent
    return r

N, Q = list(map(int, input().split()))
color, distance = {}, {}
nodes = {v: Node(v) for v in range(1, N + 1)}
links = {i: set() for i in range(1, N + 1)}
for _ in range(N - 1):
    a, b, c, d = list(map(int, input().split()))
    if a > b:
        a, b = b, a
    if c in color:
        color[c].add((a, b))
    else:
        color[c] = {(a, b)}
    distance[(a, b)] = d
    links[a].add(nodes[b])
    links[b].add(nodes[a])
q = [list(map(int, input().split())) for _ in range(Q)]

def link_distance(x, y, i, j):
    if i > j:
        i, j = j, i
    if x in color and (i, j) in color[x]:
        return y
    else:
        return distance[(i, j)]

# nodeにリンクを張る。baseは1
parents = [nodes[1]]
while True:
    next_parents = set()
    for parent in parents:
        children = links[parent.value]
        next_parents |= children
        for child in children:
            child.parent = parent
            links[child.value].remove(parent)
    if len(next_parents) == 0:
        break
    parents = next_parents

for x, y, u, v in q:
    node1, node2 = nodes[u], nodes[v]
    if (u, v) in distance:
        print(link_distance(x, y, u, v))
        continue
    root1, root2 = root(node1), root(node2)
    root1, root2 = root1 - root2, root2 - root1
    d = 0
    w = node1
    for r in root1:
        d += link_distance(x, y, w.value, r.value)
        w = r
    if node1 in root2:
        root2.remove(node1)
    else:
        r = w.parent
        d += link_distance(x, y, w.value, r.value)
        w = r
    for r in root2:
        d += link_distance(x, y, w.value, r.value)
        w = r
    d += link_distance(x, y, node2.value, node2.parent.value)
    print(d)