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 bisect import bisect
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.buffer.readline()[:-1]

class LCA():
	def __init__(self, adj_given, root_given):
		self.adj = adj = adj_given
		self.root = root_given
		self.n = n = len(adj)
		self.maxlog = 0
		while (1 << self.maxlog) < n:
			self.maxlog += 1
		maxlog = self.maxlog
		self.par = [[-1 for _ in range(n)] for _ in range(maxlog)]
		self.dep = [0 for _ in range(n)]
		self.num_key = [[0] for _ in range(n)]
		self.num_value = [[0] for _ in range(n)]
		self.sum_value = [[0] for _ in range(n)]
		self.first = [10**6 for _ in range(n)]
		self.first[self.root] = 0
		self.visited = 1
		self.cnt = 1
		self.dist = [0 for _ in range(n)]

	def dfs(self, x, pa, de, co, le):
		par = self.par
		dep = self.dep
		root = self.root
		
		par[0][x] = pa
		dep[x] = de

		if x != root and self.visited < n:
			self.num_key[co].append(self.cnt)
			self.num_value[co].append(self.num_value[co][-1] + 1)
			self.sum_value[co].append(self.sum_value[co][-1] + le)
			if self.first[x] == 10**6:
				self.visited += 1
				self.first[x] = self.cnt
			self.cnt += 1
			self.dist[x] = self.dist[pa] + le

		for v, c, l in adj[x]:
			if v != pa:
				self.dfs(v, x, de+1, c, l)

		if x != root and self.visited < n:
			self.num_key[co].append(self.cnt)
			self.num_value[co].append(self.num_value[co][-1] - 1)
			self.sum_value[co].append(self.sum_value[co][-1] - le)
			self.cnt += 1

		return

	def calc(self):
		root = self.root
		par = self.par
		maxlog = self.maxlog
		self.dfs(root, -1, 0, -1, 0)

		for k in range(maxlog-1):
			for v in range(n):
				if par[k][v] < 0:
					continue
				else:
					par[k+1][v] = par[k][par[k][v]]
		return

	def get_lca(self, u, v):
		par = self.par
		dep = self.dep
		maxlog = self.maxlog
		if dep[u] > dep[v]:
			u, v = v, u
		for k in range(maxlog):
			if ((dep[v] - dep[u]) >> k) & 1:
				v = par[k][v]

		if u == v:
			return u
		else:
			for k in range(maxlog-1, -1, -1):
				if par[k][u] != par[k][v]:
					u = par[k][u]
					v = par[k][v]
			return par[0][u]

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

lca = LCA(adj, 0)
lca.calc()

for _ in range(q):
	x, y, u, v = map(int, input().split())
	x, u, v = x-1, u-1, v-1
	a = lca.get_lca(u, v)
	id_u = max(bisect(lca.num_key[x], lca.first[u])-1, 0)
	id_v = max(bisect(lca.num_key[x], lca.first[v])-1, 0)
	id_a = max(bisect(lca.num_key[x], lca.first[a])-1, 0)

	dist_u = lca.dist[u] + lca.num_value[x][id_u] * y - lca.sum_value[x][id_u]
	dist_v = lca.dist[v] + lca.num_value[x][id_v] * y - lca.sum_value[x][id_v]
	dist_a = lca.dist[a] + lca.num_value[x][id_a] * y - lca.sum_value[x][id_a]
	print(dist_u + dist_v - 2 * dist_a)

Solution (Python):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.node_size=len(ls)+1
                self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.node_size=int(input())
        else:
            self.node_size=inp_size
        self.edges,_=GI(self.node_size,self.node_size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.node_size=len(ls)+1
        self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  
        tps=[]
        q=deque([x])
        v=[None]*self.node_size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.node_size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.node_size
        self.ETout=[-1]*self.node_size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def doubling_LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.depth=[None]*self.node_size
            self.depth=self.bfs(0,func=lambda pr,prv,nxt,dist:prv+1)
            self.par=self.bfs(0,func=lambda pr,prv,nxt,dist:pr)
            self.db=[self.par]
            for i in range(self.node_size.bit_length()):
                
                self.db+=[[self.db[-1][self.db[-1][i]] for i in range(self.node_size)]]
            self.LCA_init_stat=True
        dx=self.depth[x]
        dy=self.depth[y]
        if dx>dy:
            dx,dy=dy,dx
        c=self.node_size.bit_length()
        while c>0:
            if dx+c<=dy:
                x=self.db[c][x]
                dx+=1<<c
            c>>=1
        
        if x==y:
            return x
        
        c=self.node_size.bit_length()
        while c>0:
            if self.db[c][x]!=self.db[c][y]:
                x=self.db[c][x]
                y=self.db[c][y]
            c>>=1
        
        return self.par[x]
        
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in e]) for e in self.edges]):
            print( [[nd for nd,d in e] for e in self.edges] )
        else:
            print(self)
 
    def dfs2(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        dfs_tr=[x]
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
                    dfs_tr+=nb,
        return v,dfs_tr

class SparseTable: 
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    
    def query(self,l,r):
        if r>self.size:r=self.size
        
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    
    def query_id(self,l,r):
        if r>self.size:r=self.size
        
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos

    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)

show_flg=False
show_flg=True
ans=0
 
n,q=LI()
ls=deque()
col=dict()
e_len=dict()
for i in range(n-1):
    a,b,c,d=LI_()
    d+=1
    ls+=[(a,b,d)]
    
    eid=a*n+b if a<b else b*n+a
    col[eid]=c
    e_len[eid]=d
    
tr=Tree(init=False)
tr.listin(ls,index=0)
 
root=0
dist=tr.dfs(root)
tr.EulerTour(0)
dep=tr.depth
et=tr.ETtable
 
ad=[[0] for i in range(n)]
an=[[0] for i in range(n)]
index=[[] for i in range(n)]
for i in range(2*n-1-1):
    a,b=et[i],et[i+1]
    sign=1 if dep[a]<dep[b] else -1
    eid=a*n+b if a<b else b*n+a
    c=col[eid]
    dd=e_len[eid]*sign
    an[c]+=[an[c][-1]+sign]
    ad[c]+=[ad[c][-1]+dd]
    index[c]+=[i]
for i in range(n):
    ad[i]+=[ad[i][-1]]
    an[i]+=[an[i][-1]]
 
for i in range(q):
    x,y,u,v=LI_()
    y+=1
    lca=tr.LCA(root,u,v)
    path=dist[u]+dist[v]-dist[lca]*2
    
    ui=bisect.bisect_left(index[x],tr.ETin[u])
    vi=bisect.bisect_left(index[x],tr.ETin[v])
    ai=bisect.bisect_left(index[x],tr.ETin[lca])
    
    c_path=ad[x][ui]+ad[x][vi]-ad[x][ai]*2
    c_n=an[x][ui]+an[x][vi]-an[x][ai]*2
    ans=path-c_path+c_n*y
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6+1) 


def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None



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




edge = [[] for i in range(N)]
for i in range(N-1):
    a,b,c,w = map(int,input().split())
    edge[a-1].append((b-1,c-1,w))
    edge[b-1].append((a-1,c-1,w)) 




def dfs(start):
    q=[(start,-1,0,0)]
    pars=[-1]*N
    depth=[-1]*N
    dist=[-1]*N
    while len(q):
        e,p,d,dis=q.pop()
        if depth[e]!=-1:continue
        pars[e]=p
        depth[e]=d
        dist[e]=dis
        for ne,c,w in edge[e]:
            q.append((ne,e,d+1,dis+w))
    return pars,depth,dist
pars,d,dist=dfs(0)
ln=N.bit_length()
dp=[[-1]*N for _ in range(ln+1)]
dp[0]=pars
for i in range(1,ln+1):
    for j in range(N):
        dp[i][j]=dp[i-1][dp[i-1][j]]



def lca(u, v):
    du = d[u]; dv = d[v]
    if du > dv:
        du, dv = dv, du
        u,v=v,u
    dif=dv-du
    for i in range(ln+1):
        if (dif>>i)&1:
            v=dp[i][v]
    if u==v:return u
    for i in range(ln,-1,-1):
        pu=dp[i][u];pv=dp[i][v]
        if pu!=pv:
            u,v=pu,pv
    return pars[u]

q=Q
qs = tuple(tuple(map(int, input().split())) for i in range(Q)) 
ans=[0]*Q
qn=[[] for _ in range(N)]
for i,(x,y,u,v) in enumerate(qs):
    a=lca(u-1,v-1)
    ans[i]=dist[u-1]+dist[v-1]-2*dist[a]
    qn[u-1].append((i,x-1,y,1))
    qn[v-1].append((i,x-1,y,1))
    qn[a].append((i,x-1,y,-2))

cc=[[0,0] for _ in range(N-1)]

dfq=[(0,None,0,-1)]
def dfs2(e,c,d,p):
    if c!=None:
        cc[c][0]+=1
        cc[c][1]+=d
    for qi,x,y,sgn in qn[e]:
        ans[qi]+=(y*cc[x][0]-cc[x][1])*sgn
    for ne,nc,nd in edge[e]:
        if ne==pars[e]:continue
        dfs2(ne,nc,nd,e)
    if c!=None:
        cc[c][0]-=1
        cc[c][1]-=d
dfs2(0,-1,0,None)
printl(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6+1) 


def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None



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




edge = [[] for i in range(N)]
for i in range(N-1):
    a,b,c,w = map(int,input().split())
    edge[a-1].append((b-1,c-1,w))
    edge[b-1].append((a-1,c-1,w)) 




def dfs(start):
    q=[(start,-1,0,0)]
    pars=[-1]*N
    depth=[-1]*N
    dist=[-1]*N
    while len(q):
        e,p,d,dis=q.pop()
        if depth[e]!=-1:continue
        pars[e]=p
        depth[e]=d
        dist[e]=dis
        for ne,c,w in edge[e]:
            q.append((ne,e,d+1,dis+w))
    return pars,depth,dist
pars,d,dist=dfs(0)
ln=N.bit_length()
dp=[[-1]*N for _ in range(ln+1)]
dp[0]=pars
for i in range(1,ln+1):
    for j in range(N):
        dp[i][j]=dp[i-1][dp[i-1][j]]



def lca(u, v):
    du = d[u]; dv = d[v]
    if du > dv:
        du, dv = dv, du
        u,v=v,u
    dif=dv-du
    for i in range(ln+1):
        if (dif>>i)&1:
            v=dp[i][v]
    if u==v:return u
    for i in range(ln,-1,-1):
        pu=dp[i][u];pv=dp[i][v]
        if pu!=pv:
            u,v=pu,pv
    return pars[u]

q=Q
qs = tuple(tuple(map(int, input().split())) for i in range(Q)) 
ans=[0]*Q
qn=[[] for _ in range(N)]
for i,(x,y,u,v) in enumerate(qs):
    ans[i]=dist[u-1]+dist[v-1]-2*dist[lca(u-1,v-1)]
    qn[u-1].append((i,x-1,y,1))
    qn[v-1].append((i,x-1,y,1))
    qn[lca(u-1,v-1)].append((i,x-1,y,-2))

cc=[[0,0] for _ in range(N-1)]

dfq=[(0,None,0,-1)]
def dfs2(e,c,d,p):
    if c!=None:
        cc[c][0]+=1
        cc[c][1]+=d
    for qi,x,y,sgn in qn[e]:
        ans[qi]+=(y*cc[x][0]-cc[x][1])*sgn
    for ne,nc,nd in edge[e]:
        if ne==pars[e]:continue
        dfs2(ne,nc,nd,e)
    if c!=None:
        cc[c][0]-=1
        cc[c][1]-=d
dfs2(0,-1,0,None)
printl(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6+1) 


def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None



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




edge = [[] for i in range(N)]
for i in range(N-1):
    a,b,c,w = map(int,input().split())
    edge[a-1].append((b-1,c-1,w))
    edge[b-1].append((a-1,c-1,w)) 




def dfs(start):
    q=[(start,-1,0,0)]
    pars=[-1]*N
    depth=[-1]*N
    dist=[-1]*N
    while len(q):
        e,p,d,dis=q.pop()
        if depth[e]!=-1:continue
        pars[e]=p
        depth[e]=d
        dist[e]=dis
        for ne,c,w in edge[e]:
            q.append((ne,e,d+1,dis+w))
    return pars,depth,dist
pars,d,dist=dfs(0)
ln=N.bit_length()
dp=[[-1]*N for _ in range(ln+1)]
dp[0]=pars
for i in range(1,ln+1):
    for j in range(N):
        dp[i][j]=dp[i-1][dp[i-1][j]]



def lca(u, v):
    du = d[u]; dv = d[v]
    if du > dv:
        du, dv = dv, du
        u,v=v,u
    dif=dv-du
    for i in range(ln+1):
        if (dif>>i)&1:
            v=dp[i][v]
    if u==v:return u
    for i in range(ln,-1,-1):
        pu=dp[i][u];pv=dp[i][v]
        if pu!=pv:
            u,v=pu,pv
    return pars[u]

q=Q
qs = tuple(tuple(map(int, input().split())) for i in range(Q)) 
ans=[0]*Q
qn=[[] for _ in range(N)]
for i,(x,y,u,v) in enumerate(qs):
    ans[i]=dist[u-1]+dist[v-1]-2*dist[lca(u-1,v-1)]
    qn[u-1].append((i,x-1,y,1))
    qn[v-1].append((i,x-1,y,1))
    qn[lca(u-1,v-1)].append((i,x-1,y,-2))
cnt=[0]*Q


qc=[[0,0] for _ in range(Q)]
cc=[[0,0] for _ in range(N-1)]

dfq=[(0,None,0,-1)]
def dfs2(e):
    for qi,x,y,sgn in qn[e]:
        ans[qi]+=(y*cc[x][0]-cc[x][1])*sgn
    for ne,c,nd in edge[e]:
        if ne==pars[e]:continue
        if c!=None:
            cc[c][0]+=1
            cc[c][1]+=nd
        dfs2(ne)
        if c!=None:
            cc[c][0]-=1
            cc[c][1]-=nd
dfs2(0)
printl(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6+1) 


def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None



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




edge = [[] for i in range(N)]
for i in range(N-1):
    a,b,c,w = map(int,input().split())
    edge[a-1].append((b-1,c-1,w))
    edge[b-1].append((a-1,c-1,w)) 




def dfs(start):
    q=[(start,-1,0,0)]
    pars=[-1]*N
    depth=[-1]*N
    dist=[-1]*N
    while len(q):
        e,p,d,dis=q.pop()
        if depth[e]!=-1:continue
        pars[e]=p
        depth[e]=d
        dist[e]=dis
        for ne,c,w in edge[e]:
            q.append((ne,e,d+1,dis+w))
    return pars,depth,dist
pars,d,dist=dfs(0)
ln=N.bit_length()
dp=[[-1]*N for _ in range(ln+1)]
dp[0]=pars
for i in range(1,ln+1):
    for j in range(N):
        dp[i][j]=dp[i-1][dp[i-1][j]]



def lca(u, v):
    du = d[u]; dv = d[v]
    if du > dv:
        du, dv = dv, du
        u,v=v,u
    dif=dv-du
    for i in range(ln+1):
        if (dif>>i)&1:
            v=dp[i][v]
    if u==v:return u
    for i in range(ln,-1,-1):
        pu=dp[i][u];pv=dp[i][v]
        if pu!=pv:
            u,v=pu,pv
    return pars[u]

q=Q



































n=N
A = [0]*q
C = [[] for _ in range(n)]
num = [0]*n
cum = [0]*n
for i in range(q):
  x, y, u, v = map(int, input().split())
  u -= 1
  v -= 1
  a = lca(u, v)
  C[u].append((i, x, y, 1))
  C[v].append((i, x, y, 1))
  C[a].append((i, x, y, -2))
dist = 0
stack = [0]
def dfs2(v):
  global dist
  for i, x, y, b in C[v]:
    A[i] += (dist + num[x]*y - cum[x]) * b
  for nv, c, d in edge[v]:
    c+=1
    if nv ==pars[v]:continue
    dist += d
    num[c] += 1
    cum[c] += d
    dfs2(nv)
    dist -= d
    num[c] -= 1
    cum[c] -= d
dfs2(0)
print(*A, sep="\n")

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

class LCA:
    def __init__(self, edge, root):
        self.l = len(edge)
        self.stack = []
        self.stack.append((root, 0))
        self.vs = []
        self.depth = [0]*self.l
        self.firstVisited = [-1]*self.l
        while self.stack:
            v, d = self.stack[-1]
            if self.firstVisited[v] == -1:
                self.firstVisited[v] = len(self.vs)
            self.vs.append(v)
            self.depth[v] = d
            if edge[v]:
                self.stack.append((edge[v].pop(), d+1))
            else:
                self.stack.pop()
        
        self.n = len(self.vs)
        self.INF = (self.l, self.l)
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [self.INF]*(self.N0 << 1)
        for i, v in enumerate(self.vs, self.N0):
            self.seg[i] = (self.depth[v], v)
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = min(self.seg[2*i], self.seg[2*i+1])
    
    def _query(self, l, r):
        res = self.INF
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = min(res, self.seg[r-1])
            if l & 1:
                res = min(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res

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

n, q = map(int, input().split())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b, c, d = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append((b, c, d))
  T[b].append((a, c, d))
G = [[] for _ in range(n)]
edge = [[] for _ in range(n)]
stack = [(0, -1)]
while stack:
  v, par = stack.pop()
  for nv, c, d in T[v]:
    if nv == par:
      continue
    G[v].append((nv, c, d))
    edge[v].append(nv)
    stack.append((nv, v))

seg = LCA(edge, 0)
A = [0]*q
C = [[] for _ in range(n)]
num = [0]*n
cum = [0]*n
for i in range(q):
  x, y, u, v = map(int, input().split())
  u -= 1
  v -= 1
  a = seg.query(u, v)
  C[u].append((i, x, y, 1))
  C[v].append((i, x, y, 1))
  C[a].append((i, x, y, -2))
dist = 0
stack = [0]
def dfs(v):
  global dist
  for i, x, y, b in C[v]:
    A[i] += (dist + num[x]*y - cum[x]) * b
  for nv, c, d in G[v]:
    dist += d
    num[c] += 1
    cum[c] += d
    dfs(nv)
    dist -= d
    num[c] -= 1
    cum[c] -= d
dfs(0)
print(*A, sep="\n")

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

class LCA:
    def __init__(self, edge, root):
        self.l = len(edge)
        self.stack = []
        self.stack.append((root, 0))
        self.vs = []
        self.depth = [0]*self.l
        self.firstVisited = [-1]*self.l
        while self.stack:
            v, d = self.stack[-1]
            if self.firstVisited[v] == -1:
                self.firstVisited[v] = len(self.vs)
            self.vs.append(v)
            self.depth[v] = d
            if edge[v]:
                self.stack.append((edge[v].pop(), d+1))
            else:
                self.stack.pop()
        
        self.n = len(self.vs)
        self.INF = (self.l, self.l)
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [self.INF]*(self.N0 << 1)
        for i, v in enumerate(self.vs, self.N0):
            self.seg[i] = (self.depth[v], v)
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = min(self.seg[2*i], self.seg[2*i+1])
    
    def _query(self, l, r):
        res = self.INF
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = min(res, self.seg[r-1])
            if l & 1:
                res = min(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res

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

n, q = map(int, input().split())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b, c, d = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append((b, c, d))
  T[b].append((a, c, d))
G = [[] for _ in range(n)]
edge = [[] for _ in range(n)]
stack = [(0, -1)]
while stack:
  v, par = stack.pop()
  for nv, c, d in T[v]:
    if nv == par:
      continue
    G[v].append((nv, c, d))
    edge[v].append(nv)
    stack.append((nv, v))

seg = LCA(edge, 0)
A = [0]*q
C = [[] for _ in range(n)]
num = [0]*n
cum = [0]*n
for i in range(q):
  x, y, u, v = map(int, input().split())
  u -= 1
  v -= 1
  a = seg.query(u, v)
  C[u].append((i, x, y, 1))
  C[v].append((i, x, y, 1))
  C[a].append((i, x, y, -2))
dist = 0
stack = [0]
def dfs(v):
  global dist
  for i, x, y, b in C[v]:
    A[i] += (dist + num[x]*y - cum[x]) * b
  for nv, c, d in G[v]:
    dist += d
    num[c] += 1
    cum[c] += d
    dfs(nv)
    dist -= d
    num[c] -= 1
    cum[c] -= d
dfs(0)
print(*A, sep="\n")