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 collections import defaultdict
readline = sys.stdin.readline
 
N, Q = map(int, readline().split())


def process():
    INF = (N, None)
    M = 2*N
    M0 = 2**(M-1).bit_length()
    data = [INF]*(2*M0)

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

    S = [0]*(2*N)
    F = [0]*(2*N)
    stack = [0] + G[0][::-1]
    visited = set([0])
    depth = [0]*N
    depthh = [0]*N
    mmn = [[0] for _ in range(N)]
    msn = [[0] for _ in range(N)]
    iin = [[] for _ in range(N)]
    ccs = [0]*N
    path = [0]
    ii = 0
    d = 0
    dd = 0

    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v in visited:
            continue
        ii += 1
        if v >=0:
            visited.add(v)
            cc, dpd = dp[(min(v,path[-1]), max(v,path[-1]))]
            F[v] = ii
            S[ii] = v
            d += 1
            dd += dpd
            depth[v] = d
            depthh[v] = dd
            ccs[v] = cc

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

            path.append(v)
            stack += [-v] + G[v][::-1]
        else:
            cc, dpd = dp[(min(path[-1], path[-2]), max(path[-1],path[-2]))]
            dd -= dpd
            mmn[cc].append(mmn[cc][-1]-1)
            iin[cc].append(-path[-1])
            msn[cc].append(msn[cc][-1]-dpd)
            F[-path[-1]] = ii
            path.pop()
            S[ii] = path[-1]
            d -= 1
    
    for i, v in enumerate(S):
        data[M0-1+i] = (depth[v], i)
    for i in range(M0-2, -1, -1):
        data[i] = min(data[2*i+1], data[2*i+2])

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

        minx = INF
        a, b = fu, fv+1
        a += M0; b += M0
        while a < b:
            if b & 1:
                b -= 1
                minx = min(minx, data[b-1])
            if a & 1:
                minx = min(minx, data[a-1])
                a += 1
            a >>= 1; b >>= 1
        cc = S[minx[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 < F[ll[0]] or target_i >= F[ll[lncc]]:
                    uvcs.append((0,0))
                else:
                    while True:
                        if F[ll[ind]] <= target_i:
                            if target_i < F[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
input=sys.stdin.readline
from collections import deque
class LCA:
    def __init__(self,v,Edges,root=0):
        self.v=v
        self.Edges=Edges
        self.maxLog=18
        self.Parent=[[-1]*v for _ in range(self.maxLog+1)]
        self.Depth=[0]*v
        self.__bfs(root)
        for i in range(self.maxLog):
            for j in range(v):
                if self.Parent[i][j]!=-1:
                    self.Parent[i+1][j]=self.Parent[i][self.Parent[i][j]]
    def __bfs(self,root):
        Visited=[False]*self.v
        Visited[root]=True
        q=deque([root])
        while q:
            fr=q.pop()
            for to in self.Edges[fr]:
                if Visited[to]:
                    continue
                self.Parent[0][to]=fr
                self.Depth[to]=self.Depth[fr]+1
                Visited[to]=True
                q.append(to)
    def lca(self,a,b):
        if self.Depth[a]>self.Depth[b]:
            a,b=b,a
        for i in range(self.maxLog):
            if (self.Depth[b]-self.Depth[a])&(1<<i):
                b=self.Parent[i][b]
        if a==b:
            return b
        for i in reversed(range(self.maxLog-1)):
            if self.Parent[i][a]!=self.Parent[i][b]:
                a=self.Parent[i][a]
                b=self.Parent[i][b]
        return self.Parent[0][a]

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

n,q=map(int,input().split())
Edgedict=[dict() for _ in range(n)]
for _ in range(n-1):
    a,b,c,d=map(int,input().split())
    a-=1; b-=1
    Edgedict[a][b]=(c,d)
    Edgedict[b][a]=(c,d)
Queries=[tuple(map(int,input().split())) for _ in range(q)]
Euler=Eulertour(Edgedict,n)
lca=LCA(n,Edgedict)
Q=[[] for _ in range(n)]
for i,(x,y,u,v) in enumerate(Queries):
    u-=1; v-=1
    Q[u].append([i,x,y,True])
    Q[v].append([i,x,y,True])
    Q[lca.lca(u,v)].append([i,x,y,False])
Ans=[0]*q
dist=0
C_len=[0]*n
C_cnt=[0]*n
for i in range(1,len(Euler)):
    idx=Euler[i][1]
    c,l=Edgedict[Euler[i-1][1]][idx]
    if Euler[i-1][0]<Euler[i][0]:
        dist+=l
        C_len[c]+=l
        C_cnt[c]+=1
        for q_idx,x,y,flag in Q[idx]:
            if flag:
                Ans[q_idx]+=dist+C_cnt[x]*y-C_len[x]
            else:
                Ans[q_idx]-=(dist+C_cnt[x]*y-C_len[x])*2
    else:
        dist-=l
        C_len[c]-=l
        C_cnt[c]-=1
print(*Ans,sep='\n')

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
class LCA:
    def __init__(self,V,edges,depth,parent,root=0):
        self.edges=edges
        self.maxLog=18
        self.parent=[[-1]*V for _ in range(self.maxLog+1)]
        self.parent[0]=parent
        self.depth=depth
        for i in range(self.maxLog):
            for j in range(V):
                if self.parent[i][j]!=-1:
                    self.parent[i+1][j]=self.parent[i][self.parent[i][j]]
    def lca(self,a,b):
        if self.depth[a]>self.depth[b]:
            a,b=b,a
        for i in range(self.maxLog):
            if (self.depth[b]-self.depth[a])&(1<<i):
                b=self.parent[i][b]
        if a==b:
            return b
        for i in reversed(range(self.maxLog-1)):
            if self.parent[i][a]!=self.parent[i][b]:
                a=self.parent[i][a]
                b=self.parent[i][b]
        return self.parent[0][a]

from collections import deque
def Eulertour(Edges,n,root=0):
    Euler=[]
    Depth=[-1]*n
    Depth[root]=0
    Parent=[-1]*n
    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
                Parent[to]=fr
                que2.append(to)
        que.extend(que2)
        que2=deque()
        Visited[fr]=True
    return Euler,Depth,Parent

n,q=map(int,input().split())
Edgedict=[dict() for _ in range(n)]
for _ in range(n-1):
    a,b,c,d=map(int,input().split())
    a-=1; b-=1
    Edgedict[a][b]=(c,d)
    Edgedict[b][a]=(c,d)
Queries=[tuple(map(int,input().split())) for _ in range(q)]
Euler,Depth,Parent=Eulertour(Edgedict,n)
lca=LCA(n,Edgedict,Depth,Parent)
Q=[[] for _ in range(n)]
for i,(x,y,u,v) in enumerate(Queries):
    u-=1; v-=1
    Q[u].append([i,x,y,True])
    Q[v].append([i,x,y,True])
    Q[lca.lca(u,v)].append([i,x,y,False])
Ans=[0]*q
dist=0
C_len=[0]*n
C_cnt=[0]*n
for i in range(1,len(Euler)):
    idx=Euler[i][1]
    c,l=Edgedict[Euler[i-1][1]][idx]
    if Euler[i-1][0]<Euler[i][0]:
        dist+=l
        C_len[c]+=l
        C_cnt[c]+=1
        for q_idx,x,y,flag in Q[idx]:
            if flag:
                Ans[q_idx]+=dist+C_cnt[x]*y-C_len[x]
            else:
                Ans[q_idx]-=(dist+C_cnt[x]*y-C_len[x])*2
    else:
        dist-=l
        C_len[c]-=l
        C_cnt[c]-=1
print(*Ans,sep='\n')

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

N, Q = map(int, input().split())
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
        a, b, c, d = map(int, input().split())
        edge[a].append((b, c, d))
        edge[b].append((a, c, d))
        
depth = [0] * (N+1)
U = 17
ancestor = [[0] * (U+1) for _ in range(N+1)]

q = [(1, 0, 0)]
while q:
        qq = []
        for x, d, parent in q:
                depth[x] = d
                ax = ancestor[x]
                ax[0] = parent
                for i in range(d.bit_length()-1):
                        ax[i+1] = ancestor[ax[i]][i]

                for y, _, _ in edge[x]:
                        if y == parent:
                                continue
                        qq.append((y, d+1, x))
        q = qq

def lca(x, y):
        dx = depth[x]
        dy = depth[y]
        if dx > dy:
                x, y = y, x
                dx, dy = dy, dx
        diff = dy - dx
        while diff:
                step = diff & (-diff)
                y = ancestor[y][step.bit_length()-1]
                diff -= step
        while x!=y:
                j = 0
                while ancestor[x][j] != ancestor[y][j]:
                        j += 1
                if j==0:
                        return ancestor[x][0]
                x = ancestor[x][j-1]
                y = ancestor[y][j-1]
        return x

task = [[] for _ in range(N+1)]
for i in range(Q):
        x, y, u, v = map(int, input().split())
        task[u].append((i, x, y, 1))
        task[v].append((i, x, y, 1))
        task[lca(u, v)].append((i, x, y, -2))

answer = [0] * Q

def dfs(x=1, sums=[0]*(N+1), nums=[0]*(N+1), total=0, parent=0):
        for i, c, d, coef in task[x]:
                answer[i] += coef * (total - sums[c] + nums[c]*d)
        for y, c, d in edge[x]:
                if y == parent:
                        continue
                sums[c] += d
                nums[c] += 1
                total += d
                dfs(y, sums, nums, total, x)
                sums[c] -= d
                nums[c] -= 1
                total -= d
        return

dfs()

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

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

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

depth = [0] * (N+1)
U = 17
ancestor = [[0] * (U+1) for _ in range(N+1)]

q = [(1, 0, 0)]
while q:
    qq = []
    for x, d, parent in q:
        depth[x] = d
        ax = ancestor[x]
        ax[0] = parent
        for i in range(d.bit_length()-1):
            ax[i+1] = ancestor[ax[i]][i]
        for y, _, _ in graph[x]:
            if y == parent:
                continue
            qq.append((y, d+1, x))
    q = qq

def LCA(x, y):
    dx = depth[x]
    dy = depth[y]
    if dx > dy:
        x, y = y, x
        dx, dy = dy, dx
    diff = dy - dx
    while diff:
        step = diff & (-diff)
        y = ancestor[y][step.bit_length()-1]
        diff -= step
    while x != y:
        j = 0
        while ancestor[x][j] != ancestor[y][j]:
            j += 1
        if j == 0:
            return ancestor[x][0]
        x = ancestor[x][j-1]
        y = ancestor[y][j-1]
    return x

tasks = [[] for _ in range(N+1)]
for i, (x, y, u, v) in enumerate(query):
    tasks[u].append((i, x, y, 1))
    tasks[v].append((i, x, y, 1))
    tasks[LCA(u, v)].append((i, x, y, -2))

answer = [0] * Q

def dfs(x = 1, sums = [0] * (N+1), nums = [0] * (N+1), total = 0, parent = 0):
    for i, c, d, coef in tasks[x]:
        answer[i] += coef * (total - sums[c] + nums[c] * d)
    for y, c, d in graph[x]:
        if y == parent:
            continue
        sums[c] += d
        nums[c] += 1
        total += d
        dfs(y, sums, nums, total, x)
        sums[c] -= d
        nums[c] -= 1
        total -= d
    return

dfs()

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

Solution (Python):
import sys
from copy import deepcopy
from operator import add, itemgetter
class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

def getpar(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[p] = None
    stack = [p]
    visited = set([p])
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            stack.append(vf)
    return par

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res

def eulertour(Par, Cld, st):
    
    Cld = deepcopy(Cld)
    N = len(Cld)
    St = [None]*N
    En = [None]*N
    et = []
    sign = []
    vf = st
    cnt = 0
    depth = [0]*N
    while vf is not None:
        vn = vf
        et.append(vn)
        if St[vn] is None:
            St[vn] = cnt
        En[vn] = cnt
        cnt += 1
        if Cld[vn]:
            vf = Cld[vn].pop()
            sign.append(1)
            depth[vf] = depth[vn] + 1
        else:
            vf = P[vn]
            sign.append(-1)
    return St, En, et, sign[:-1], depth

N, Q = map(int, input().split())
Edge = [[] for _ in range(N)]
Edgelen = [0]*(N-1)
Edgenum = {}
Color = [[] for _ in range(N)]
for i in range(N-1):
    a, b, c, d = map(int, sys.stdin.readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
    Edgelen[i] = d
    Edgenum[(a, b)] = i
    Edgenum[(b, a)] = i
    Color[c].append(i) 

P = getpar(Edge, 0)
C = getcld(P)
St, En, et, sign, depth = eulertour(P, C, 0)
etnum = [Edgenum[(v1, v2)] for v1, v2 in zip(et, et[1:])]
etnuminv = [[] for _ in range(N-1)]
for i, e in enumerate(etnum):
    etnuminv[e].append(i)
etl = [Edgelen[num]*sign[i] for i, num in enumerate(etnum)]

LCA = Segtree(et, None, initialize = True, segf = lambda x, y: x if y is None or (x is not None and depth[x] < depth[y]) else y)
Leng = Segtree([0]+etl, 0, initialize = True, segf = add)

Query = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
Ans = [None]*Q
CQ = [[] for _ in range(N)]
for i, (x, y, u, v) in enumerate(Query):
    CQ[x].append((i, y, u-1, v-1))

for col, cq in enumerate(CQ):
    if not cq:
        continue
    inf = 2*10**9
    for vidx in Color[col]:
        Leng.update(1+etnuminv[vidx][0], inf)
        Leng.update(1+etnuminv[vidx][1], -inf)
    
    for i, y, u, v in cq:
        if St[u] > St[v]:
            u, v = v, u
        su = St[u]
        sv = St[v]
        lca = LCA.query(su, sv+1)
        dis = Leng.query(0, su+1) + Leng.query(0,sv+1) - 2*Leng.query(0,St[lca]+1)
        disq, disr = divmod(dis, inf)
        Ans[i] = disr + disq*y
    for vidx in Color[col]:
        Leng.update(1+etnuminv[vidx][0], Edgelen[vidx])
        Leng.update(1+etnuminv[vidx][1], -Edgelen[vidx])
print('\n'.join(map(str, Ans)))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
 
INF = 10**6
 
class RMQ:
    def __init__(self, a):
        self.n = len(a)
        self.size = 2**(self.n - 1).bit_length()
        self.data = [(INF, INF) for _ in range(2*self.size-1)]
        self.initialize(a)
 
    
    def initialize(self, a):
        for i in range(self.n):
            self.data[self.size + i - 1] = a[i][:]
        for i in range(self.size-2, -1, -1):
            self.data[i] = min(self.data[i*2 + 1], self.data[i*2 + 2])[:]
    
    
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])[:]
    
    
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = (INF, INF)
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])[:]
            if L & 1:
                s = min(s, self.data[L-1])[:]
                L += 1
            L >>= 1; R >>= 1
        return s
 
class LCA:
    def __init__(self, edge, root):
        self.itr = 0
        self.edge = edge[:]
        self.path = [0] * (2*n-1)
        self.depth = [0] * (2*n-1)
        self.color = [0] * (2*n-1)
        self.weight = [0] * (2*n-1)
        self.index = [0] * n
        self.euler_tour(-1, root, 0, 0, 0, 0)
        dat = list(zip(self.depth, self.path))
        self.rmq = RMQ(dat)
    
    
    def get_lca(self, u, v):
        l, r = self.index[u], self.index[v]
        if l > r:
            l, r = r, l
        return self.rmq.query(l, r+1)[1]
    
    def euler_tour(self, prev, v, d, k, c, w):
        self.index[v] = k
        self.path[self.itr] = v
        self.depth[self.itr] = d
        self.color[self.itr] = c
        self.weight[self.itr] = w
        self.itr += 1
        k += 1
        for dest, c, w in self.edge[v]:
            if prev == dest:
                continue
            k = self.euler_tour(v, dest, d + 1, k, c, w)
            self.path[self.itr] = v
            self.depth[self.itr] = d
            self.color[self.itr] = -c
            self.weight[self.itr] = -w
            self.itr += 1
            k += 1
        return k
        
n, q = [int(item) for item in input().split()] 
edge = [[] for _ in range(n)]
 
for _ in range(n-1):
    u, v, c, w = [int(item) for item in input().split()]
    u -= 1; v -= 1
    edge[u].append((v, c, w))
    edge[v].append((u, c, w))
 
lca = LCA(edge, 0)
memo = [dict() for _ in range(n)]
lca_memo = dict()
 
query = []
for _ in range(q):
    x, y, u, v = [int(item) for item in input().split()]
    u -= 1; v -= 1
    if u > v:
        u, v = v, u
    if (u, v) in lca_memo:
        ca = lca_memo[(u, v)]
    else:
        ca = lca.get_lca(u, v)
        lca_memo[(u, v)] = ca
    memo[u][x] = None
    memo[v][x] = None
    memo[ca][x] = None
    query.append((x, y, ca, u, v))
 
colors = [0] * n
c_depth = [0] * n
depth = 0
for p, c, w in zip(lca.path[1:], lca.color[1:], lca.weight[1:]):
    color = abs(c)
    if c < 0:
        colors[color] -= 1
    else:
        colors[color] += 1
    c_depth[color] += w
    depth += w
 
    for key in memo[p].keys():
        if memo[p][key] != None:
            break
        memo[p][key] = (colors[key], c_depth[key])
    memo[p][0] = depth 
 
ans = []
for x, y, ca, u, v in query:
    
    val = memo[u][0] + memo[v][0] - memo[ca][0] * 2
    
    val += (memo[v][x][0] + memo[u][x][0] - memo[ca][x][0] * 2) * y 
    val -= (memo[v][x][1] + memo[u][x][1] - memo[ca][x][1] * 2)
    ans.append(val)
print("\n".join(map(str,ans)))

Solution (Python):
import bisect
import math
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



class SparseTable:
    """
    構築 O(NlogN)、クエリ O(1)
    """

    def __init__(self, values, fn):
        """
        :param list values:
        :param callable fn: 結合則を満たす冪等な関数。min、max など。add はだめ
        """
        self._values = values
        self._fn = fn

        
        
        self._table = self._build(values, fn)

        
        self._msb = [0] * (len(values) + 1)
        for i in range(2, len(values) + 1):
            self._msb[i] = self._msb[i >> 1] + 1

    @staticmethod
    def _build(values, fn):
        
        size = int(math.log(len(values), 2)) + 1

        st = [[0] * size for _ in range(len(values))]
        for i in range(len(values)):
            st[i][0] = i
        for p in range(1, size):
            for i in range(len(values)):
                q = min(i + (1 << (p - 1)), len(values) - 1)
                l = st[i][p - 1]
                r = st[q][p - 1]
                if values[l] == fn(values[l], values[r]):
                    st[i][p] = l
                else:
                    st[i][p] = r
        return st

    def get(self, a, b):
        """
        半開区間 [a, b) に fn を適用した結果
        :param int a:
        :param int b:
        """
        if b <= a:
            return None
        p = self._msb[b - a]
        return self._fn(
            self._values[self._table[a][p]],
            self._values[self._table[b - (1 << p)][p]]
        )


def eulerian_trail(tree, max_v, root=0):
    """
    木のオイラー路; オイラーツアー
    :param list of (list of (int, int, int)) tree:
    :param int max_v:
    :param int root:
    :return: (trails, depths)
    :rtype: (list of int, list of int, list of (int, int))
    """
    seen = [False] * (max_v + 1)
    
    trails = []
    
    depths = []
    
    edges = []
    
    stack = [(root, 0, (0, 0), True)]
    while stack:
        v, d, edge, forward = stack.pop()
        seen[v] = True
        trails.append(v)
        depths.append(d)
        edges.append(edge)
        if not forward:
            continue
        for u, c, w in tree[v]:
            if not seen[u]:
                stack.append((v, d, (c, -w), False))
                stack.append((u, d + 1, (c, w), True))
    return trails, depths, edges


N, Q = list(map(int, sys.stdin.readline().split()))
ABCD = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]
XYVU = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]


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

trails, depths, edges = eulerian_trail(graph, max_v=N, root=1)
ids = [-1] * (N + 1)
for i, t in enumerate(trails):
    ids[t] = i

distances = []
color_dist = defaultdict(lambda: [(-1, 0)])
color_cnt = defaultdict(lambda: [(-1, 0)])
s = 0
for i, (c, d) in enumerate(edges):
    s += d
    distances.append(s)

    color_dist[c].append((i, color_dist[c][-1][1] + d))
    _, cc = color_cnt[c][-1]
    color_cnt[c].append((i, cc + 1 if d > 0 else cc - 1))

st = SparseTable(values=list(zip(depths, trails)), fn=min)


def get_lca(v, u):
    iv, iu = ids[v], ids[u]
    if iv > iu:
        iv, iu = iu, iv
    _, ret = st.get(iv, iu + 1)
    return ret


def distance(v):
    
    return distances[ids[v]]


def count_color(v, c):
    
    iv = ids[v]
    i = bisect.bisect_left(color_cnt[c], (iv + 1, 0))
    return color_cnt[c][i - 1][1]


def distance_color(v, c):
    
    iv = ids[v]
    i = bisect.bisect_left(color_dist[c], (iv + 1, 0))
    return color_dist[c][i - 1][1]


for x, y, u, v in XYVU:
    lca = get_lca(u, v)
    d = distance(u) + distance(v) - distance(lca) * 2
    c = count_color(u, x) + count_color(v, x) - count_color(lca, x) * 2
    s = distance_color(u, x) + distance_color(v, x) - distance_color(lca, x) * 2
    print(d - s + c * y)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
from math import log
from collections import deque

def solve():
    N, Q = map(int, input().split())
    es = [[] for i in range(N+1)]
    for i in range(N-1):
        u, v, c, d = map(int, input().split())
        es[u].append([v, c, d])
        es[v].append([u, c, d])
    LOG_N = int(log(N, 2)) + 1
    parent = [[-1] * (N+1) for i in range(LOG_N)]
    level = [None] * (N+1)
    level[1] = 0
    dq = deque()
    dq.append(1)
    while dq:
        v = dq.popleft()
        p = parent[0][v]
        lv = level[v]
        for u, c, d in es[v]:
            if u != p:
                parent[0][u] = v
                level[u] = lv + 1
                dq.append(u)
    for k in range(LOG_N-1):
        parentk = parent[k]
        for v in range(1, N+1):
            if parentk[v] < 0:
                parent[k+1][v] = -1
            else:
                parent[k+1][v] = parentk[parentk[v]]

    def lca(u, v):
        if level[u] > level[v]:
            u, v = v, u
        for k in range(LOG_N)[::-1]:
            if (level[v] - level[u]) >> k & 1:
                v = parent[k][v]
        if u == v:
            return u
        for k in range(LOG_N)[::-1]:
            if parent[k][u] != parent[k][v]:
                u, v = parent[k][u], parent[k][v]
        return parent[0][u]

    qs = [[] for i in range(N+1)]
    for i in range(Q):
        x, y, u, v = map(int, input().split())
        qs[u].append([i, x, y, 1])
        qs[v].append([i, x, y, 1])
        a = lca(u, v)
        qs[a].append([i, x, y, -2])
    ds = [0] * N
    cnt = [0] * N
    query = [0] * Q

    def EulerTour(v, p, d):
        for id, col, y, f in qs[v]:
            query[id] += f * (d + y * cnt[col] - ds[col])
        for u, c, _d in es[v]:
            if u != p:
                ds[c] += _d
                cnt[c] += 1
                EulerTour(u, v, d + _d)
                ds[c] -= _d
                cnt[c] -= 1

    EulerTour(1, -1, 0)
    for res in query:
        print(res)

if __name__ == '__main__':
    solve()