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
import operator
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 SegmentTree:
    
    def __init__(self, size, fn=operator.add, default=None, initial_values=None):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        :param default:
        :param list initial_values:
        """
        default = default or 0

        
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._fn = fn

        self._tree = [default] * (self._size * 2 - 1)
        if initial_values:
            i = self._size - 1
            for v in initial_values:
                self._tree[i] = v
                i += 1
            i = self._size - 2
            while i >= 0:
                self._tree[i] = self._fn(self._tree[i * 2 + 1], self._tree[i * 2 + 2])
                i -= 1

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size


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 = SegmentTree(size=len(trails), fn=min, default=(IINF, -1), initial_values=list(zip(depths, trails)))


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

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n,a,b = LI()
    print(min(a*n,b))
    return


def B():
    n,d = LI()
    x = LIR(n)
    f = defaultdict(lambda : 0)
    for i in range(1000000):
        f[i*i] = 1
    ans = 0
    for i in range(n):
        for j in range(i+1,n):
            s = 0
            for k in range(d):
                s += (x[i][k]-x[j][k])**2
            if f[s]:
                ans += 1
    print(ans)
    return


def C():
    l,r = LI()
    if r-l > 2019:
        print(0)
        quit()
    ans = float("inf")
    for i in range(l,r+1):
        for j in range(i+1,r+1):
            if i*j%2019 < ans:
                ans = i*j%2019
    print(ans)
    return


def D():
    n = I()
    a = LI()
    for i in range(n):
        a[i] *= 2
    x = a[0]
    for i in range(1,n):
        if i%2:
            x -= a[i]
        else:
            x += a[i]
    b = [x//2]
    for i in range(n-1):
        b.append(abs(b[-1]-a[i]))
    print(*b)
    return


def E():
    n,k = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    if k == 1:
        if n == 1:
            print(1)
            quit()
        else:
            print(0)
            quit()
    if k == 2:
        print(2)
        quit()
    d = [0]*n
    v.append([])
    v.append([])
    q = deque([0])
    bfs = [1]*n
    bfs[0] = 0
    f = [0]*n
    while q:
        x= q.popleft()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                q.append(y)
    ans = 1
    q = deque([0])
    dp = [None]*n
    dp[0] = k
    bfs = [1]*n
    bfs[0] = 0
    while q:
        x = q.popleft()
        m = len(v[x])
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                dp[y] = k-m
                m -= 1
                q.append(y)
    for i in dp:
        ans *= i
        ans %= mod
    print(ans)
    return


def F():
    def lca(x,y):
        k = depth[x]-depth[y]
        while k > 0:
            x = par[x][int(math.log(k,2))]
            k = depth[x]-depth[y]
        k = -k
        while k > 0:
            y = par[y][int(math.log(k,2))]
            k = depth[y]-depth[x]
        if x == y:
            return x
        for i in range(M+1)[::-1]:
            if i < len(par[x]):
                if par[x][i] != par[y][i]:
                    x = par[x][i]
                    y = par[y][i]
        return par[x][0]

    def euler_tour(x,p,color):
        for i,c,d,k in f[x]:
            if k:
                query[i] -= 2*(-color[c][0]+color[c][1]*d)
            else:
                query[i] += -color[c][0]+color[c][1]*d
        for y,c,d in v[x]:
            if y != p:
                color[c][0] += d
                color[c][1] += 1
                euler_tour(y,x,color)
                color[c][0] -= d
                color[c][1] -= 1

    M = 16 
    n,Q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b,c,d = LI()
        a -= 1
        b -= 1
        c -= 1
        v[a].append((b,c,d))
        v[b].append((a,c,d))
    par = [[] for i in range(n)]
    dist = [-1]*n
    dist[0] = 0
    depth = [0]*n
    q = deque([0])
    while q:
        x = q.popleft()
        for y,c,d in v[x]:
            if dist[y] < 0:
                dist[y] = dist[x]+d
                depth[y] = depth[x]+1
                q.append(y)
                par[y].append(x)

    l = [i for i in range(n)]
    l.sort(key = lambda x:depth[x])
    for i in range(M):
        k = 1<<(i+1)
        for x in l[::-1]:
            if depth[x] < k:break
            par[x].append(par[par[x][i]][i])
    f = [[] for i in range(n)] 
    query = [0]*Q 
    for i in range(Q):
        x,y,a,b = LI()
        x -= 1
        a -= 1
        b -= 1
        f[a].append((i,x,y,0))
        f[b].append((i,x,y,0))
        l = lca(a,b)
        f[l].append((i,x,y,1))
        query[i] = dist[a]+dist[b]-2*dist[l]
    color = [[0,0] for i in range(n)] 
    euler_tour(0,-1,color)
    for i in query:
        print(i)
    return



if __name__ == "__main__":
    F()

Solution (Python):
from collections import defaultdict
from math import log2
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline

def f(n,q):
    def dfs(i, oi=-1, dpt=0):
        depth[i] = dpt
        parent_2k[0][i] = oi
        for ki, c, d in to[i]:
            if ki == oi: continue
            dfs(ki, i, dpt + 1)
        return

    def make_parent(level):
        parent_2kk1 = parent_2k[0]
        for k in range(1, level):
            parent_2kk = parent_2k[k]
            for i in range(n):
                parent1 = parent_2kk1[i]
                if parent1 != -1:
                    parent_2kk[i] = parent_2kk1[parent1]
            parent_2kk1 = parent_2kk
        return

    def lca(u, v):
        dist_uv = depth[u] - depth[v]
        if dist_uv < 0:
            u, v = v, u
            dist_uv *= -1

        k = 0
        while dist_uv:
            if dist_uv & 1:
                u = parent_2k[k][u]
            dist_uv >>= 1
            k += 1

        if u == v:
            return u

        for k in range(int(log2(depth[u])) + 1, -1, -1):
            pu = parent_2k[k][u]
            pv = parent_2k[k][v]
            if pu != pv:
                u = pu
                v = pv
        return parent_2k[0][u]

    to = defaultdict(list)
    root = 0
    depth = [0] * n
    level = int(log2(n)) + 1
    parent_2k = [[-1] * n for _ in range(level)]

    for _ in range(n - 1):
        a, b, c, d = list(map(int, input().split()))
        to[a - 1] += [[b - 1, c - 1, d]]
        to[b - 1] += [[a - 1, c - 1, d]]

    dfs(root)
    make_parent(level)

    qs = [[] for _ in range(n)]
    for qi in range(q):
        x, y, u, v = map(int, input().split())
        qs[u - 1].append([qi, x - 1, y, 1])
        qs[v - 1].append([qi, x - 1, y, 1])
        qs[lca(u - 1, v - 1)].append([qi, x - 1, y, -2])

    cnt_c = [0] * n
    sum_c = [0] * n
    ans = [0] * q

    def dfs2(i, oi=-1, sum_d=0):
        for qi, qc, qd, qk in qs[i]:
            ans[qi] += (sum_d - sum_c[qc] + qd * cnt_c[qc]) * qk
        for ki, c, d in to[i]:
            if ki == oi: continue
            cnt_c[c] += 1
            sum_c[c] += d
            dfs2(ki, i, sum_d + d)
            cnt_c[c] -= 1
            sum_c[c] -= d
        return

    dfs2(root)
    for x in ans:
        print(x)

n, q = map(int, input().split())
f(n,q)

Solution (Python):
def f_colorful_tree(N, Q, Edges, Queries):
    
    

    import sys
    sys.setrecursionlimit(10**5)

    
    tree = [[] for _ in range(N)]
    for a, b, c, d in Edges:
        tree[a - 1].append((b - 1, c - 1, d))
        tree[b - 1].append((a - 1, c - 1, d))

    """Least Common Ancestorを求めるための前処理"""
    depth_from_root = [0] * N
    
    
    parent_to_root = [[-1] * N for _ in range(18)]
    distance_from_root = [0] * N

    def dfs1(parent, current, depth, distance):
        depth_from_root[current] = depth
        parent_to_root[0][current] = parent
        distance_from_root[current] = distance
        for child, _, dist in tree[current]:  
            if child != parent:
                dfs1(current, child, depth + 1, distance + dist)

    dfs1(-1, 0, 0, 0)
    for i in range(17):
        for j in range(N):
            parent_to_root[i + 1][j] = parent_to_root[i][parent_to_root[i][j]]

    def least_common_ancestor(a, b):
        
        if depth_from_root[a] > depth_from_root[b]:
            a, b = b, a
        for i in range(18):
            if (depth_from_root[b] - depth_from_root[a]) & (1 << i):
                b = parent_to_root[i][b]
        if a == b:
            return a
        for i in range(18)[::-1]:
            if parent_to_root[i][a] != parent_to_root[i][b]:
                a = parent_to_root[i][a]
                b = parent_to_root[i][b]
        return parent_to_root[0][a]

    """先読みした(オフライン)クエリに対して解を求める"""
    ans = [0] * Q
    v_need = [[] for i in range(N)]
    for i, (x, y, u, v) in enumerate(Queries):
        
        lca = least_common_ancestor(u - 1, v - 1)
        
        
        
        
        v_need[u - 1].append((i, x - 1, y, 1))
        v_need[v - 1].append((i, x - 1, y, 1))
        v_need[lca].append((i, x - 1, y, -2))

    color_appear = [0] * N  
    color_distance = [0] * N  

    def dfs2(parent, current):
        nonlocal color_distance
        for i, x, y, coefficient in v_need[current]:
            ans[i] += (coefficient * (distance_from_root[current]
                                      - color_distance[x] + y * color_appear[x]))
        for child, x, y in tree[current]:
            if child == parent:
                continue
            color_appear[x] += 1
            color_distance[x] += y
            dfs2(current, child)
            
            
            color_appear[x] -= 1
            color_distance[x] -= y

    dfs2(-1, 0)
    return '\n'.join(map(str, ans))

N, Q = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(N - 1)]
Queries = [[int(i) for i in input().split()] for j in range(Q)]
print(f_colorful_tree(N, Q, Edges, Queries))

Solution (Python):
import sys
input = sys.stdin.readline

N,Q=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]
Query=[list(map(int,input().split())) for i in range(Q)]
mod=10**9+7

EDGELIST=[dict() for i in range(N+1)]
for x,y,c,l in EDGE:
    EDGELIST[x][y]=(c,l)
    EDGELIST[y][x]=(c,l)
    


DEPTH=[-1]*(N+1)
DEPTH[1]=0

from collections import deque
QUE = deque([1])
QUE2 = deque()
EULER=[]

USED=[0]*(N+1)
while QUE:
    x=QUE.pop()
    EULER.append((DEPTH[x],x))
    if USED[x]==1:
        continue
    for to in EDGELIST[x]:
        
        if USED[to]==0:
            DEPTH[to]=DEPTH[x]+1
            QUE2.append(to)
        else:
            QUE.append(to)
    QUE.extend(QUE2)
    QUE2=deque()
 
    USED[x]=1

MINP=[1<<30]*(N+1)
MAXP=[-1]*(N+1)

for ind,(depth,p) in enumerate(EULER):
    MINP[p]=min(MINP[p],ind)
    MAXP[p]=ind

LEN=len(EULER)

seg_el=1<<(LEN.bit_length())
SEG=[(1<<30,0)]*(2*seg_el)

for i in range(LEN):
    SEG[i+seg_el]=EULER[i]

for i in range(seg_el-1,0,-1):
    SEG[i]=min(SEG[i*2],SEG[i*2+1])

def update(n,x,seg_el):
    i=n+seg_el
    SEG[i]=x
    i>>=1
    
    while i!=0:
        SEG[i]=min(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r):
    L=l+seg_el
    R=r+seg_el
    ANS=(1<<30,0)

    while L<R:
        if L & 1:
            ANS=min(ANS , SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS=min(ANS , SEG[R])
        L>>=1
        R>>=1

    return ANS

def LCA(l,r):
    return getvalues(min(MINP[l],MINP[r]),max(MAXP[l],MAXP[r])+1)

N_q=[[] for i in range(N+1)]
for ind,(c,pl,x,y) in enumerate(Query):
    N_q[x].append([ind,c,pl,1])
    N_q[y].append([ind,c,pl,1])
    N_q[LCA(x,y)[1]].append([ind,c,pl,0])

ANS=[0]*Q

LENG=0
C_LENGTH=[0]*N
C_SUM=[0]*N

for i in range(1,len(EULER)):
    ind=EULER[i][1]
    c,l=EDGELIST[EULER[i-1][1]][ind]
    if EULER[i][0]>EULER[i-1][0]:
        LENG+=l
        C_LENGTH[c]+=l
        C_SUM[c]+=1

        for que,c,pl,boo in N_q[ind]:
            if boo==1:
                ANS[que]+=LENG+C_SUM[c]*pl-C_LENGTH[c]

            else:
                ANS[que]-=(LENG+C_SUM[c]*pl-C_LENGTH[c])*2
            
    else:
        LENG-=l
        C_LENGTH[c]-=l
        C_SUM[c]-=1

for ans in ANS:
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N,Q=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]
Query=[list(map(int,input().split())) for i in range(Q)]
mod=10**9+7

EDGELIST=[dict() for i in range(N+1)]
for x,y,c,l in EDGE:
    EDGELIST[x][y]=(c,l)
    EDGELIST[y][x]=(c,l)
    


DEPTH=[-1]*(N+1)
DEPTH[1]=0

from collections import deque
QUE = deque([1])
QUE2 = deque()
EULER=[]

USED=[0]*(N+1)
while QUE:
    x=QUE.pop()
    EULER.append((DEPTH[x],x))
    if USED[x]==1:
        continue
    for to in EDGELIST[x]:
        
        if USED[to]==0:
            DEPTH[to]=DEPTH[x]+1
            QUE2.append(to)
        else:
            QUE.append(to)
    QUE.extend(QUE2)
    QUE2=deque()
 
    USED[x]=1

MINP=[1<<30]*(N+1)
MAXP=[-1]*(N+1)

for ind,(depth,p) in enumerate(EULER):
    MINP[p]=min(MINP[p],ind)
    MAXP[p]=max(MAXP[p],ind)

LEN=len(EULER)

seg_el=1<<(LEN.bit_length())
SEG=[(1<<30,0)]*(2*seg_el)

for i in range(LEN):
    SEG[i+seg_el]=EULER[i]

for i in range(seg_el-1,0,-1):
    SEG[i]=min(SEG[i*2],SEG[i*2+1])

def update(n,x,seg_el):
    i=n+seg_el
    SEG[i]=x
    i>>=1
    
    while i!=0:
        SEG[i]=min(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r):
    L=l+seg_el
    R=r+seg_el
    ANS=(1<<30,0)

    while L<R:
        if L & 1:
            ANS=min(ANS , SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS=min(ANS , SEG[R])
        L>>=1
        R>>=1

    return ANS

def LCA(l,r):
    return getvalues(min(MINP[l],MINP[r]),max(MAXP[l],MAXP[r])+1)

N_q=[[] for i in range(N+1)]
for ind,(c,pl,x,y) in enumerate(Query):
    N_q[x].append([ind,c,pl,1])
    N_q[y].append([ind,c,pl,1])
    N_q[LCA(x,y)[1]].append([ind,c,pl,0])

ANS=[0]*Q

LENG=0
C_LENGTH=[0]*N
C_SUM=[0]*N

for i in range(1,len(EULER)):
    ind=EULER[i][1]
    c,l=EDGELIST[EULER[i-1][1]][ind]
    if EULER[i][0]>EULER[i-1][0]:
        LENG+=l
        C_LENGTH[c]+=l
        C_SUM[c]+=1

        for que,c,pl,boo in N_q[ind]:
            if boo==1:
                ANS[que]+=LENG+C_SUM[c]*pl-C_LENGTH[c]

            else:
                ANS[que]-=(LENG+C_SUM[c]*pl-C_LENGTH[c])*2
            
    else:
        LENG-=l
        C_LENGTH[c]-=l
        C_SUM[c]-=1

for ans in ANS:
    print(ans)

Solution (Python):



import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

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



dep=[0]*n
par=[[-1]*n for i in range(18)]

dis=[0]*n



def dfs(p,v,d,dd):
    dep[v]=d
    par[0][v]=p
    dis[v]=dd
    for w, _, dist in edges[v]:
        if w!=p:
            dfs(v,w,d+1, dd+dist)

def lca(a,b):
    if dep[a]>dep[b]:
        a,b=b,a
    for i in range(18):
        if (dep[b]-dep[a]) & 1<<i:
            b=par[i][b]
    if a==b:
        return a
    for i in range(18)[::-1]:
        if par[i][a]!=par[i][b]:
            a=par[i][a]
            b=par[i][b]
    return par[0][a]

dfs(-1,0,0,0)

for i in range(17):
    for j in range(n):
        par[i+1][j]=par[i][par[i][j]]



ans = [0]*q
v_need = [[] for i in range(n)]
for i in range(q):
    x,y,u,v = map(int, input().split())
    x -= 1
    u -= 1
    v -= 1
    l = lca(u, v)
    
    
    v_need[u].append((i, x, y, 1))
    v_need[v].append((i, x, y, 1))
    v_need[l].append((i, x, y, -2))


color = [0]*n

cdist = [0]*n

def dfs2(cur, par):
    for i, x, y, k in v_need[cur]:
        ans[i] += k*(dis[cur] - cdist[x] + y*color[x])
    for to, x, y, in edges[cur]:
        if to == par:
            continue
        color[x] += 1
        cdist[x] += y
        dfs2(to, cur)
        
        
        color[x] -= 1
        cdist[x] -= y
dfs2(0, -1)

for i in ans:
    print(i)

Solution (Python):
import sys
input = sys.stdin.readline

N,Q=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]
Query=[list(map(int,input().split())) for i in range(Q)]
mod=10**9+7

EDGELIST=[dict() for i in range(N+1)]
for x,y,c,l in EDGE:
    EDGELIST[x][y]=(c,l)
    EDGELIST[y][x]=(c,l)
    


DEPTH=[-1]*(N+1)
DEPTH[1]=0

from collections import deque
QUE = deque([1])
QUE2 = deque()
EULER=[]

USED=[0]*(N+1)
while QUE:
    x=QUE.pop()
    EULER.append((DEPTH[x],x))
    if USED[x]==1:
        continue
    for to in EDGELIST[x]:
        
        if USED[to]==0:
            DEPTH[to]=DEPTH[x]+1
            QUE2.append(to)
        else:
            QUE.append(to)
    QUE.extend(QUE2)
    QUE2=deque()
 
    USED[x]=1

MINP=[1<<30]*(N+1)
MAXP=[-1]*(N+1)

for ind,(depth,p) in enumerate(EULER):
    MINP[p]=min(MINP[p],ind)
    MAXP[p]=max(MAXP[p],ind)

LEN=len(EULER)

seg_el=1<<(LEN.bit_length())
SEG=[(1<<30,0)]*(2*seg_el)

for i in range(LEN):
    SEG[i+seg_el]=EULER[i]

for i in range(seg_el-1,0,-1):
    SEG[i]=min(SEG[i*2],SEG[i*2+1])

def update(n,x,seg_el):
    i=n+seg_el
    SEG[i]=x
    i>>=1
    
    while i!=0:
        SEG[i]=min(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r):
    L=l+seg_el
    R=r+seg_el
    ANS=(1<<30,0)

    while L<R:
        if L & 1:
            ANS=min(ANS , SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS=min(ANS , SEG[R])
        L>>=1
        R>>=1

    return ANS

def LCA(l,r):
    return getvalues(min(MINP[l],MINP[r]),max(MAXP[l],MAXP[r])+1)

check=[set() for i in range(N+1)]
for c,l,x,y in Query:
    check[x].add(c)
    check[y].add(c)
    check[LCA(x,y)[1]].add(c)

LENGTH=[0]*(N+1)
LENG=0
C_LENGTH=[0]*N
C_SUM=[0]*N
C_LDICT=dict()
C_SDICT=dict()

for c in check[1]:
    C_LDICT[(1,c)]=0
    C_SDICT[(1,c)]=0
    

for i in range(1,len(EULER)):
    ind=EULER[i][1]
    c,l=EDGELIST[EULER[i-1][1]][ind]
    if EULER[i][0]>EULER[i-1][0]:
        LENG+=l
        C_LENGTH[c]+=l
        C_SUM[c]+=1

        LENGTH[ind]=LENG

        for c in check[ind]:
            C_LDICT[(ind,c)]=C_LENGTH[c]
            C_SDICT[(ind,c)]=C_SUM[c]
            

    else:
        LENG-=l
        C_LENGTH[c]-=l
        C_SUM[c]-=1
        
        
for c,pl,x,y in Query:
    ind=LCA(x,y)[1]
    print(LENGTH[x]+LENGTH[y]-LENGTH[ind]*2+(C_SDICT[x,c]+C_SDICT[y,c]-C_SDICT[ind,c]*2)*pl-(C_LDICT[x,c]+C_LDICT[y,c]-C_LDICT[ind,c]*2))

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

N, Q = map(int, input().split())

path = [[] for _ in range(N)]

for _ in range(N-1) :
    a, b, c, d = (int(i) for i in input().split())
    path[a-1].append((b-1, c-1, d))
    path[b-1].append((a-1, c-1, d))


for K in range(18) :
    if 2 ** K >= N :
        break


parent = [[-1] * N for _ in range(K)]
rank = [-1 for _ in range(N)]

rank[0] = 0
queue = [0]

while queue :
    cur = queue.pop()
    for nex, _, _ in path[cur] :
        if rank[nex] < 0 :
            queue.append(nex)
            parent[0][nex] = cur
            rank[nex] = rank[cur] + 1


for i in range(1, K) :
    for j in range(N) :
        if parent[i-1][j] > 0 :
            parent[i][j] = parent[i-1][parent[i-1][j]]


def lca(a, b) :
    if rank[a] > rank[b] :
        a, b = b, a

    diff = rank[b] - rank[a]
    i = 0
    while diff > 0 :
        if diff & 1 :
            b = parent[i][b]
        diff >>= 1
        i += 1
        
    if a == b :
        return a

    for i in range(K-1, -1, -1) :
        if parent[i][a] != parent[i][b] :
            a = parent[i][a]
            b = parent[i][b]

    return parent[0][a]


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

ret = [0] * Q
C = [0] * (N-1)
D = [0] * (N-1)

def dfs(cur, pre, tot) :
    for i, t, c, d in schedule[cur] :
        ret[i] += t * (tot - D[c] + C[c] * d)
    
    for nex, c, d in path[cur] :
        if nex == pre :
            continue
        C[c] += 1
        D[c] += d
        dfs(nex, cur, tot + d)
        C[c] -= 1
        D[c] -= d

dfs(0, -1, 0)
   
for i in range(Q) :
    print(ret[i])

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
from bisect import bisect_right as br
N, K = map(int, input().split())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y, c, d = map(int, input().split())
    X[x-1].append((y-1, c-1, d))
    X[y-1].append((x-1, c-1, d))

P = [(-1, 0, 0)] * N
Q = [(0, 0, 0)]
R = []
ET = []
ct = 0
CT = [0] * (N-1) * 2
CTA = [-1]* N
BT = [[[-1], [0], [0]] for _ in range(N)]
while Q:
    i, c, d = Q.pop()
    if i < 0:
        BT[c][0].append(ct)
        BT[c][1].append(BT[c][1][-1]-1)
        BT[c][2].append(BT[c][2][-1]-d)
        ct += 1
        continue
    R.append(i)
    if i > 0:
        if CTA[i] < 0: CTA[i] = ct
        BT[c][0].append(ct)
        BT[c][1].append(BT[c][1][-1]+1)
        BT[c][2].append(BT[c][2][-1]+d)
        ct += 1
    
    for a, c, d in X[i][::-1]:
        if a != P[i][0]:
            ET.append((i, a))
            P[a] = (i, c, d)
            for k in range(len(X[a])):
                if X[a][k][0] == i:
                    del X[a][k]
                    break
            Q.append((~a, c, d))
            Q.append((a, c, d))

L = [[0, 0] for _ in range(N)]
for i in R[1:]:
    p, c, d = P[i]
    L[i][0] = L[p][0] + 1
    L[i][1] = L[p][1] + d

D = [[P[i][0] for i in range(N)]] + [[-1]*N for _ in range(16)]
for k in range(1, 17):
    for i in range(N):
        a = D[k-1][i]
        if a > 0:
            D[k][i] = D[k-1][a]

def lca(u0, v0):
    u, v = u0, v0
    if L[u][0] < L[v][0]:
        u, v = v, u
    
    while L[u][0] > L[v][0]:
        d = L[u][0] - L[v][0]
        dd = d.bit_length() - 1
        u = D[dd][u]
    if u == v:
        return u
    
    for i in range(17)[::-1]:
        if D[i][u] != D[i][v]:
            u = D[i][u]
            v = D[i][v]
    
    return D[0][u]
    

def calc(x, y, w):
    aa = br(BT[x][0], CTA[w]) - 1
    c = BT[x][1][aa]
    d = BT[x][2][aa]
    return L[w][1] + c*y - d

for _ in range(K):
    x, y, u, v = map(int, input().split())
    x, u, v = x-1, u-1, v-1
    ll = lca(u, v)
    print(calc(x, y, u) + calc(x, y, v) - 2*calc(x, y, ll))