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 bisect
from collections import deque


class LowestCommonAncestor():
    """根付き木に対して、二頂点の共通の祖先で最も近いところにある頂点を求める
    初期化(ダブリング配列parent[k][v]の構築): O(NlogN)
    lcaを求めるクエリ: O(logN)
    """
    def __init__(self, tree, root):
        self.n = len(tree)
        self.depth = [0] * self.n
        self.log_size = (self.n).bit_length()
        self.parent = [[-1] * self.n for i in range(self.log_size)]

        
        
        q = deque([(root, -1, 0)]) 
        while q:
            v, par, dist = q.pop()
            self.parent[0][v] = par
            self.depth[v] = dist
            for child_v, _, _ in tree[v]:
                if child_v != par:
                    self.depth[child_v] = dist + 1
                    q.append((child_v, v, dist + 1))

        
        for k in range(1, self.log_size):
            for v in range(self.n):
                self.parent[k][v] = self.parent[k-1][self.parent[k-1][v]]
            
    def lca(self, u, v):
        
        if self.depth[u] > self.depth[v]:
            u, v = v, u
        for k in range(self.log_size):
            if (self.depth[v] - self.depth[u] >> k) & 1:
                v = self.parent[k][v]
        if u == v:
            return u
          
        
        for k in reversed(range(self.log_size)):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]
 

def euler_tour(tree: list, root: int):
    """根をrootとしたときの辺に対するオイラーツアーを行う
    posの部分木が区間[begin[pos], end[pos])に対応する
    """
    n = len(tree)
    trail = []
    weight = []
    color = []
    begin = [-1] * n
    end = [-1] * n
    par = {root: -1}
    stack = [(root, 0, 0)]

    while stack:
        v, c, col = stack.pop()
        if v >= 0:  
            trail.append(v)
            weight.append(c)
            color.append(col)
            begin[v] = len(trail) - 1
            end[v] = len(trail)
            stack.append((~v, -c, col))
            for nxt_v, nxt_c, nxt_col in tree[v]:
                if nxt_v not in par:
                    par[nxt_v] = v
                    stack.append((nxt_v, nxt_c, nxt_col))

        else:  
            if ~v == root:
                continue
            trail.append(par[~v])
            weight.append(c)
            color.append(col)
            end[par[~v]] = len(trail)

    return trail, weight, color, begin, end


n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n - 1)]
query = [list(map(int, input().split())) for i in range(q)]

tree = [[] for i in range(n)]
for a, b, col, dist in info:
    a -= 1
    b -= 1
    tree[a].append((b, dist, col))
    tree[b].append((a, dist, col))

trail, weight, color, begin, end = euler_tour(tree, 0)


w_col = [[0] for i in range(n)]
for i in range(len(weight)):
    col = color[i]
    w_col[col].append(weight[i] + w_col[col][-1])


cnt_col = [[0] for i in range(n)]
for i in range(len(weight)):
    col = color[i]
    cnt_col[col].append(int(2 * (weight[i] >= 1)) - 1 + cnt_col[col][-1])


ind = [[] for i in range(n)]
for i in range(len(weight)):
    col = color[i]
    ind[col].append(i)


for i in range(len(weight) - 1):
    weight[i + 1] += weight[i]

lca = LowestCommonAncestor(tree, 0)
for x, y, u, v in query:
    u -= 1
    v -= 1
    lca_uv = lca.lca(u, v)

    ans = weight[begin[u]] + weight[begin[v]] - 2 * weight[begin[lca_uv]]

    l = bisect.bisect_right(ind[x], begin[u])
    r = bisect.bisect_right(ind[x], begin[v])
    mid = bisect.bisect_right(ind[x], begin[lca_uv])
    
    cnt = cnt_col[x][r] + cnt_col[x][l] - 2 * cnt_col[x][mid]
    w = w_col[x][r] + w_col[x][l] - 2 * w_col[x][mid]
    
    print(abs(ans) + abs(cnt) * y - abs(w))

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 Queue:
    def __init__(self) -> None:
        self.items = deque()

    def is_empty(self) -> bool:
        return len(self.items) == 0

    def enqueue(self, item) -> None:
        self.items.appendleft(item)

    def insert(self, item) -> None:
        self.enqueue(item)

    def dequeue(self):
        return self.items.pop()

    def front(self):
        return self.items[-1]

    def pop(self) -> None:
        self.items.pop()

    def size(self) -> int:
        return len(self.items)


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 _bfs(self, root: int) -> None:
        que = Queue()
        que.enqueue(root)
        self.dep[root] = 0
        self.costs[root] = 0
        vis = [False] * self.N
        while que.is_empty() is False:
            v = que.dequeue()
            vis[v] = True
            nd = self.dep[v] + 1
            cs = self.costs[v]
            for i in range(len(self.to[v])):
                nv = self.to[v][i]
                if vis[nv]:
                    continue
                else:
                    que.enqueue(nv)
                    self.dep[nv] = nd
                    self.costs[nv] = cs + self.co[v][i]
                    self.par[nv][0] = v

    def init(self, root: int = 0) -> None:
        self.root = root
        self._bfs(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


    sk = []
    tr = [{} for _ in range(N+1)]
    vis = [False] * (N+1)

    def dfs2(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

        vis[v] = True

        for (to, co, col) in reversed(es[v]):
            if to == p:
                continue
            sk.append((to, v, col, co))
            tr[v][to] = (col, co)

        while len(sk) > 0:
            v, p, cl, cs = sk[-1]
            if len(es[v]) == 1:
                sk.pop()

            if vis[v] and p >= 0:
                cl, cs = tr[p][v]
                cnt[cl] -= 1
                sum_[cl] -= cs
                tr[p].pop(v)
                sk.pop()
                continue

            cnt[cl] += 1
            sum_[cl] += cs

            for (col, qid, coeff, dist) in qs[v]:
                x = -sum_[col]
                x += dist * cnt[col]
                ans[qid] += x * coeff

            vis[v] = True

            for (to, co, col) in reversed(es[v]):
                if to == p:
                    continue
                sk.append((to, v, col, co))
                tr[v][to] = (col, co)

            if len(tr[v]) == 0 and p >= 0:
                cl, cs = tr[p][v]
                cnt[cl] -= 1
                sum_[cl] -= cs
                tr[p].pop(v)

    dfs2(0)

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


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 Queue:
    def __init__(self) -> None:
        self.items = deque()

    def is_empty(self) -> bool:
        return len(self.items) == 0

    def enqueue(self, item) -> None:
        self.items.appendleft(item)

    def insert(self, item) -> None:
        self.enqueue(item)

    def dequeue(self):
        return self.items.pop()

    def front(self):
        return self.items[-1]

    def pop(self) -> None:
        self.items.pop()

    def size(self) -> int:
        return len(self.items)


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 _bfs(self, root: int) -> None:
        que = Queue()
        que.enqueue(root)
        self.dep[root] = 0
        self.costs[root] = 0
        vis = [False] * self.N
        while que.is_empty() is False:
            v = que.dequeue()
            vis[v] = True
            nd = self.dep[v] + 1
            cs = self.costs[v]
            for i in range(len(self.to[v])):
                nv = self.to[v][i]
                if vis[nv]:
                    continue
                else:
                    que.enqueue(nv)
                    self.dep[nv] = nd
                    self.costs[nv] = cs + self.co[v][i]
                    self.par[nv][0] = v

    def init(self, root: int = 0) -> None:
        self.root = root
        self._bfs(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
    '''

    sk = []
    tr = [{} for _ in range(N+1)]
    vis = [False] * (N+1)

    def dfs2(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

        vis[v] = True

        for (to, co, col) in reversed(es[v]):
            if to == p:
                continue
            sk.append((to, v, col, co))
            tr[v][to] = (col, co)

        while len(sk) > 0:
            v, p, cl, cs = sk[-1]
            if len(es[v]) == 1:
                sk.pop()

            if vis[v] and p >= 0:
                cl, cs = tr[p][v]
                cnt[cl] -= 1
                sum_[cl] -= cs
                tr[p].pop(v)
                sk.pop()
                continue

            cnt[cl] += 1
            sum_[cl] += cs

            for (col, qid, coeff, dist) in qs[v]:
                x = -sum_[col]
                x += dist * cnt[col]
                ans[qid] += x * coeff

            vis[v] = True

            for (to, co, col) in reversed(es[v]):
                if to == p:
                    continue
                sk.append((to, v, col, co))
                tr[v][to] = (col, co)

            if len(tr[v]) == 0 and p >= 0:
                cl, cs = tr[p][v]
                cnt[cl] -= 1
                sum_[cl] -= cs
                tr[p].pop(v)

    dfs2(0)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


class LCA:
    def __init__(self, N, L):
        self.L = L
        self.INF = (N, None)
        self.M0 = 2 ** (2 * N - 1).bit_length()
        self.data = [self.INF] * (2 * self.M0)
        self.D = [0] * N
        self.F = [0] * N
        self.S = []
        self.dist = [0] * N

        self.dfs1(0, 0, -1)
        for i, v in enumerate(self.S):
            self.data[self.M0 - 1 + i] = (self.D[v], i)
        for i in range(self.M0 - 2, -1, -1):
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def dfs1(self, v, d, p, pd=0):
        self.F[v] = len(self.S)
        self.D[v] = d
        self.S.append(v)
        self.dist[v] = pd
        for w, c, dis in self.L[v]:
            if w == p:
                continue
            self.dfs1(w, d + 1, v, pd + dis)
            self.S.append(v)

    def _query(self, a, b):
        yield self.INF
        a += self.M0
        b += self.M0
        while a < b:
            if b & 1:
                b -= 1
                yield self.data[b - 1]
            if a & 1:
                yield self.data[a - 1]
                a += 1
            a >>= 1
            b >>= 1

    def query(self, u, v):
        fu = self.F[u]
        fv = self.F[v]
        if fu > fv:
            fu, fv = fv, fu
        return self.S[min(self._query(fu, fv + 1))[1]]

    def dist(self, v):
        return self.dist[v]


def dfs2(L, v, p, QS, ans, CC, CD):
    for q, x, y, f in QS[v]:
        ans[q] += (y * CC[x] - CD[x]) * f

    for w, c, dis in L[v]:
        if w == p:
            continue
        CC[c] += 1
        CD[c] += dis
        dfs2(L, w, v, QS, ans, CC, CD)
        CC[c] -= 1
        CD[c] -= dis


def main():
    N, Q = read_values()
    L = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b, c, d = read_values()
        a -= 1
        b -= 1
        c -= 1
        L[a].append((b, c, d))
        L[b].append((a, c, d))

    g = LCA(N, L)

    QS = [[] for _ in range(N)]
    ans = [0] * Q
    for q in range(Q):
        x, y, u, v = read_values()
        x -= 1
        u -= 1
        v -= 1
        w = g.query(u, v)
        ans[q] = g.dist[u] + g.dist[v] - 2 * g.dist[w]
        QS[u].append((q, x, y, 1))
        QS[v].append((q, x, y, 1))
        QS[w].append((q, x, y, -2))

    CC = [0] * N
    CD = [0] * N
    dfs2(L, 0, -1, QS, ans, CC, CD)

    print("\n".join(map(str, ans)))


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 Queue:
    def __init__(self) -> None:
        self.items = deque()
    def is_empty(self) -> bool:
        return len(self.items) == 0
    def enqueue(self, item) -> None:
        self.items.appendleft(item)
    def insert(self, item) -> None:
        self.enqueue(item)
    def dequeue(self):
        return self.items.pop()
    def front(self):
        return self.items[-1]
    def pop(self) -> None:
        self.items.pop()
    def size(self) -> int:
        return len(self.items)

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 _bfs(self, root: int) -> None:
        que = Queue()
        que.enqueue(root)
        self.dep[root] = 0
        self.costs[root] = 0
        vis = [False] * self.N
        while que.is_empty() is False:
            v = que.dequeue()
            vis[v] = True
            nd = self.dep[v] + 1
            cs = self.costs[v]
            for i in range(len(self.to[v])):
                nv = self.to[v][i]
                if vis[nv]:
                    continue
                else:
                    que.enqueue(nv)
                    self.dep[nv] = nd
                    self.costs[nv] = cs + self.co[v][i]
                    self.par[nv][0] = v
    def init(self, root: int = 0) -> None:
        self.root = root
        self._bfs(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)

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


if __name__ == '__main__':
    main()