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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,Q = map(int,readline().split())
data = np.array(read().split(),np.int64)

ABCD = data[:4*N-4].reshape(-1,4).tolist()

graph = [[] for _ in range(N+1)]
for a,b,c,d in ABCD:
    graph[a].append((b,c,d))
    graph[b].append((a,c,d))

color = [0] * (N+1) 
length = [0] * (N+1) 

def EulerTour(graph,start=1):
    """
    1-indexed graph
    graphを破壊しているので場合によっては注意
    """
    V = len(graph)
    par = [0] * V
    depth = [0] * V; depth[start] = 0
    tour = [start]; st = [start]
    while st:
        x = st[-1]
        if not graph[x]:
            st.pop()
            tour.append(par[x])
            continue
        y,c,d = graph[x].pop()
        if y == par[x]:
            continue
        par[y] = x
        color[y] = c
        length[y] = d
        depth[y] = depth[x] + 1
        st.append(y)
        tour.append(y)
    return tour,depth

tour,depth = EulerTour(graph)

Ltour = len(tour)
tour_arr = np.array(tour)
depth_arr = np.array(depth)
tour_d = depth_arr[tour_arr]
idx = np.arange(len(depth))
idx[tour_arr] = np.arange(Ltour)


sp = np.empty((Ltour.bit_length(),Ltour),np.int32)
sp[0] = np.arange(Ltour)
for n in range(1,Ltour.bit_length()):
    prev,width = sp[n-1],1<<(n-1)
    x = prev[:-width]; y = prev[width:]
    condition = tour_d[x] > tour_d[y]
    sp[n] = prev
    sp[n,:-width][condition] = y[condition]

def LCA(A,B):
    AB = np.vstack([A,B]).T
    LR = idx[AB]
    LR.sort(axis=1)
    
    L = LR[:,0]; R = LR[:,1]
    x = R-L
    n = np.zeros_like(x) 
    for _ in range(20):
        x >>= 1
        n[x>0] += 1
    x = sp[n,L]; y = sp[n,R-(1<<n)+1]
    return np.where(tour_d[x] < tour_d[y], tour_arr[x], tour_arr[y])

XYUV = data[4*N-4:]
U = XYUV[2::4]; V = XYUV[3::4]
lca = LCA(U,V)

answer = [0] * Q
task = [[] for _ in range(N+1)]
for i,((x,y,u,v),w) in enumerate(zip(XYUV.reshape(-1,4).tolist(),lca.tolist())):
    
    task[u].append((x,y,1,i))
    task[v].append((x,y,1,i))
    task[w].append((x,y,-2,i))

color_cnt = [0] * N
color_sum = [0] * N
d = 0 

for fr,to in zip(tour,tour[1:]):
    d1 = depth[fr]; d2 = depth[to]
    if d1 > d2:
        
        for x,y,coef,i in task[fr]:
            answer[i] += coef * (d - color_sum[x] + color_cnt[x] * y)
    if d1 < d2:
        c = color[to]; l = length[to]
        color_cnt[c] += 1
        color_sum[c] += l; d += l
    else:
        c = color[fr]; l = length[fr]
        color_cnt[c] -= 1
        color_sum[c] -= l; d -= l

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,Q = map(int,readline().split())
data = np.array(read().split(),np.int64)

ABCD = data[:4*N-4].reshape(-1,4).tolist()

graph = [[] for _ in range(N+1)]
for a,b,c,d in ABCD:
    graph[a].append((b,c,d))
    graph[b].append((a,c,d))

color = [0] * (N+1) 
length = [0] * (N+1) 

def EulerTour(graph,start=1):
    """
    1-indexed graph
    graphを破壊しているので場合によっては注意
    """
    V = len(graph)
    par = [0] * V
    depth = [0] * V; depth[start] = 0
    tour = [start]; st = [start]
    while st:
        x = st[-1]
        if not graph[x]:
            st.pop()
            tour.append(par[x])
            continue
        y,c,d = graph[x].pop()
        if y == par[x]:
            continue
        par[y] = x
        color[y] = c
        length[y] = d
        depth[y] = depth[x] + 1
        st.append(y)
        tour.append(y)
    return tour,depth

tour,depth = EulerTour(graph)

Ltour = len(tour)
tour_arr = np.array(tour)
depth_arr = np.array(depth)
tour_d = depth_arr[tour_arr]
idx = np.arange(len(depth))
idx[tour_arr] = np.arange(Ltour)


sp = np.empty((Ltour.bit_length(),Ltour),np.int32)
sp[0] = np.arange(Ltour)
for n in range(1,Ltour.bit_length()):
    prev,width = sp[n-1],1<<(n-1)
    x = prev[:-width]; y = prev[width:]
    condition = tour_d[x] > tour_d[y]
    sp[n] = prev
    sp[n,:-width][condition] = y[condition]

def LCA(A,B):
    AB = np.vstack([A,B]).T
    LR = idx[AB]
    LR.sort(axis=1)
    
    L = LR[:,0]; R = LR[:,1]
    x = R-L
    n = np.zeros_like(x) 
    for _ in range(20):
        x >>= 1
        n[x>0] += 1
    x = sp[n,L]; y = sp[n,R-(1<<n)+1]
    return np.where(tour_d[x] < tour_d[y], tour_arr[x], tour_arr[y])

XYUV = data[4*N-4:]
U = XYUV[2::4]; V = XYUV[3::4]
lca = LCA(U,V)

answer = [0] * Q
task = [[] for _ in range(N+1)]
for i,((x,y,u,v),w) in enumerate(zip(XYUV.reshape(-1,4),lca)):
    
    task[u].append((x,y,1,i))
    task[v].append((x,y,1,i))
    task[w].append((x,y,-2,i))

color_cnt = [0] * N
color_sum = [0] * N
d = 0 

for fr,to in zip(tour,tour[1:]):
    d1 = depth[fr]; d2 = depth[to]
    if d1 > d2:
        
        for x,y,coef,i in task[fr]:
            answer[i] += coef * (d - color_sum[x] + color_cnt[x] * y)
    if d1 < d2:
        c = color[to]; l = length[to]
        color_cnt[c] += 1
        color_sum[c] += l; d += l
    else:
        c = color[fr]; l = length[fr]
        color_cnt[c] -= 1
        color_sum[c] -= l; d -= l

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,Q = map(int,readline().split())
data = np.array(read().split(),np.int64)

ABCD = data[:4*N-4].reshape(-1,4).tolist()

graph = [[] for _ in range(N+1)]
for a,b,c,d in ABCD:
    graph[a].append((b,c,d))
    graph[b].append((a,c,d))

color = [0] * (N+1) 
length = [0] * (N+1) 

def EulerTour(graph,start=1):
    """
    1-indexed graph
    graphを破壊しているので場合によっては注意
    """
    V = len(graph)
    par = [0] * V
    depth = [0] * V; depth[start] = 0
    tour = [start]; st = [start]
    while st:
        x = st[-1]
        if not graph[x]:
            st.pop()
            tour.append(par[x])
            continue
        y,c,d = graph[x].pop()
        if y == par[x]:
            continue
        par[y] = x
        color[y] = c
        length[y] = d
        depth[y] = depth[x] + 1
        st.append(y)
        tour.append(y)
    return tour,depth

tour,depth = EulerTour(graph)

Ltour = len(tour)
tour_arr = np.array(tour)
depth_arr = np.array(depth)
tour_d = depth_arr[tour_arr]
idx = np.arange(len(depth))
idx[tour_arr] = np.arange(Ltour)


sp = np.empty((Ltour.bit_length(),Ltour),np.int32)
sp[0] = np.arange(Ltour)
for n in range(1,Ltour.bit_length()):
    prev,width = sp[n-1],1<<(n-1)
    x = prev[:-width]; y = prev[width:]
    condition = tour_d[x] > tour_d[y]
    sp[n] = prev
    sp[n,:-width][condition] = y[condition]

def LCA(A,B):
    AB = np.vstack([A,B]).T
    LR = idx[AB]
    LR.sort(axis=1)
    
    L = LR[:,0]; R = LR[:,1]
    x = R-L
    n = np.zeros_like(x) 
    for _ in range(20):
        x >>= 1
        n[x>0] += 1
    x = sp[n,L]; y = sp[n,R-(1<<n)+1]
    return np.where(tour_d[x] < tour_d[y], tour_arr[x], tour_arr[y])

XYUV = data[4*N-4:]
U = XYUV[2::4]; V = XYUV[3::4]
lca = LCA(U,V)

answer = [0] * Q
task = [[] for _ in range(N+1)]
for i,((x,y,u,v),w) in enumerate(zip(XYUV.reshape(-1,4),lca)):
    
    task[u].append((x,y,1,i))
    task[v].append((x,y,1,i))
    task[w].append((x,y,-2,i))

color_cnt = [0] * N
color_sum = [0] * N
d = 0 

for fr,to in zip(tour,tour[1:]):
    d1 = depth[fr]; d2 = depth[to]
    if d1 > d2:
        
        for x,y,coef,i in task[fr]:
            answer[i] += coef * (d - color_sum[x] + color_cnt[x] * y)
    if d1 < d2:
        c = color[to]; l = length[to]
        color_cnt[c] += 1
        color_sum[c] += l; d += l
    else:
        c = color[fr]; l = length[fr]
        color_cnt[c] -= 1
        color_sum[c] -= l; d -= l

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

Solution (Python):

import sys
from collections import defaultdict
readline = sys.stdin.readline
N, Q = map(int, readline().split())

vs = set()
def dfs_w(v, d):

    S, F, depth, depthh = [], [None]+[0]*N, [-1] + [0]*N, [0] + [0]*N
    iin = [[(0, 0, 0)] for _ in range(N)]

    stack, path = [(1, 0, 0)], [0]
    while True:
        if len(stack) == 0:
            break
        v, cc, dpd = stack.pop()
        if v > 0:
            parent = path[-1]
            path.append(v)
            vs.add(v)

            F[v] = len(S)
            depth[v], depthh[v] = depth[parent] + 1, depthh[parent] + dpd
            iin[cc].append((iin[cc][-1][0]+1, iin[cc][-1][1]+dpd, len(S)))

            S.append(v)
            for u, ucc, udpd in d[v]:
                if u in vs:
                    continue
                stack += [(-v, ucc, udpd), (u, ucc, udpd)]
        else:
            path.pop()
            iin[cc].append((iin[cc][-1][0]-1, iin[cc][-1][1]-dpd, len(S)))
            S.append(v)

    return S, F, depth, depthh, iin

class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

def bsearch(target, min_i, max_i, func):
    
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

def process():
    G = [set() for _ in range(N+1)]
    for _ in range(N-1):
        a, b, c, d = map(int, readline().split())
        G[a].add((b,c,d))
        G[b].add((a,c,d))

    S, F, depth, depthh, iin = dfs_w(1, G)

    stree = SegTree([(depth[abs(v)], i) for i, v in enumerate(S)], len(S), (N, None), min)
    for _ in range(Q):
        x, y, u, v = map(int, readline().split())
        fu, fv = sorted([F[u], F[v]])
        cc = abs(S[stree.query(fu, fv+1)[1]])

        (fuy, fuv, _), (fvy, fvv, _), (fccy, fccv, _) = [iin[x][bsearch(index, 0, len(iin[x])-1, lambda j: iin[x][j][2])] for index in [fu, fv, F[cc]]]
        r = depthh[u] + depthh[v] - 2*depthh[cc] + (fuy + fvy - 2 * fccy) * y - (fuv + fvv - 2 * fccv)
        print(r)

if __name__ == '__main__':
    process()

Solution (Python):

import sys
from collections import defaultdict
readline = sys.stdin.readline
N, Q = map(int, readline().split())

vs = set()
def dfs_w(v, d):

    S, F, depth, depthh = [], [None]+[0]*N, [-1] + [0]*N, [0] + [0]*N
    mmn, msn, iin = [[0] for _ in range(N)], [[0] for _ in range(N)], [[0] for _ in range(N)]

    pvs, stack, path = set(), [(1, 0, 0)], [0]
    
    while True:
        if len(stack) == 0:
            break
        v, cc, dpd = stack.pop()
        if v > 0:
            parent = path[-1]
            path.append(v)
            pvs.add(v)
            vs.add(v)

            F[v] = len(S)
            depth[v], depthh[v] = depth[parent] + 1, depthh[parent] + dpd
            mmn[cc].append(mmn[cc][-1]+1)
            msn[cc].append(msn[cc][-1]+dpd)
            iin[cc].append(len(S))

            S.append(v)
            for u, ucc, udpd in d[v]:
                if u in pvs:
                    continue
                    
                    for i, c in enumerate(path):
                        if c == u:
                            break
                    return path[i+1:]  + [u]
                if u in vs:
                    continue
                stack += [(-v, ucc, udpd), (u, ucc, udpd)]
        else:
            pvs.remove(path[-1])
            path.pop()
            mmn[cc].append(mmn[cc][-1]-1)
            msn[cc].append(msn[cc][-1]-dpd)
            iin[cc].append(len(S))
            S.append(v)

    return S, F, depth, depthh, mmn, msn, iin

class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

def bsearch(ll, target, min_i, max_i):
    
    if ll[max_i] <= target:
        return max_i
    if target < ll[min_i]:
        return None
    index = len(ll)//2
    while True:
        if ll[index] <= target:
            if target < ll[index+1]:
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

def process():
    G = [set() for _ in range(N+1)]
    for _ in range(N-1):
        a, b, c, d = map(int, readline().split())
        G[a].add((b,c,d))
        G[b].add((a,c,d))

    S, F, depth, depthh, mmn, msn, iin = dfs_w(1, G)

    stree = SegTree([(depth[abs(v)], i) for i, v in enumerate(S)], len(S), (N, None), min)
    for _ in range(Q):
        x, y, u, v = map(int, readline().split())
        fu, fv = sorted([F[u], F[v]])
        cc = abs(S[stree.query(fu, fv+1)[1]])

        r = depthh[u] + depthh[v] - 2*depthh[cc]
        index = bsearch(iin[x], F[u], 0, len(iin[x])-1)
        r += mmn[x][index] * y - msn[x][index]
        index = bsearch(iin[x], F[v], 0, len(iin[x])-1)
        r += mmn[x][index] * y - msn[x][index]

        index = bsearch(iin[x], F[cc], 0, len(iin[x])-1)
        r -= 2 * (mmn[x][index] * y - msn[x][index])
        print(r)

if __name__ == '__main__':
    process()

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.readline
N, Q = map(int, readline().split())

class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

def bsearch(ll, target, min_i, max_i):
    
    if ll[max_i] <= target:
        return max_i
    if target < ll[min_i]:
        return None
    index = len(ll)//2
    while True:
        if ll[index] <= target:
            if target < ll[index+1]:
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

def process():

    G = [[] for _ in range(N+1)]
    dp = {}
    for v in range(N-1):
        a, b, c, d = map(int, readline().split())
        G[a].append(b)
        G[b].append(a)
        dp[(min(a,b), max(a,b))] = c, d

    S = [1]*(2*N+1)
    F = [0]*(N+1)
    stack = []
    for u in G[1]:
        stack += [-1, u]

    visited = set([1])
    depth, depthh = [0]*(N+1), [0]*(N+1)
    mmn = [[0] for _ in range(N)]
    msn = [[0] for _ in range(N)]
    iin = [[0] for _ in range(N)]
    path = [1]
    ii = 0

    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        ii += 1
        if v > 0:
            visited.add(v)
            parent = path[-1]
            path.append(v)
            

            cc, dpd = dp[(min(v,parent), max(v,parent))]
            F[v], S[ii] = ii, v
            depth[v], depthh[v] = depth[parent] + 1, depthh[parent] + dpd

            mmn[cc].append(mmn[cc][-1]+1)
            msn[cc].append(msn[cc][-1]+dpd)
            iin[cc].append(ii)

            for u in G[v]:
                if u in visited:
                    continue
                stack += [-v, u]
        else:
            child = path.pop()
            cc, dpd = dp[(min(-v, child), max(-v, child))]
            S[ii] = v
            mmn[cc].append(mmn[cc][-1]-1)
            iin[cc].append(ii)
            msn[cc].append(msn[cc][-1]-dpd)
    




    stree = SegTree([(depth[abs(v)], i) for i, v in enumerate(S)], len(S), (N, None), min)

    for q in range(Q):
        x, y, u, v = map(int, readline().split())
        fu = F[u]; fv = F[v]
        if fu > fv:
            fu, fv = fv, fu

        cc = abs(S[stree.query(fu, fv+1)[1]])

        ll, mm, ms = iin[x], mmn[x], msn[x]
        uvcs = []
        for target_i in [F[u], F[v], F[cc]]:
            index = bsearch(ll, target_i, 0, len(ll)-1)
            uvcs.append((mm[index], ms[index]))
        diff = (uvcs[0][0] + uvcs[1][0] - 2 * uvcs[2][0]) * y - (uvcs[0][1] + uvcs[1][1] - 2 * uvcs[2][1])
        print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)


if __name__ == '__main__':
    process()

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.readline
N, Q = map(int, readline().split())

class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

def process():

    G = [[] for _ in range(N+1)]
    dp = {}
    for v in range(N-1):
        a, b, c, d = map(int, readline().split())
        G[a].append(b)
        G[b].append(a)
        dp[(min(a,b), max(a,b))] = c, d

    S = [1]*(2*N+1)
    F = [0]*(N+1)
    stack = []
    for u in G[1]:
        stack += [-1, u]

    visited = set([1])
    depth, depthh = [0]*(N+1), [0]*(N+1)
    mmn = [[0] for _ in range(N)]
    msn = [[0] for _ in range(N)]
    iin = [[] for _ in range(N)]
    path = [1]
    ii = 0

    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        ii += 1
        if v > 0:
            visited.add(v)
            parent = path[-1]
            path.append(v)
            

            cc, dpd = dp[(min(v,parent), max(v,parent))]
            F[v], S[ii] = ii, v
            depth[v], depthh[v] = depth[parent] + 1, depthh[parent] + dpd

            mmn[cc].append(mmn[cc][-1]+1)
            msn[cc].append(msn[cc][-1]+dpd)
            iin[cc].append(ii)

            for u in G[v]:
                if u in visited:
                    continue
                stack += [-v, u]
        else:
            child = path.pop()
            cc, dpd = dp[(min(-v, child), max(-v, child))]
            S[ii] = v
            mmn[cc].append(mmn[cc][-1]-1)
            iin[cc].append(ii)
            msn[cc].append(msn[cc][-1]-dpd)
    




    stree = SegTree([(depth[abs(v)], i) for i, v in enumerate(S)], len(S), (N, None), min)

    for q in range(Q):
        x, y, u, v = map(int, readline().split())
        fu = F[u]; fv = F[v]
        if fu > fv:
            fu, fv = fv, fu

        cc = abs(S[stree.query(fu, fv+1)[1]])

        ll, mm, ms = iin[x], mmn[x], msn[x]
        uvcs = []
        for target_i in [F[u], F[v], F[cc]]:
            if not ll:
                uvcs.append((0,0))
                continue
            ind, lw, hw =  (len(ll)-1)//2, 0, len(ll)-1
            if target_i < ll[0] or target_i >= ll[-1]:
                uvcs.append((0,0))
                continue
            while True:
                if ll[ind] <= target_i:
                    if target_i < ll[ind+1]:
                        uvcs.append((mm[ind+1], ms[ind+1]))
                        break
                    ind, lw = (ind+1 + hw)//2, ind+1
                    continue
                ind, hw = (ind-1 + lw)//2, ind-1
        diff = (uvcs[0][0] + uvcs[1][0] - 2 * uvcs[2][0]) * y - (uvcs[0][1] + uvcs[1][1] - 2 * uvcs[2][1])
        print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)


if __name__ == '__main__':
    process()

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.readline
N, Q = map(int, readline().split())

class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

def process():

    G = [[] for _ in range(N+1)]
    dp = {}
    for v in range(N-1):
        a, b, c, d = map(int, readline().split())
        G[a].append(b)
        G[b].append(a)
        dp[(min(a,b), max(a,b))] = c, d

    S = [1]*(2*N+1)
    F = [0]*(N+1)
    stack = []
    for u in G[1][::-1]:
        stack += [-1, u]

    visited = set([1])
    depth, depthh = [0]*(N+1), [0]*(N+1)
    mmn = [[0] for _ in range(N)]
    msn = [[0] for _ in range(N)]
    iin = [[] for _ in range(N)]
    path = [1]
    ii = 0

    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        ii += 1
        if v > 0:
            visited.add(v)
            parent = path[-1]
            path.append(v)
            

            cc, dpd = dp[(min(v,parent), max(v,parent))]
            F[v], S[ii] = ii, v
            depth[v], depthh[v] = depth[parent] + 1, depthh[parent] + dpd

            mmn[cc].append(mmn[cc][-1]+1)
            msn[cc].append(msn[cc][-1]+dpd)
            iin[cc].append(ii)

            for u in G[v][::-1]:
                if u in visited:
                    continue
                stack += [-v, u]
        else:
            child = path.pop()
            cc, dpd = dp[(min(-v, child), max(-v, child))]
            mmn[cc].append(mmn[cc][-1]-1)
            iin[cc].append(ii)
            msn[cc].append(msn[cc][-1]-dpd)
            S[ii] = v
    




    stree = SegTree([(depth[abs(v)], i) for i, v in enumerate(S)], len(S), (N, None), min)

    for q in range(Q):
        x, y, u, v = map(int, readline().split())
        fu = F[u]; fv = F[v]
        if fu > fv:
            fu, fv = fv, fu

        cc = abs(S[stree.query(fu, fv+1)[1]])

        if len(mmn[x])-1 == 0:
            diff = 0
        else:
            ll, mm, ms, lncc = iin[x], mmn[x], msn[x], len(mmn[x])-2
            uvcs = []
            for target_i in [F[u], F[v], F[cc]]:
                ind, lw, hw =  (len(mmn[x])-2)//2, 0, len(mmn[x]) - 2
                if target_i < ll[0] or target_i >= ll[lncc]:
                    uvcs.append((0,0))
                else:
                    while True:
                        if ll[ind] <= target_i:
                            if target_i < ll[ind+1]:
                                uvcs.append((mm[ind+1], ms[ind+1]))
                                break
                            ind, lw = (ind+1 + hw)//2, ind+1
                            continue
                        ind, hw = (ind-1 + lw)//2, ind-1
            diff = (uvcs[0][0] + uvcs[1][0] - 2 * uvcs[2][0]) * y - (uvcs[0][1] + uvcs[1][1] - 2 * uvcs[2][1])
        print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)


if __name__ == '__main__':
    process()