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.

Solution (Python):
import sys
from itertools import combinations, permutations, product, combinations_with_replacement, accumulate
from heapq import heapify, heappop, heappush, heappushpop
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from math import sqrt, log, floor, ceil, factorial, cos, sin, pi
from fractions import gcd
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
LINF = 2**63-1
NIL = -LINF
MOD = 10**9+7
MGN = 4
def AST(exp: bool, msg: str = ""): assert exp, msg
def TAST(exp: bool, msg = ""):
    if exp is False: print("TAssertionError:", msg)
    while exp is False:
        pass
def EPR(msg): print(msg, file=sys.stderr)
def II(): return int(input())
def IF(): return float(input())
def IS(): return input().replace('\n', '')
def ILCI(n: int): return [II() for _ in range(n)]
def ILCF(n: int): return [IF() for _ in range(n)]
def ILI(): return list(map(int, input().split()))
def ILLI(n: int): return [[int(j) for j in input().split()] for i in range(n)]
def ILF(): return list(map(float, input().split()))
def ILLF(n: int): return [[float(j) for j in input().split()] for i in range(n)]
def LTOS(lst: list, sep: str = ' '): return sep.join(map(str, lst))
def DEC(lst: list): return list(map(lambda x: x-1, lst))
def INC(lst: list): return list(map(lambda x: x+1, lst))

class LCA:
    def __init__(self, N: int) -> None:
        self.N = N
        self.to = [[] for _ in range(N)]
        self.co = [[] for _ in range(N)]
        self.dep = [0] * N
        self.costs = [0] * N
        l = 0
        while (1 << l) < N:
            l += 1
        self.l = l
        self.par = [([0]*l) for _ in range(N+1)]
    def add_edge(self, a: int, b: int, c = 0) -> None:
        self.to[a].append(b)
        self.co[a].append(c)
        self.to[b].append(a)
        self.co[b].append(c)
    def _dfs(self, v: int, d: int = 0, c = 0, p: int = -1) -> None:
        if p != -1:
            self.par[v][0] = p
        self.dep[v] = d
        self.costs[v] = c
        for i in range(len(self.to[v])):
            u = self.to[v][i]
            if u == p:
                continue
            else:
                self._dfs(u, d+1, c+self.co[v][i], v)
    def init(self, root: int = 0) -> None:
        self.root = root
        self._dfs(root)
        for i in range(self.l - 1):
            for v in range(self.N):
                self.par[v][i+1] = self.par[self.par[v][i]][i]
    def lca(self, a: int, b: int) -> int:
        dep_s, dep_l = self.dep[a], self.dep[b]
        if dep_s > dep_l:
            a, b = b, a
            dep_s, dep_l = dep_l, dep_s
        gap = dep_l - dep_s
        L_1 = self.l-1
        par = self.par
        for i in range(L_1, -1, -1):
            leng = 1 << i
            if gap >= leng:
                gap -= leng
                b = par[b][i]
        if a == b:
            return a
        for i in range(L_1, -1, -1):
            na = par[a][i]
            nb = par[b][i]
            if na != nb:
                a, b = na, nb
        return par[a][0]
    def length(self, a: int, b: int) -> int:
        c = self.lca(a, b)
        dep = self.dep
        return dep[a] + dep[b] - dep[c] * 2
    def dist(self, a: int, b: int):
        c = self.lca(a, b)
        costs = self.costs
        return costs[a] + costs[b] - costs[c] * 2

def main():
    N,Q = ILI()
    gr = LCA(N)
    es = [[] for _ in range(N)]
    for i in range(N-1):
        a,b, col, dist = ILI()
        a -= 1; b -= 1
        es[a].append((b, dist, col))
        es[b].append((a, dist, col))
        gr.add_edge(a, b, dist)

    gr.init()
    ans = [0] * Q
    qs = [[] for _ in range(N)]
    for i in range(Q):
        cx,dy, a,b = ILI()
        a -= 1; b -= 1
        
        c = gr.lca(a, b)
        ans[i] = gr.costs[a] + gr.costs[b] - gr.costs[c] * 2
        qs[a].append((cx, i, 1, dy))
        qs[b].append((cx, i, 1, dy))
        qs[c].append((cx, i, -2, dy))

    cnt = [0] * N
    sum_ = [0] * N

    def dfs(v: int, p: int = -1) -> None:
        for (col,qid,coeff,dist) in qs[v]:
            x = -sum_[col]
            x += dist * cnt[col]
            ans[qid] += x * coeff
        
        for (to, co, col) in es[v]:
            if to == p:
                continue
            cnt[col] += 1
            sum_[col] += co
            dfs(to, v)
            cnt[col] -= 1
            sum_[col] -= co

    dfs(0)

    for an in ans:
        print(an)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import combinations, permutations, product, combinations_with_replacement, accumulate
from heapq import heapify, heappop, heappush, heappushpop
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from math import sqrt, log, floor, ceil, factorial, cos, sin, pi
from fractions import gcd
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
LINF = 2**63-1
NIL = -LINF
MOD = 10**9+7
MGN = 4
def AST(exp: bool, msg: str = ""): assert exp, msg
def TAST(exp: bool, msg = ""):
    if exp is False: print("TAssertionError:", msg)
    while exp is False:
        pass
def EPR(msg): print(msg, file=sys.stderr)
def II(): return int(input())
def IF(): return float(input())
def IS(): return input().replace('\n', '')
def ILCI(n: int): return [II() for _ in range(n)]
def ILCF(n: int): return [IF() for _ in range(n)]
def ILI(): return list(map(int, input().split()))
def ILLI(n: int): return [[int(j) for j in input().split()] for i in range(n)]
def ILF(): return list(map(float, input().split()))
def ILLF(n: int): return [[float(j) for j in input().split()] for i in range(n)]
def LTOS(lst: list, sep: str = ' '): return sep.join(map(str, lst))
def DEC(lst: list): return list(map(lambda x: x-1, lst))
def INC(lst: list): return list(map(lambda x: x+1, lst))

class LCA:
    def __init__(self, N: int) -> None:
        self.N = N
        self.to = [[] for _ in range(N)]  
        self.co = [[] for _ in range(N)]  
        self.dep = [0] * N  
        self.costs = [0] * N  
        l = 0
        while (1 << l) < N:
            l += 1
        self.l = l
        self.par = [([0]*l) for _ in range(N+1)]  
    def add_edge(self, a: int, b: int, c = 0) -> None:
        self.to[a].append(b)
        self.co[a].append(c)
        self.to[b].append(a)
        self.co[b].append(c)
    def _dfs(self, v: int, d: int = 0, c = 0, p: int = -1) -> None:
        if p != -1:
            self.par[v][0] = p  
        self.dep[v] = d
        self.costs[v] = c
        for i in range(len(self.to[v])):
            u = self.to[v][i]
            if u == p:
                continue
            else:
                self._dfs(u, d+1, c+self.co[v][i], v)
    def init(self, root: int = 0) -> None:
        self.root = root
        self._dfs(root)
        for i in range(self.l - 1):
            for v in range(self.N):
                self.par[v][i+1] = self.par[self.par[v][i]][i]
    
    def lcs(self, a: int, b: int) -> int:
        dep_s, dep_l = self.dep[a], self.dep[b]
        self_par = self.par
        if dep_s > dep_l:
            a, b = b, a  
            dep_s, dep_l = dep_l, dep_s
        gap = dep_l - dep_s
        L_1 = self.l-1
        for i in range(L_1, -1, -1):
            leng = 1 << i
            if gap >= leng:
                gap -= leng
                b = self_par[b][i]
        if a == b:  
            return a
        for i in range(L_1, -1, -1):
            na = self_par[a][i]
            nb = self_par[b][i]
            if na != nb:
                a, b = na, nb
        return self_par[a][0]
    def length(self, a: int, b: int) -> int:
        
        c = self.lcs(a, b)
        return self.dep[a] + self.dep[b] - self.dep[c] * 2
    def dist(self, a: int, b: int):
        
        c = self.lcs(a, b)
        return self.costs[a] + self.costs[b] - self.costs[c] * 2

def main():
    N,Q = ILI()
    gr = LCA(N)
    es = [[] for _ in range(N)]
    for i in range(N-1):
        a,b, col, dist = ILI()
        a -= 1; b -= 1
        es[a].append((b, dist, col))
        es[b].append((a, dist, col))
        gr.add_edge(a, b, dist)

    gr.init()
    ans = [0] * Q
    qs = [[] for _ in range(N)]
    for i in range(Q):
        cx,dy, a,b = ILI()
        a -= 1; b -= 1
        
        c = gr.lcs(a, b)
        ans[i] = gr.costs[a] + gr.costs[b] - gr.costs[c] * 2
        qs[a].append((cx, i, 1, dy))
        qs[b].append((cx, i, 1, dy))
        qs[c].append((cx, i, -2, dy))

    cnt = [0] * N
    sum_ = [0] * N

    def dfs(v: int, p: int = -1) -> None:
        for (col,qid,coeff,dist) in qs[v]:
            x = -sum_[col]
            x += dist * cnt[col]
            ans[qid] += x * coeff
        
        for (to, co, col) in es[v]:
            if to == p:
                continue
            cnt[col] += 1
            sum_[col] += co
            dfs(to, v)
            cnt[col] -= 1
            sum_[col] -= co

    dfs(0)

    for an in ans:
        print(an)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import combinations, permutations, product, combinations_with_replacement, accumulate
from heapq import heapify, heappop, heappush, heappushpop
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from math import sqrt, log, floor, ceil, factorial, cos, sin, pi
from fractions import gcd
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
LINF = 2**63-1
NIL = -LINF
MOD = 10**9+7
MGN = 4
def AST(exp: bool, msg: str = ""): assert exp, msg
def TAST(exp: bool, msg = ""):
    if exp is False: print("TAssertionError:", msg)
    while exp is False:
        pass
def II(): return int(input())
def IF(): return float(input())
def IS(): return input().replace('\n', '')
def ILCI(n: int): return [II() for _ in range(n)]
def ILCF(n: int): return [IF() for _ in range(n)]
def ILI(): return list(map(int, input().split()))
def ILLI(n: int): return [[int(j) for j in input().split()] for i in range(n)]
def ILF(): return list(map(float, input().split()))
def ILLF(n: int): return [[float(j) for j in input().split()] for i in range(n)]
def LTOS(lst: list, sep: str = ' '): return sep.join(map(str, lst))
def DEC(lst: list): return list(map(lambda x: x-1, lst))
def INC(lst: list): return list(map(lambda x: x+1, lst))

class LCA:
    def __init__(self, N: int) -> None:
        self.N = N
        self.to = [[] for _ in range(N)]  
        self.co = [[] for _ in range(N)]  
        self.dep = [0] * N  
        self.costs = [0] * N  
        l = 0
        while (1 << l) < N:
            l += 1
        self.l = l
        self.par = [([0]*l) for _ in range(N+1)]  
    def add_edge(self, a: int, b: int, c = 0) -> None:
        self.to[a].append(b)
        self.co[a].append(c)
        self.to[b].append(a)
        self.co[b].append(c)
    def _dfs(self, v: int, d: int = 0, c = 0, p: int = -1) -> None:
        if p != -1:
            self.par[v][0] = p  
        self.dep[v] = d
        self.costs[v] = c
        for i in range(len(self.to[v])):
            u = self.to[v][i]
            if u == p:
                continue
            else:
                self._dfs(u, d+1, c+self.co[v][i], v)
    def init(self, root: int = 0) -> None:
        self.root = root
        self._dfs(root)
        for i in range(self.l - 1):
            for v in range(self.N):
                self.par[v][i+1] = self.par[self.par[v][i]][i]
    def __call__(self, a: int, b: int) -> int:
        dep_s, dep_l = self.dep[a], self.dep[b]
        if dep_s > dep_l:
            a, b = b, a  
            dep_s, dep_l = dep_l, dep_s
        gap = dep_l - dep_s
        L_1 = self.l-1
        for i in range(L_1, -1, -1):
            leng = 1 << i
            if gap >= leng:
                gap -= leng
                b = self.par[b][i]
        if a == b:  
            return a
        for i in range(L_1, -1, -1):
            na = self.par[a][i]  
            nb = self.par[b][i]  
            if na != nb:
                a, b = na, nb
        return self.par[a][0]
    def length(self, a: int, b: int) -> int:
        c = self.__call__(a, b)
        return self.dep[a] + self.dep[b] - self.dep[c] * 2
    def dist(self, a: int, b: int):
        c = self.__call__(a, b)
        return self.costs[a] + self.costs[b] - self.costs[c] * 2

def main():
    N,Q = ILI()
    gr = LCA(N)
    es = [[] for _ in range(N)]
    for i in range(N-1):
        a,b, col, dist = ILI()
        a -= 1; b -= 1
        es[a].append((b, dist, col))
        es[b].append((a, dist, col))
        gr.add_edge(a, b, dist)

    gr.init()
    ans = [0] * Q
    qs = [[] for _ in range(N)]
    for i in range(Q):
        cx,dy, a,b = ILI()
        a -= 1; b -= 1
        c = gr(a, b)
        ans[i] = gr.costs[a] + gr.costs[b] - gr.costs[c] * 2
        qs[a].append((cx, i, 1, dy))
        qs[b].append((cx, i, 1, dy))
        qs[c].append((cx, i, -2, dy))

    cnt = [0] * N
    sum_ = [0] * N

    def dfs(v: int, p: int = -1) -> None:
        for (col,qid,coeff,dist) in qs[v]:
            x = -sum_[col]
            x += dist * cnt[col]
            ans[qid] += x * coeff
        
        for (to, co, col) in es[v]:
            if to == p:
                continue
            cnt[col] += 1
            sum_[col] += co
            dfs(to, v)
            cnt[col] -= 1
            sum_[col] -= co

    dfs(0)
    for i in range(Q):
        print(ans[i])


if __name__ == '__main__':
    main()

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

    
    class SparseTable():
        def __init__(self, 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):
            
            k = (r - l).bit_length() - 1
            return STfunc(self.table[l][k], self.table[r - (1 << k)][k])

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

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

Solution (Python):
import sys
input=lambda :sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**8)

class LCA(object):
    def __init__(self, to, root=0):
        self.__n = len(to)
        self.__to = to
        self.__logn = (self.__n - 1).bit_length()
        self.__depth = [-1] * self.__n
        self.__dist = [-1] * self.__n
        self.__depth[root] = 0
        self.__dist[root] = 0
        self.__parents = [[-1] * self.__n for _ in range(self.__logn)]
        self.__dfs(root)
        self.__doubling()

    def __dfs(self, v):
        for u, c, d in self.__to[v]:
            if self.__depth[u] != -1: continue
            self.__parents[0][u] = v
            self.__depth[u] = self.__depth[v] + 1
            self.__dist[u] = self.__dist[v] + d
            self.__dfs(u)

    def __doubling(self):
        for i in range(1, self.__logn):
            for v in range(self.__n):
                if self.__parents[i - 1][v] == -1: continue
                self.__parents[i][v] = self.__parents[i - 1][self.__parents[i - 1][v]]

    @property
    def depth(self):
        return self.__depth

    @property
    def dist(self):
        return self.__dist

    def get(self, u, v):
        dd = self.__depth[v] - self.__depth[u]
        if dd < 0:
            u, v = v, u
            dd *= -1
        for i in range(self.__logn):
            if dd & (2 ** i):
                v = self.__parents[i][v]
        if v == u: return v
        for i in range(self.__logn - 1, -1, -1):
            pu = self.__parents[i][u]
            pv = self.__parents[i][v]
            if pu != pv: u, v = pu, pv
        return self.__parents[0][u]

def resolve():
    n, q = map(int, input().split())
    to = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b, c, d = map(int, input().split())
        a -= 1; b -= 1
        to[a].append((b, c, d))
        to[b].append((a, c, d))

    G = LCA(to)
    Query = [[] for _ in range(n)]
    for i in range(q):
    
        x, y, u, v = map(int, input().split())
        u -= 1; v -= 1
        c = G.get(u, v)
        Query[u].append((i, x, y, 1))
        Query[v].append((i, x, y, 1))
        Query[c].append((i, x, y, -2))

    ans = [0] * q
    S = [[0, 0] for _ in range(n)]

    def dfs(v, p=-1):
        for idx, color, mag, coef in Query[v]:
            x = G.dist[v]
            x -= S[color][1]
            x += mag * S[color][0]
            ans[idx] += x * coef
        for nv, color, d in to[v]:
            if nv == p: continue
            S[color][0] += 1
            S[color][1] += d
            dfs(nv, v)
            S[color][0] -= 1
            S[color][1] -= d
    dfs(0)
    print(*ans, sep="\n")

resolve()

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

    
    class SparseTable():
        def __init__(self, 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):
            
            k = (r - l).bit_length() - 1
            return STfunc(self.table[l][k], self.table[r - (1 << k)][k])

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

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

Solution (Python):
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  
    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()