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


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 eulertour(G, root=0):
    n = len(G)
    euler = []
    depth = [-1] * n
    depth[root] = 0
    que = deque([root])
    que2 = deque()
    visited = [0] * n
    while que:
        u = que.pop()
        euler += [(depth[u], u)]
        if visited[u]:
            continue
        for v in G[u]:
            if visited[v]:
                que += [v]
            else:
                depth[v] = depth[u] + 1
                que2 += [v]
        que.extend(que2)
        que2 = deque()
        visited[u] = 1
    return euler

dist = 0
color_len = [0] * n
color_cnt = [0] * n
ans = [0] * q
euler = eulertour(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')

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


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 Eulertour(G, root=0):
    n = len(G)
    Euler = []
    Depth = [-1] * n
    Depth[root] = 0
    que = deque([root])
    que2 = deque()
    Visited = [0] * n
    while que:
        fr=que.pop()
        Euler.append((Depth[fr],fr))
        if Visited[fr]:
            continue
        for to in G[fr]:
            if Visited[to]:
                que.append(to)
            else:
                Depth[to]=Depth[fr]+1
                que2.append(to)
        que.extend(que2)
        que2=deque()
        Visited[fr]=True
    return Euler

dist = 0
color_len = [0] * n
color_cnt = [0] * n
ans = [0] * q
euler = Eulertour(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')

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


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 Eulertour(Edges,n,root=0):
    Euler=[]
    Depth=[-1]*n
    Depth[root]=0
    que=deque([root])
    que2=deque()
    Visited=[False]*n
    while que:
        fr=que.pop()
        Euler.append((Depth[fr],fr))
        if Visited[fr]:
            continue
        for to in Edges[fr]:
            if Visited[to]:
                que.append(to)
            else:
                Depth[to]=Depth[fr]+1
                que2.append(to)
        que.extend(que2)
        que2=deque()
        Visited[fr]=True
    return Euler

dist = 0
color_len = [0] * n
color_cnt = [0] * n
ans = [0] * q
euler = Eulertour(edge_dict, n)
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')

Solution (Python):

class Accumulate:
    def __init__(self,lst): 
        from itertools import accumulate
        self.acc = list(accumulate([0]+lst))

    def query(self,u,v): 
        return self.acc[v+1] - self.acc[u]



"""
オイラーツアー（辺属性）　http://beet-aizu.hatenablog.com/entry/2019/07/08/174727
部分木に関するクエリを処理

ds[v] = v は行きがけで ls[v]番目の頂点
us[v] = v の帰りがけ時、すでに行きがけに確認した頂点の個数

v の部分木に属する頂点は [ls[v],rs[v]) までの頂点
"""

class Euler_tour_edge:
    """
    parent: ダブリングテーブル
    depth: 元の深さ
    """
    def __init__(self,g,root): 

        def dfs(root):
            n = len(g)
            parent = self.parent[0]
            q = [root]
            cnt = 0
            q_wt = [0]; q_col = [0] 
            data_wt = []; data_col = [] 
            while q:
                v = q.pop()
                if v >= 0: 
                    q.append(-v-1)
                    self.ds[v] = cnt; cnt += 1
                    if v != root: 
                        data_wt.append(q_wt[-1]); data_col.append(q_col[-1]);
                    for c,col,wt in g[v]:
                        if c != parent[v]:
                            parent[c] = v
                            self.depth[c] = self.depth[v] + 1
                            q.append(c);
                            q_wt.append(wt); q_col.append(col) 
                else: 
                    
                    data_wt.append(-q_wt.pop()); data_col.append(q_col.pop())
                    self.us[-v-1] = cnt; cnt += 1
            data_wt.pop(); data_col.pop() 
            
            
            return data_wt, data_col        
            
        def doubling_make_table(N,logN,Table):
            for i in range(1,logN):
                for j, Tiij in enumerate(Table[i-1]):
                    if Tiij != -1:
                        Table[i][j] = Table[i-1][Tiij]

        N = len(g)
        self.logN = len(bin(N))-2
        self.parent = [[-1]*N for _ in range(self.logN)]
        self.depth = [0]*(N) 
        self.ds = [0]*(n)
        self.us = [0]*(n)
        data_wt,data_col = dfs(root)
        doubling_make_table(N, self.logN, self.parent) 

        
        
        self.wt_acc = Accumulate(data_wt)
        self.color_id = [[] for _ in range(n)]
        self.color_num = [[0] for _ in range(n)]
        self.color_acc = [[0] for _ in range(n)]
        for i,(c,w) in enumerate(zip(data_col,data_wt)):
            self.color_id[c].append(i)
            self.color_num[c].append(self.color_num[c][-1] + (1 if w>0 else -1))
            self.color_acc[c].append(self.color_acc[c][-1]+w)
        
        
        
    
            
    def get_path_wt(self,col,wt,u,v):
        p = self.getLCA(u,v)
        
        res = self.wt_acc.query(self.ds[p],self.ds[u]-1) + self.wt_acc.query(self.ds[p],self.ds[v]-1)
        
        cid  = self.color_id[col] 
        cnum = self.color_num[col]
        cacc = self.color_acc[col]
        if cid:
            i = bisect_left(cid,self.ds[u])
            res += (-cacc[i] + wt*cnum[i])
            i = bisect_left(cid,self.ds[v])
            res += (-cacc[i] + wt*cnum[i])
            i = bisect_left(cid,self.ds[p])
            res -= 2*(-cacc[i] + wt*cnum[i])
        return res
        

    def getLCA(self,u,v): 
        if self.depth[u] > self.depth[v]: u,v = v,u 
        dd = self.depth[v] - self.depth[u]
        for k in range(self.logN-1,-1,-1):
            if (dd >> k) & 1: v = self.parent[k][v]
        if u == v: return u;
        for k in range(self.logN-1,-1,-1):
            if self.parent[k][u] != self.parent[k][v]:
                u,v = self.parent[k][u], self.parent[k][v]
        return self.parent[0][u];

    def getdepth(self,u): 
        return self.depth[u]







import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines




n,m = [int(i) for i in readline().split()]
abcd = map(int,read().split())

g = [[] for _ in range(n)]

for i in range(n-1):
    a,b,c,d = next(abcd),next(abcd),next(abcd),next(abcd)
    a -= 1; b -= 1
    
    g[a].append([b,c,d])
    g[b].append([a,c,d])



E = Euler_tour_edge(g,0)

ans = [0]*m

from bisect import bisect_left

for i in range(m):
    c,w,u,v = next(abcd),next(abcd),next(abcd),next(abcd)
    u -= 1; v -= 1
    
    ans[i] = E.get_path_wt(c,w,u,v)

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

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


class SegmentTree1():
    """
    1-indexed Segment Tree
    """
    def __init__(self, n_, ele_id, operation_func):
        self.n = 1 << (n_ - 1).bit_length()  
        self.data = [ele_id] * (2 * self.n)  
        self.ele_id = ele_id  
        self.operation_func = operation_func  

    def __getitem__(self, idx):
        return self.data[idx + self.n]

    def build(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n] = data_init[i]
        for i in range(self.n - 1, 0, -1):
            self.data[i] = self.operation_func(self.data[2 * i],
                                               self.data[2 * i + 1])

    def update(self, idx, x):
        
        idx += self.n
        self.data[idx] = x
        while idx > 1:
            idx = idx >> 1
            self.data[idx] = self.operation_func(self.data[2 * idx],
                                                 self.data[2 * idx + 1])

    def query(self, l, r):
        
        l += self.n
        r += self.n
        ret = self.ele_id
        while l < r:
            if l & 1:  
                ret = self.operation_func(ret, self.data[l])
                l += 1
            if r & 1:  
                r -= 1
                ret = self.operation_func(ret, self.data[r])
            
            l = l >> 1
            r = r >> 1
        return ret


class Tree():
    def __init__(self, n, graph, v_root):
        self.n = n  
        self.graph = graph  
        self.v_root = v_root  

        
        self.first_idx = [2 * self.n] * self.n
        self.euler_tour = []
        self.euler_depth_topo = []
        self.euler_depth_real = []
        self.euler_tour_dfs(self.v_root, -1, 0, 0)

        depth_list = [(di, i) for i, di in enumerate(self.euler_depth_topo)]
        INF = (2 * self.n, -1)
        operation_func = lambda a, b: a if a[0] < b[0] else b
        self.st_rmq = SegmentTree1(2 * self.n - 1, INF, operation_func)
        self.st_rmq.build(depth_list)

    def euler_tour_dfs(self, v, v_par, depth_topo, depth_real):
        self.first_idx[v] = len(self.euler_tour)
        self.euler_tour.append(v)
        self.euler_depth_topo.append(depth_topo)
        self.euler_depth_real.append(depth_real)
        for v_next, c, d in self.graph[v]:
            if v_next == v_par:
                continue
            self.euler_tour_dfs(v_next, v, depth_topo + 1, depth_real + d)
            self.euler_tour.append(v)
            self.euler_depth_topo.append(depth_topo)
            self.euler_depth_real.append(depth_real)

    def depth_topo(self, v):
        return self.euler_depth_topo[self.first_idx[v]]

    def depth_real(self, v):
        return self.euler_depth_real[self.first_idx[v]]

    def lca(self, u, v):
        u_idx, v_idx = self.first_idx[u], self.first_idx[v]
        if u_idx > v_idx:
            u_idx, v_idx = v_idx, u_idx
        _, idx = self.st_rmq.query(u_idx, v_idx + 1)
        return self.euler_tour[idx]

    def dist(self, u, v):
        lca_uv = self.lca(u, v)
        return self.depth(u) + self.depth(v) - 2 * self.depth(lca_uv)


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

tree = Tree(n, graph, 0)

query = []
memo = [set() for i in range(n)]
for _ in range(q):
    x, y, u, v = map(int, input().split())
    u -= 1
    v -= 1
    lca_uv = tree.lca(u, v)
    memo[u].add(x)
    memo[v].add(x)
    memo[lca_uv].add(x)

    query.append((x, y, u, v, lca_uv))

n_color = [0] * n
d_color = [0] * n
n_color_memo = {}
d_color_memo = {}


def dfs(v, v_par, depth):
    for c in memo[v]:
        n_color_memo[(v, c)] = n_color[c]
        d_color_memo[(v, c)] = d_color[c]

    for v_next, c, d in graph[v]:
        if v_next == v_par:
            continue
        n_color[c] += 1
        d_color[c] += d
        dfs(v_next, v, depth + d)
        n_color[c] -= 1
        d_color[c] -= d


dfs(0, -1, 0)

for x, y, u, v, lca in query:
    depth_u = tree.depth_real(u)
    depth_u += -d_color_memo[(u, x)] + y * n_color_memo[(u, x)]
    depth_v = tree.depth_real(v)
    depth_v += -d_color_memo[(v, x)] + y * n_color_memo[(v, x)]
    depth_lca = tree.depth_real(lca)
    depth_lca += -d_color_memo[(lca, x)] + y * n_color_memo[(lca, x)]

    ans = depth_u + depth_v - 2 * depth_lca
    print(ans)

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


class SegmentTree1():
    """
    1-indexed Segment Tree
    """
    def __init__(self, n_, ele_id, operation_func):
        self.n = 1 << (n_ - 1).bit_length()  
        self.data = [ele_id] * (2 * self.n)  
        self.ele_id = ele_id  
        self.operation_func = operation_func  

    def __getitem__(self, idx):
        return self.data[idx + self.n]

    def build(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n] = data_init[i]
        for i in range(self.n - 1, 0, -1):
            self.data[i] = self.operation_func(self.data[2 * i],
                                               self.data[2 * i + 1])

    def update(self, idx, x):
        
        idx += self.n
        self.data[idx] = x
        while idx > 1:
            idx = idx >> 1
            self.data[idx] = self.operation_func(self.data[2 * idx],
                                                 self.data[2 * idx + 1])

    def query(self, l, r):
        
        l += self.n
        r += self.n
        ret = self.ele_id
        while l < r:
            if l & 1:  
                ret = self.operation_func(ret, self.data[l])
                l += 1
            if r & 1:  
                r -= 1
                ret = self.operation_func(ret, self.data[r])
            
            l = l >> 1
            r = r >> 1
        return ret


class Tree():
    def __init__(self, n, graph, v_root):
        self.n = n  
        self.graph = graph  
        self.v_root = v_root  

        
        self.first_idx = [2 * self.n] * self.n
        self.euler_tour = []
        self.euler_depth_topo = []
        self.euler_depth_real = []
        self.cs_color = [0] * self.n
        self.euler_tour_dfs(self.v_root, -1, 0, 0)

        depth_list = [(di, i) for i, di in enumerate(self.euler_depth_topo)]
        INF = (2 * self.n, -1)
        operation_func = lambda a, b: a if a[0] < b[0] else b
        self.st_rmq = SegmentTree1(2 * self.n - 1, INF, operation_func)
        self.st_rmq.build(depth_list)

    def euler_tour_dfs(self, v, v_par, depth_topo, depth_real):
        self.first_idx[v] = len(self.euler_tour)
        self.euler_tour.append(v)
        self.euler_depth_topo.append(depth_topo)
        self.euler_depth_real.append(depth_real)
        for v_next, c, d in self.graph[v]:
            if v_next == v_par:
                continue
            self.euler_tour_dfs(v_next, v, depth_topo + 1, depth_real + d)
            self.euler_tour.append(v)
            self.euler_depth_topo.append(depth_topo)
            self.euler_depth_real.append(depth_real)

    def depth_topo(self, v):
        return self.euler_depth_topo[self.first_idx[v]]

    def depth_real(self, v):
        return self.euler_depth_real[self.first_idx[v]]

    def lca(self, u, v):
        u_idx, v_idx = self.first_idx[u], self.first_idx[v]
        if u_idx > v_idx:
            u_idx, v_idx = v_idx, u_idx
        _, idx = self.st_rmq.query(u_idx, v_idx + 1)
        return self.euler_tour[idx]

    def dist(self, u, v):
        lca_uv = self.lca(u, v)
        return self.depth(u) + self.depth(v) - 2 * self.depth(lca_uv)


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

tree = Tree(n, graph, 0)

query = []
memo = [set() for i in range(n)]
for _ in range(q):
    x, y, u, v = map(int, input().split())
    u -= 1
    v -= 1
    lca_uv = tree.lca(u, v)
    memo[u].add(x)
    memo[v].add(x)
    memo[lca_uv].add(x)

    query.append((x, y, u, v, lca_uv))

n_color = [0] * n
d_color = [0] * n
n_color_memo = {}
d_color_memo = {}


def dfs(v, v_par, depth):
    for c in memo[v]:
        n_color_memo[(v, c)] = n_color[c]
        d_color_memo[(v, c)] = d_color[c]

    for v_next, c, d in graph[v]:
        if v_next == v_par:
            continue
        n_color[c] += 1
        d_color[c] += d
        dfs(v_next, v, depth + d)
        n_color[c] -= 1
        d_color[c] -= d


dfs(0, -1, 0)

for x, y, u, v, lca in query:
    depth_u = tree.depth_real(u)
    depth_u += -d_color_memo[(u, x)] + y * n_color_memo[(u, x)]
    depth_v = tree.depth_real(v)
    depth_v += -d_color_memo[(v, x)] + y * n_color_memo[(v, x)]
    depth_lca = tree.depth_real(lca)
    depth_lca += -d_color_memo[(lca, x)] + y * n_color_memo[(lca, x)]

    ans = depth_u + depth_v - 2 * depth_lca
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class LCA(object):
    def __init__(self,E,root=0):
        self.__n=len(E)
        self.__E=E
        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.__E[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&(1<<i)): v=self.__parents[i][v]
        if(v==u): return v
        for i in range(self.__logn-1,-1,-1):
            pu,pv=self.__parents[i][u],self.__parents[i][v]
            if(pu!=pv): u,v=pu,pv
        return self.__parents[0][u]

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

    
    Qs=[[] 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)
        Qs[u].append((i,x,y,1))
        Qs[v].append((i,x,y,1))
        Qs[c].append((i,x,y,-2))

    
    ans=[0]*q
    S=[[0,0] for _ in range(n)] 
    def dfs(v,p):
        
        
        for idx,col,mag,coef in Qs[v]:
            x=G.dist[v]
            x-=S[col][1]
            x+=mag*S[col][0]
            ans[idx]+=x*coef
        
        for nv,col,d in E[v]:
            if(nv==p): continue
            S[col][0]+=1
            S[col][1]+=d
            dfs(nv,v)
            S[col][0]-=1
            S[col][1]-=d
    dfs(0,-1)
    print(*ans,sep="\n")
resolve()