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: Time Limit Exceeded

Solution code:
import math

N, Q = map(int, input().split())
edge = [[] for i in range(N+1)]
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))

U = 17
doubling = [[1] * U for i in 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
        dx = doubling[now]
        dx[0] = prev
        for i in range(dep.bit_length()-1):
                dx[i+1] = doubling[dx[i]][i]
        
        for e, c, d in edge[now]:
                if e == prev:
                        continue
                else:
                        stack.append((e, now, dep+1, dist+d))

def lca(a, b):
        x, y = depth[a], depth[b]
        if x > y:
                x, y = y, x
                a, b = b, a        
        diff = y-x
        while diff:
                step = diff & (-diff)
                b = doubling[b][step.bit_length()-1]
                diff -= step

        while a != b:
                j = 0
                while doubling[a][j] != doubling[b][j]:
                        j += 1
                if j==0:
                        return doubling[a][0]
                x = doubling[a][j-1]
                y = doubling[b][j-1]

        return a

task = [[] for i 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))

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: Time Limit Exceeded

Solution code:
import math

N, Q = map(int, input().split())
edge = [[] for i in range(N+1)]
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))

U = 17
doubling = [[1] * U for i in range(N+1)]
for i in range(U):
        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
        while diff:
                step = diff & (-diff)
                b = doubling[b][step.bit_length()-1]
                diff -= step

        while a != b:
                j = 0
                while doubling[a][j] != doubling[b][j]:
                        j += 1
                if j==0:
                        return doubling[a][0]
                x = doubling[a][j-1]
                y = doubling[b][j-1]

        return a

task = [[] for i 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))

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: Time Limit Exceeded

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

U = 17
doubling = [[1] * U for i in range(N+1)]
for i in range(U):
        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(U)):
                        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(U)):
                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: Time Limit Exceeded

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

U = 17
doubling = [[1] * U for i in range(N+1)]
for i in range(U):
        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(U)):
                        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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

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 graph[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

tasks = [[] for _ in range(N+1)]
for i, (x, y, u, v) in enumerate(query):
    tasks[u].append((i, x, y, 1))
    tasks[v].append((i, x, y, 1))
    tasks[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 tasks[x]:
        answer[i] += coef * (total - sums[c] + nums[c] * d)
    for y, c, d in graph[x]:
        if y == parent:
            continue
        sums[c] += d
        nums[c] += 1
        total += d
        dfs(y, sums, nums, total, x)
        sums[c] -= d
        nums[c] -= 1
        total -= d
    return

dfs()

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

Submission status: Time Limit Exceeded

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


N, Q = list(map(int, input().split()))
color, distance = {}, {}
nodes = [None] * (N + 1)
links = {}
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
    if a in links:
        links[a].append(b)
    else:
        links[a] = [b]
    if b in links:
        links[b].append(a)
    else:
        links[b] = [a]
q = [list(map(int, input().split())) for _ in range(Q)]

# nodeにリンクを張る。baseは1
base = Node(1, [], 1)
history = {1}
nodes[1] = base
parents = [1]
for i in range(2, N + 1):
    next_parents = []
    for parent in parents:
        p = nodes[parent]
        children = links[parent]
        for child in children:
            if child not in history:
                history.add(child)
                next_parents.append(child)
                child_parents = [parent] + p.parents
                c = Node(child, child_parents, i)
                nodes[child] = c
    if next_parents is []:
        break
    parents = next_parents[:]

for x, y, u, v in q:
    if (u, v) in distance:
        if x in color and (u, v) in color[x]:
            print(y)
        else:
            print(distance[(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.value]
    if n != 0 and node1.value == node2.parents[n - 1]:
        root.extend(node2.parents[:n])
    else:
        i = 0
        for w1, w2 in zip(node1.parents, node2.parents[n:]):
            if w1 == w2:
                break
            i += 1
        root.extend(node2.parents[:n + i])
        root.extend(node1.parents[i::-1])
        root.append(node1.value)
    d = 0
    w = root[0]
    for r in root[1:]:
        i, j = w, r
        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: Time Limit Exceeded

Solution code:
class Node:
    
    def __init__(self, v):
        self.value = v
        self.parents = [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.parents = [parent] + parent.parents
            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:
        if x in color and (u, v) in color[x]:
            print(y)
        else:
            print(distance[(u, v)])
        continue
    node1, node2 = nodes[u], nodes[v]
    if node1.depth > node2.depth:
        node1, node2 = node2, node1
    n = node2.depth - node1.depth
    root1 = [node1]
    root = [node2]
    if n != 0 and node1 is node2.parents[n - 1]:
        root.extend(node2.parents[:n - 1])
    else:
        i = 0
        for w1, w2 in zip(node1.parents, node2.parents[n:]):
            if w1 is w2:
                break
            i += 1
        root1.extend(node1.parents[:i])
        root.extend(node2.parents[:n + i + 1])
    d = 0
    root.extend(reversed(root1))
    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: Time Limit Exceeded

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:
        if x in color and (u, v) in color[x]:
            print(y)
        else:
            print(distance[(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: Time Limit Exceeded

Solution code:
import collections
import heapq
import copy


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        #0-indexedでなくてもよいことに注意
        #u = from, v = to, d = cost
        #directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        #0-indexedでなくてもよいことに注意
        #:param s: 始点
        #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]


def solve(x, y, u, v):
    graph_ = copy.deepcopy(graph)
    if len(paths[x]) >= 1:
        for i, value in enumerate(paths[x]):
            fro, to, weight = value
            graph_.delete(fro, to)
            graph_.add(fro, to, y)
    ans, _ = graph_.Dijkstra_search(u-1)
    return ans[v-1]


N, Q = map(int, input().split())
graph = Dijkstra()
paths = collections.defaultdict(list)

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

for i in range(Q):
    x, y, u, v = map(int, input().split())
    print(solve(x, y, u, v))

Submission status: Time Limit Exceeded

Solution code:
import sys
import random
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
 
INF = 10**6
 
class RMQ:
    def __init__(self, a):
        self.n = len(a)
        self.size = 2**(self.n - 1).bit_length()
        self.data = [(INF, INF) for _ in range(2*self.size-1)]
        self.initialize(a)
 
    # Initialize data
    def initialize(self, a):
        for i in range(self.n):
            self.data[self.size + i - 1] = a[i][:]
        for i in range(self.size-2, -1, -1):
            self.data[i] = min(self.data[i*2 + 1], self.data[i*2 + 2])[:]
    
    # Update ak as x
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])[:]
    
    # Min value in [l, r)
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = (INF, INF)
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])[:]
            if L & 1:
                s = min(s, self.data[L-1])[:]
                L += 1
            L >>= 1; R >>= 1
        return s
 
class LCA:
    def __init__(self, edge, root):
        self.itr = 0
        self.edge = edge[:]
        self.path = [0] * (2*n-1)
        self.depth = [0] * (2*n-1)
        self.color = [0] * (2*n-1)
        self.weight = [0] * (2*n-1)
        self.index = [0] * n
        self.euler_tour(-1, root, 0, 0, 0, 0)
        dat = list(zip(self.depth, self.path))
        self.rmq = RMQ(dat)
    
    # Lowest ancestor of u, v
    def get_lca(self, u, v):
        l, r = self.index[u], self.index[v]
        if l > r:
            l, r = r, l
        return self.rmq.query(l, r+1)[1]
    
    def euler_tour(self, prev, v, d, k, c, w):
        self.index[v] = k
        self.path[self.itr] = v
        self.depth[self.itr] = d
        self.color[self.itr] = c
        self.weight[self.itr] = w
        self.itr += 1
        k += 1
        for dest, c, w in self.edge[v]:
            if prev == dest:
                continue
            k = self.euler_tour(v, dest, d + 1, k, c, w)
            self.path[self.itr] = v
            self.depth[self.itr] = d
            self.color[self.itr] = -c
            self.weight[self.itr] = -w
            self.itr += 1
            k += 1
        return k
        
n, q = [int(item) for item in input().split()] 
edge = [[] for _ in range(n)]
 
for _ in range(n-1):
    u, v, c, w = [int(item) for item in input().split()]
    u -= 1; v -= 1
    edge[u].append((v, c, w))
    edge[v].append((u, c, w))
 
lca = LCA(edge, 0)
memo = [dict() for _ in range(n)]
lca_memo = dict()
 
query = []
for _ in range(q):
    x, y, u, v = [int(item) for item in input().split()]
    u -= 1; v -= 1
    if u > v:
        u, v = v, u
    if (u, v) in lca_memo:
        ca = lca_memo[(u, v)]
    else:
        ca = lca.get_lca(u, v)
        lca_memo[(u, v)] = ca
    memo[u][x] = None
    memo[v][x] = None
    memo[ca][x] = None
    query.append((x, y, ca, u, v))
 
colors = [0] * n
c_depth = [0] * n
depth = 0
for p, c, w in zip(lca.path[1:], lca.color[1:], lca.weight[1:]):
    color = abs(c)
    if c < 0:
        colors[color] -= 1
    else:
        colors[color] += 1
    c_depth[color] += w
    depth += w
 
    for key in memo[p].keys():
        memo[p][key] = (colors[key], c_depth[key])
    memo[p][0] = depth 
 
ans = []
for x, y, ca, u, v in query:
    # Calc basic distance
    val = memo[u][0] + memo[v][0] - memo[ca][0] * 2
    # Append color diff
    val += (memo[v][x][0] + memo[u][x][0] - memo[ca][x][0] * 2) * y 
    val -= (memo[v][x][1] + memo[u][x][1] - memo[ca][x][1] * 2)
    ans.append(val)
print("\n".join([str(item) for item in ans]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import random
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
 
INF = 10**6
 
class RMQ:
    def __init__(self, a):
        self.n = len(a)
        self.size = 2**(self.n - 1).bit_length()
        self.data = [(INF, INF) for _ in range(2*self.size-1)]
        self.initialize(a)
 
    # Initialize data
    def initialize(self, a):
        for i in range(self.n):
            self.data[self.size + i - 1] = a[i][:]
        for i in range(self.size-2, -1, -1):
            self.data[i] = min(self.data[i*2 + 1], self.data[i*2 + 2])[:]
    
    # Update ak as x
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])[:]
    
    # Min value in [l, r)
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = (INF, INF)
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])[:]
            if L & 1:
                s = min(s, self.data[L-1])[:]
                L += 1
            L >>= 1; R >>= 1
        return s
 
class LCA:
    def __init__(self, edge, root):
        self.itr = 0
        self.edge = edge[:]
        self.path = [0] * (2*n-1)
        self.depth = [0] * (2*n-1)
        self.color = [0] * (2*n-1)
        self.weight = [0] * (2*n-1)
        self.index = [0] * n
        self.euler_tour(-1, root, 0, 0, 0, 0)
        dat = list(zip(self.depth, self.path))
        self.rmq = RMQ(dat)
    
    # Lowest ancestor of u, v
    def get_lca(self, u, v):
        l, r = self.index[u], self.index[v]
        if l > r:
            l, r = r, l
        return self.rmq.query(l, r+1)[1]
    
    def euler_tour(self, prev, v, d, k, c, w):
        self.index[v] = k
        self.path[self.itr] = v
        self.depth[self.itr] = d
        self.color[self.itr] = c
        self.weight[self.itr] = w
        self.itr += 1
        k += 1
        for dest, c, w in self.edge[v]:
            if prev == dest:
                continue
            k = self.euler_tour(v, dest, d + 1, k, c, w)
            self.path[self.itr] = v
            self.depth[self.itr] = d
            self.color[self.itr] = -c
            self.weight[self.itr] = -w
            self.itr += 1
            k += 1
        return k
        
n, q = [int(item) for item in input().split()] 
edge = [[] for _ in range(n)]
 
for i in range(n-1):
    u, v, c, w = [int(item) for item in input().split()]
    u -= 1; v -= 1
    edge[u].append((v, c, w))
    edge[v].append((u, c, w))
 
lca = LCA(edge, 0)
memo = [dict() for _ in range(n)]
lca_memo = dict()
 
query = []
for i in range(q):
    x, y, u, v = [int(item) for item in input().split()]
    u -= 1; v -= 1
    if (u, v) in lca_memo:
        ca = lca_memo[(u, v)]
    else:
        ca = lca.get_lca(u, v)
        lca_memo[(u, v)] = ca
    memo[u][x] = None
    memo[v][x] = None
    memo[ca][x] = None
    query.append((x, y, ca, u, v))
 
colors = [0] * n
c_depth = [0] * n
depth = 0
for p, c, w in zip(lca.path[1:], lca.color[1:], lca.weight[1:]):
    color = abs(c)
    if c < 0:
        colors[color] -= 1
    else:
        colors[color] += 1
    c_depth[color] += w
    depth += w
 
    for key in memo[p].keys():
        memo[p][key] = (colors[key], c_depth[key])
    memo[p][0] = depth 
 
ans = []
for x, y, ca, u, v in query:
    # Calc basic distance
    val = memo[u][0] + memo[v][0] - memo[ca][0] * 2
    # Append color diff
    val += (memo[v][x][0] + memo[u][x][0] - memo[ca][x][0] * 2) * y 
    val -= (memo[v][x][1] + memo[u][x][1] - memo[ca][x][1] * 2)
    ans.append(val)
print("\n".join([str(item) for item in ans]))