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: Accepted

Solution code:
def main():
    import sys
    from bisect import bisect_left
    input = sys.stdin.buffer.readline

    # クエリは0-indexedで[l, r)
    class SparseTable():
        def __init__(self, A):
            # A: 処理したい数列
            self.N = len(A)
            self.K = self.N.bit_length() - 1
            self.table = [[0] * (self.K + 1) for _ in range(self.N)]
            for i, a in enumerate(A):
                self.table[i][0] = a
            for k in range(1, self.K + 1):
                for i in range(self.N):
                    j = i + (1 << (k - 1))
                    if j <= self.N - 1:
                        self.table[i][k] = STfunc(self.table[i][k - 1], self.table[j][k - 1])
                    else:
                        self.table[i][k] = self.table[i][k - 1]

        def query(self, l, r):
            # [l, r)の最小値を求める
            k = (r - l).bit_length() - 1
            return STfunc(self.table[l][k], self.table[r - (1 << k)][k])

    # adj[0] must be empty list
    def EulerTour(adj, root):
        st = [root]
        ret = []
        seen = [0] * len(adj)
        par = [0] * len(adj)
        depth = [0] * len(adj)
        while st:
            v = st.pop()
            if seen[v]:
                ret.append(v)
                continue
            ret.append(v)
            seen[v] = 1
            if par[v] != 0:
                st.append(par[v])
            for u in adj[v]:
                if seen[u] == 0:
                    st.append(u)
                    par[u] = v
                    depth[u] = depth[v] + 1

        return ret, depth

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

    et, depth = EulerTour(adj, 1)
    left = [-1] * (N + 1)
    right = [-1] * (N + 1)
    dist_from_root = [-1] * (N+1)
    dist_from_root[1] = 0
    color_info = [[] for _ in range(N)]
    color_d = [[] for _ in range(N)]
    for i, v in enumerate(et):
        if left[v] < 0:
            left[v] = i
        right[v] = i
        if i != 0:
            u = et[i-1]
            c, d = E[v*(N+1)+u]
            if dist_from_root[v] < 0:
                dist_from_root[v] = dist_from_root[u] + d
            if depth[u] < depth[v]:
                color_info[c].append(i)
                if not color_d[c]:
                    color_d[c].append((1, d))
                else:
                    prev_num, prev_d = color_d[c][-1]
                    color_d[c].append((prev_num+1, prev_d+d))
            else:
                color_info[c].append(i)
                prev_num, prev_d = color_d[c][-1]
                color_d[c].append((prev_num - 1, prev_d - d))

    # min
    def STfunc(a, b):
        if depth[a] < depth[b]:
            return a
        else:
            return b

    ST = SparseTable(et)
    for _ in range(Q):
        x, y, u, v = map(int, input().split())
        lca = ST.query(min(left[u], left[v]), max(right[u], right[v])+1)
        if color_info[x]:
            le = len(color_info[x])
            iu = bisect_left(color_info[x], left[u]+1) - 1
            if iu == -1:
                du = dist_from_root[u]
            else:
                num_u, dist_u = color_d[x][iu]
                du = dist_from_root[u] + num_u * y - dist_u
            
            iv = bisect_left(color_info[x], left[v]+1) - 1
            if iv == -1:
                dv = dist_from_root[v]
            else:
                num_v, dist_v = color_d[x][iv]
                dv = dist_from_root[v] + num_v * y - dist_v

            ilca = bisect_left(color_info[x], left[lca]+1) - 1
            if ilca == -1:
                dlca = dist_from_root[lca]
            else:
                num_lca, dist_lca = color_d[x][ilca]
                dlca = dist_from_root[lca] + num_lca * y - dist_lca

            print(du + dv - 2*dlca)
        else:
            print(dist_from_root[u] + dist_from_root[v] - 2 * dist_from_root[lca])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    INF = float('inf')

    N, Q = map(int, input().split())
    adjL = [[] for _ in range(N)]
    for _ in range(N-1):
        A, B, C, D = map(int, input().split())
        A, B, C = A-1, B-1, C-1
        adjL[A].append((B, C, D))
        adjL[B].append((A, C, D))
    querys = [tuple(map(int, input().split())) for _ in range(Q)]

    def dfs(vNow, vPar, depth):
        iVFirsts[vNow] = len(vs)
        vs.append(vNow)
        depths.append(depth)
        for v2, clr, dist in adjL[vNow]:
            if v2 == vPar: continue
            iVColorss[clr].append(len(numEs))
            numEs.append(1)
            sumDs.append(dist)

            dfs(v2, vNow, depth+1)

            vs.append(vNow)
            depths.append(depth)
            iVColorss[clr].append(len(numEs))
            numEs.append(-1)
            sumDs.append(-dist)

    vs = []
    iVFirsts = [-1] * N
    depths = []
    numEs = [0]
    sumDs = [0]
    iVColorss = [[0] for _ in range(N-1)]

    dfs(0, -1, 0)

    dists = [0] * N
    accD = 0
    for i, sumD in enumerate(sumDs):
        accD += sumD
        if iVFirsts[vs[i]] == i:
            dists[vs[i]] = accD

    for iVColors in iVColorss:
        for i in range(1, len(iVColors)):
            numEs[iVColors[i]] += numEs[iVColors[i-1]]
            sumDs[iVColors[i]] += sumDs[iVColors[i-1]]

    idEle = (INF, -1)
    def _binOpe(x, y):
        return x if x <= y else y  # min
    def makeSegTree(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [idEle] * (2*numPow2)
        return data, numPow2
    def setInit(As):
        for iST, A in enumerate(As, numPow2):
            data[iST] = A
        for iST in reversed(range(1, numPow2)):
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def getValue(iSt, iEn):
        L = iSt + numPow2
        R = iEn + numPow2
        ans = idEle
        while L < R:
            if L & 1:
                ans = _binOpe(ans, data[L])
                L += 1
            if R & 1:
                R -= 1
                ans = _binOpe(ans, data[R])
            L >>= 1
            R >>= 1
        return ans

    data, numPow2 = makeSegTree(len(depths))
    setInit([(depth, i) for i, depth in enumerate(depths)])

    def getLCA(x, y):
        L, R = iVFirsts[x], iVFirsts[y]
        if L > R:
            L, R = R, L
        minV, iMinV = getValue(L, R)
        return vs[iMinV]

    anss = []
    for clr, distNew, u, v in querys:
        u, v = u-1, v-1
        LCA = getLCA(u, v)

        clr -= 1
        ds = [dists[u], dists[v], dists[LCA]]
        for i, vv in enumerate([u, v, LCA]):
            iIV = bisect_right(iVColorss[clr], iVFirsts[vv]) - 1
            iV = iVColorss[clr][iIV]
            ds[i] += numEs[iV] * distNew - sumDs[iV]
        ans = ds[0] + ds[1] - 2*ds[2]
        anss.append(ans)

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


solve()

Submission status: Accepted

Solution code:
# verified: ABC014-D
# calculate LCA O(logN) for each query

# kprev[k][i]: 2^k parent of node i 
# if there is no node returns "None"
# Depth[i]: Depth of node i from rootNode

class Doubling():
    def __init__(self, graph, Depth, prev, rootNode=0):
        self.graph = graph
        self.N = len(graph)
        self.Log_N = (self.N-1).bit_length()
        self.rootNode = rootNode
        # BFSしない
        self.prev = prev 
        self.Depth = Depth

        # construct
        self.kprev = [self.prev]
        S = self.prev
        for k in range(self.Log_N):
            T = [None]*self.N
            for i in range(self.N):
                if S[i] is None:
                    continue
                T[i] = S[S[i]]
            self.kprev.append(T)
            S = T

    # LCA
    def LCAquery(self, u, v):
        dd = self.Depth[v] - self.Depth[u]
        if dd < 0:
            u, v = v, u
            dd = -dd
        
        # set same Depth
        for k in range(self.Log_N+1):
            if dd & 1:
                v = self.kprev[k][v]
            dd >>= 1
        
        if u == v:
            return u
        
        for k in reversed(range(self.Log_N)):
            pu = self.kprev[k][u]
            pv = self.kprev[k][v]
            if pu != pv:
                u, v = pu, pv
        
        return self.kprev[0][u]

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from bisect import bisect_right

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

Query = [list(map(int, input().split())) for _ in range(Q)]


D = [-1]*N
D[0] = 0
EulerTour = []
Color = [0]*N
Weight = [0]*N
PointFront = [-1]*N
prev = [None]*N
Depth = [0]*N
def dfs(p):
    PointFront[p] = len(EulerTour)
    EulerTour.append((p, +1))
    for np, c, d in graph[p]:
        if D[np] == -1:
            Color[np] = c
            Weight[np] = d
            D[np] = D[p] + d
            Depth[np] = Depth[p] + 1
            prev[np] = p
            dfs(np)
    EulerTour.append((p, -1))

def dfs2():
    stack = [0]
    while stack:
        p = stack[-1]
        if PointFront[p] == -1:
            PointFront[p] = len(EulerTour)
            EulerTour.append((p, +1))
        for np, c, d in graph[p]:
            if D[np] == -1:
                Color[np] = c
                Weight[np] = d
                D[np] = D[p] + d
                Depth[np] = Depth[p] + 1
                prev[np] = p
                stack.append(np)
        if p == stack[-1]:
            EulerTour.append((p, -1))    
            stack.pop()
            

#dfs(0)
dfs2()


Indexes = [[] for _ in range(N)]
Weights = [[0] for _ in range(N)]
Colors = [[0] for _ in range(N)]
for i, (p, num) in enumerate(EulerTour):
    if p == 0: continue
    w = Weight[p]*num
    c = Color[p]
    Weights[c].append(Weights[c][-1]+w)
    Colors[c].append(Colors[c][-1]+num)
    Indexes[c].append(i)



# point までにある color 指定された時のスコア
def fixed_score(point, color, replace):
    ind = bisect_right(Indexes[color], PointFront[point])
    return D[point] - Weights[color][ind] + Colors[color][ind]*replace


def main():
    doubling = Doubling(graph, Depth, prev)
    ans = []
    for x, y, u, v in Query:
        u -= 1; v -= 1
        lca = doubling.LCAquery(u, v)
        ans.append(fixed_score(u, x, y) + fixed_score(v, x, y) - 2*fixed_score(lca, x, y))
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class LCA(object):
    def __init__(self, G, root=0):
        self.G = G
        self.root = root
        self.n = len(G)
        self.logn = (self.n - 1).bit_length()
        self.depth = [-1 if i != root else 0 for i in range(self.n)]
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.dfs()
        self.doubling()

    def dfs(self):
        que = [self.root]
        while que:
            u = que.pop()
            for v in self.G[u]:
                if self.depth[v] == -1:
                    self.depth[v] = self.depth[u] + 1
                    self.parent[0][v] = u
                    que += [v]

    def doubling(self):
        for i in range(1, self.logn):
            for v in range(self.n):
                if self.parent[i - 1][v] != -1:
                    self.parent[i][v] = self.parent[i - 1][self.parent[i - 1][v]]

    def get(self, u, v):
        if self.depth[v] < self.depth[u]:
            u, v = v, u
        du = self.depth[u]
        dv = self.depth[v]

        for i in range(self.logn):  # depthの差分だけuを遡らせる
            if (dv - du) >> i & 1:
                v = self.parent[i][v]
        if u == v: return u  # 高さ揃えた時点で一致してたら終わり

        for i in range(self.logn - 1, -1, -1):  # そうでなければ上から二分探索
            pu, pv = self.parent[i][u], self.parent[i][v]
            if pu != pv:
                u, v = pu, pv
        return self.parent[0][u]
# query先読みで、頂点ごとに、どの色の長さを求めるのか。
n, q = LI()
edge_dict = [{} for _ in range(n)]
for u, v, c, d in LIR(n - 1):
    edge_dict[u - 1][v - 1] = (c, d)
    edge_dict[v - 1][u - 1] = (c, d)

lca = LCA(edge_dict)
query = [[] for _ in range(n)]
for q_idx, (x, y, u, v) in enumerate(LIR(q)):
    query[u - 1] += [(q_idx, x, y, 1)]
    query[v - 1] += [(q_idx, x, y, 1)]
    query[lca.get(u - 1, v - 1)] += [(q_idx, x, y, 0)]

def euler_tour(G, root=0):
    n = len(G)
    euler = []
    dq = deque([root])
    dq2 = deque()
    visited = [0] * n
    while dq:
        u = dq.pop()
        euler += [u]
        if visited[u]:
            continue
        for v in G[u]:
            if visited[v]:
                dq += [v]
            # [親頂点、子頂点、子頂点、。。。]と入れていく.その後連結
            else:
                dq2 += [v]
        dq.extend(dq2)
        dq2 = deque()
        visited[u] = 1
    return euler

dist = 0
color_len = [0] * n
color_cnt = [0] * n
ans = [0] * q
euler = euler_tour(edge_dict)
for i in range(1, len(euler)):
    now_v = euler[i]
    pre_v = euler[i - 1]
    c, d = edge_dict[pre_v][now_v]
    if lca.depth[pre_v] < lca.depth[now_v]:
        dist += d
        color_len[c] += d
        color_cnt[c] += 1
        for q_idx, x, y, flag in query[now_v]:
            if flag:
                ans[q_idx] += dist - color_len[x] + color_cnt[x] * y
            else:
                ans[q_idx] -= (dist - color_len[x] + color_cnt[x] * y) * 2
    else:
        dist -= d
        color_len[c] -= d
        color_cnt[c] -= 1


print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class LCA(object):
    def __init__(self, G, root=0):
        self.G = G
        self.root = root
        self.n = len(G)
        self.logn = (self.n - 1).bit_length()
        self.depth = [-1 if i != root else 0 for i in range(self.n)]
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.dfs()
        self.doubling()

    def dfs(self):
        que = [self.root]
        while que:
            u = que.pop()
            for v in self.G[u]:
                if self.depth[v] == -1:
                    self.depth[v] = self.depth[u] + 1
                    self.parent[0][v] = u
                    que += [v]

    def doubling(self):
        for i in range(1, self.logn):
            for v in range(self.n):
                if self.parent[i - 1][v] != -1:
                    self.parent[i][v] = self.parent[i - 1][self.parent[i - 1][v]]

    def get(self, u, v):
        if self.depth[v] < self.depth[u]:
            u, v = v, u
        du = self.depth[u]
        dv = self.depth[v]

        for i in range(self.logn):  # depthの差分だけuを遡らせる
            if (dv - du) >> i & 1:
                v = self.parent[i][v]
        if u == v: return u  # 高さ揃えた時点で一致してたら終わり

        for i in range(self.logn - 1, -1, -1):  # そうでなければ上から二分探索
            pu, pv = self.parent[i][u], self.parent[i][v]
            if pu != pv:
                u, v = pu, pv
        return self.parent[0][u]
# query先読みで、頂点ごとに、どの色の長さを求めるのか。
n, q = LI()
edge_dict = [{} for _ in range(n)]
for u, v, c, d in LIR(n - 1):
    edge_dict[u - 1][v - 1] = (c, d)
    edge_dict[v - 1][u - 1] = (c, d)

lca = LCA(edge_dict)
query = [[] for _ in range(n)]
for q_idx, (x, y, u, v) in enumerate(LIR(q)):
    query[u - 1] += [(q_idx, x, y, 1)]
    query[v - 1] += [(q_idx, x, y, 1)]
    query[lca.get(u - 1, v - 1)] += [(q_idx, x, y, 0)]

def euler_tour(G, root=0):
    n = len(G)
    euler = []
    depth = [-1] * n
    depth[root] = 0
    dq = deque([root])
    dq2 = deque()
    visited = [0] * n
    while dq:
        u = dq.pop()
        euler += [(depth[u], u)]
        if visited[u]:
            continue
        for v in G[u]:
            if visited[v]:
                dq += [v]
            # [親頂点、子頂点、子頂点、。。。]と入れていく.その後連結
            else:
                depth[v] = depth[u] + 1
                dq2 += [v]
        dq.extend(dq2)
        dq2 = deque()
        visited[u] = 1
    return euler

dist = 0
color_len = [0] * n
color_cnt = [0] * n
ans = [0] * q
euler = euler_tour(edge_dict)
for i in range(1, len(euler)):
    dep = euler[i][0]
    c, d = edge_dict[euler[i - 1][1]][euler[i][1]]
    if euler[i - 1][0] < euler[i][0]:
        dist += d
        color_len[c] += d
        color_cnt[c] += 1
        for q_idx, x, y, flag in query[euler[i][1]]:
            if flag:
                ans[q_idx] += dist - color_len[x] + color_cnt[x] * y
            else:
                ans[q_idx] -= (dist - color_len[x] + color_cnt[x] * y) * 2
    else:
        dist -= d
        color_len[c] -= d
        color_cnt[c] -= 1


print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class LCA:
    def __init__(self,v,Edges,root=0):
        self.v=v
        self.Edges=Edges
        self.maxLog=18
        self.Parent=[[-1]*v for _ in range(self.maxLog+1)]
        self.Depth=[0]*v
        self.__bfs(root)
        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 __bfs(self,root):
        Visited=[False]*self.v
        Visited[root]=True
        q=deque([root])
        while q:
            fr=q.pop()
            for to in self.Edges[fr]:
                if Visited[to]:
                    continue
                self.Parent[0][to]=fr
                self.Depth[to]=self.Depth[fr]+1
                Visited[to]=True
                q.append(to)
    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]

# query先読みで、頂点ごとに、どの色の長さを求めるのか。
n, q = LI()
edge_dict = [{} for _ in range(n)]
for u, v, c, d in LIR(n - 1):
    edge_dict[u - 1][v - 1] = (c, d)
    edge_dict[v - 1][u - 1] = (c, d)

lca = LCA(n, edge_dict)
query = [[] for _ in range(n)]
for q_idx, (x, y, u, v) in enumerate(LIR(q)):
    query[u - 1] += [(q_idx, x, y, 1)]
    query[v - 1] += [(q_idx, x, y, 1)]
    query[lca.lca(u - 1, v - 1)] += [(q_idx, x, y, 0)]

def euler_tour(G, root=0):
    n = len(G)
    euler = []
    depth = [-1] * n
    depth[root] = 0
    dq = [root]
    dq2 = deque()
    visited = [0] * n
    while dq:
        u = dq.pop()
        euler += [(depth[u], u)]
        if visited[u]:
            continue
        for v in G[u]:
            if visited[v]:
                dq += [v]
            # [親頂点、子頂点、子頂点、。。。]と入れていく.その後連結
            else:
                depth[v] = depth[u] + 1
                dq2 += [v]
        dq.extend(dq2)
        dq2 = deque()
        visited[u] = 1
    return euler

dist = 0
color_len = [0] * n
color_cnt = [0] * n
ans = [0] * q
euler = euler_tour(edge_dict)
for i in range(1, len(euler)):
    dep = euler[i][0]
    c, d = edge_dict[euler[i - 1][1]][euler[i][1]]
    if euler[i - 1][0] < euler[i][0]:
        dist += d
        color_len[c] += d
        color_cnt[c] += 1
        for q_idx, x, y, flag in query[euler[i][1]]:
            if flag:
                ans[q_idx] += dist - color_len[x] + color_cnt[x] * y
            else:
                ans[q_idx] -= (dist - color_len[x] + color_cnt[x] * y) * 2
    else:
        dist -= d
        color_len[c] -= d
        color_cnt[c] -= 1


print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class LCA:
    def __init__(self,v,Edges,root=0):
        self.v=v
        self.Edges=Edges
        self.maxLog=18
        self.Parent=[[-1]*v for _ in range(self.maxLog+1)]
        self.Depth=[0]*v
        self.__bfs(root)
        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 __bfs(self,root):
        Visited=[False]*self.v
        Visited[root]=True
        q=deque([root])
        while q:
            fr=q.pop()
            for to in self.Edges[fr]:
                if Visited[to]:
                    continue
                self.Parent[0][to]=fr
                self.Depth[to]=self.Depth[fr]+1
                Visited[to]=True
                q.append(to)
    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]

# query先読みで、頂点ごとに、どの色の長さを求めるのか。
n, q = LI()
edge_dict = [{} for _ in range(n)]
for u, v, c, d in LIR(n - 1):
    edge_dict[u - 1][v - 1] = (c, d)
    edge_dict[v - 1][u - 1] = (c, d)

lca = LCA(n, edge_dict)
query = [[] for _ in range(n)]
for q_idx, (x, y, u, v) in enumerate(LIR(q)):
    query[u - 1] += [(q_idx, x, y, 1)]
    query[v - 1] += [(q_idx, x, y, 1)]
    query[lca.lca(u - 1, v - 1)] += [(q_idx, x, y, 0)]

def euler_tour(G, root=0):
    n = len(G)
    euler = []
    depth = [-1] * n
    depth[root] = 0
    dq = deque([root])
    dq2 = deque()
    visited = [0] * n
    while dq:
        u = dq.pop()
        euler += [(depth[u], u)]
        if visited[u]:
            continue
        for v in G[u]:
            if visited[v]:
                dq += [v]
            # [親頂点、子頂点、子頂点、。。。]と入れていく.その後連結
            else:
                depth[v] = depth[u] + 1
                dq2 += [v]
        dq.extend(dq2)
        dq2 = deque()
        visited[u] = 1
    return euler

dist = 0
color_len = [0] * n
color_cnt = [0] * n
ans = [0] * q
euler = euler_tour(edge_dict)
for i in range(1, len(euler)):
    dep = euler[i][0]
    c, d = edge_dict[euler[i - 1][1]][euler[i][1]]
    if euler[i - 1][0] < euler[i][0]:
        dist += d
        color_len[c] += d
        color_cnt[c] += 1
        for q_idx, x, y, flag in query[euler[i][1]]:
            if flag:
                ans[q_idx] += dist - color_len[x] + color_cnt[x] * y
            else:
                ans[q_idx] -= (dist - color_len[x] + color_cnt[x] * y) * 2
    else:
        dist -= d
        color_len[c] -= d
        color_cnt[c] -= 1


print(*ans, sep='\n')