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.



Sample input:
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:
130
200
60

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
inf = float('inf')
import sys
input = sys.stdin.readline

def dijkstra(ad_lst, n, s, g, x, y):
    costs = [inf for i in range(n+1)]
    costs[s], q = 0, []
    heappush(q, [costs[s], s])

    while q:
        c, u = heappop(q)
        for v, tmp in ad_lst[u].items():
            color, c = tmp
            if color == x:
                c = y
            if costs[u] + c < costs[v]:
                heappush(q, [costs[u] + c, v])
                costs[v] = costs[u] + c
        if costs[g] < inf:
            break
    return costs

def resolve():
    n, q = map(int, input().split())
    graph = {i+1: {} for i in range(n)}
    for i in range(n-1):
        a, b, c, d = map(int, input().split())
        graph[a][b] = graph[b][a] = [c, d]

    for _ in range(q):
        x, y, u, v = map(int, input().split())
        costs = dijkstra(graph, n, u, v, x, y)
        print(costs[v])


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys

input=sys.stdin.readline
sys.setrecursionlimit(10**7)

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

prv=[-1]*N
depth=[0]*N
dist=[0 for i in range(N)]
def dfs(v,pv):
    prv[v]=pv
    for nv,color,weight in edge[v]:
        if nv!=pv:
            depth[nv]=depth[v]+1
            dist[nv]=dist[v]+weight
            dfs(nv,v)

dfs(0,-1)

LV = (N-1).bit_length()
def construct(prv):
    kprv = [prv]
    S = prv
    for k in range(LV):
        T = [0]*N
        for i in range(N):
            if S[i] is None:
                continue
            T[i] = S[S[i]]
        kprv.append(T)
        S = T
    return kprv

kprv=construct(prv)

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

    # assert depth[u] <= depth[v]
    for k in range(LV+1):
        if dd & 1:
            v = kprv[k][v]
        dd >>= 1

    # assert depth[u] == depth[v]
    if u == v:
        return u

    for k in range(LV-1, -1, -1):
        pu = kprv[k][u]; pv = kprv[k][v]
        if pu != pv:
            u = pu; v = pv

    # assert kprv[0][u] == kprv[0][v]
    return kprv[0][u]

query=[]
q=[[] for i in range(N)]
data={}
for i in range(Q):
    x,y,u,v=map(int,input().split())
    LCA=lca(u-1,v-1)
    query.append((x,y,u-1,v-1,LCA))
    q[u-1].append(x)
    q[v-1].append(x)
    q[LCA].append(x)

num=[0 for i in range(N)]
cdist=[0 for i in range(N)]

def dfsc(v,pv,color,weight):
    pn=num[color]
    num[color]+=1
    pd=cdist[color]
    cdist[color]+=weight
    for x in q[v]:
        data[(v,x)]=(0,0)
        data[(v,x)]=(num[x],cdist[x])

    for nv,ncolor,nweight in edge[v]:
        if nv!=pv:
            dfsc(nv,v,ncolor,nweight)

    num[color]=pn
    cdist[color]=pd



dfsc(0,0,0,0)

for x,y,u,v,LCA in query:
    d1=dist[LCA]-data[(LCA,x)][1]+data[(LCA,x)][0]*y
    d2=dist[u]-data[(u,x)][1]+data[(u,x)][0]*y
    d3=dist[v]-data[(v,x)][1]+data[(v,x)][0]*y
    print(d2-d1+d3-d1)

Submission status: Time Limit Exceeded

Solution code:
import sys

input=sys.stdin.readline
sys.setrecursionlimit(10**7)

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

prv=[-1]*N
depth=[0]*N
def dfs(v,pv):
    prv[v]=pv
    for nv,color,weight in edge[v]:
        if nv!=pv:
            depth[nv]=depth[v]+1
            dfs(nv,v)

dfs(0,-1)

LV = (N-1).bit_length()
def construct(prv):
    kprv = [prv]
    S = prv
    for k in range(LV):
        T = [0]*N
        for i in range(N):
            if S[i] is None:
                continue
            T[i] = S[S[i]]
        kprv.append(T)
        S = T
    return kprv

kprv=construct(prv)

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

    # assert depth[u] <= depth[v]
    for k in range(LV+1):
        if dd & 1:
            v = kprv[k][v]
        dd >>= 1

    # assert depth[u] == depth[v]
    if u == v:
        return u

    for k in range(LV-1, -1, -1):
        pu = kprv[k][u]; pv = kprv[k][v]
        if pu != pv:
            u = pu; v = pv

    # assert kprv[0][u] == kprv[0][v]
    return kprv[0][u]

query=[]
q=[[] for i in range(N)]
data={}
for i in range(Q):
    x,y,u,v=map(int,input().split())
    query.append((x,y,u-1,v-1))
    q[u-1].append(x)
    q[v-1].append(x)
    LCA=lca(u-1,v-1)
    q[LCA].append(x)

num=[0 for i in range(N)]
dist=[0 for i in range(N)]

def dfsc(v,pv,color,weight):
    if pv!=-1:
        pn=num[color]
        num[color]+=1
        pd=dist[color]
        dist[color]+=weight
    for x in q[v]:
        data[(v,x)]=(0,0)
        data[(v,x)]=(num[x],dist[x])

    for nv,ncolor,nweight in edge[v]:
        if nv!=pv:
            dfsc(nv,v,ncolor,nweight)

    if pv!=-1:
        num[color]=pn
        dist[color]=pd


dfsc(0,-1,-1,-1)

dist=[0 for i in range(N)]

def dd(v,pv):
    for nv,color,weight in edge[v]:
        if nv!=pv:
            dist[nv]=dist[v]+weight
            dd(nv,v)

dd(0,-1)

for x,y,u,v in query:
    LCA=lca(u,v)
    d1=dist[LCA]-data[(LCA,x)][1]+data[(LCA,x)][0]*y
    d2=dist[u]-data[(u,x)][1]+data[(u,x)][0]*y
    d3=dist[v]-data[(v,x)][1]+data[(v,x)][0]*y
    print(d2-d1+d3-d1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

n, q = map(int, input().split())
edge = [list(map(int, input().split())) for i in range(n-1)]
query = [list(map(int, input().split())) + [i] for i in range(q)]

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

root = -1
for i in range(n+1):
    if len(g[i]) == 1:
        root = i
        break

q = [(root, 0, 0)]
tour = []
visit = [False for i in range(n+1)]
while q:
    now, c, d = q.pop()
    if now >= 0:
        visit[now] = True
        for next, next_c, next_d in g[now][::-1]:
            if not visit[next]:
                q.append((~now, next_c, next_d))
                q.append((next, next_c, next_d))

        tour.append((now, c, d))
    else:
        tour.append((~now, c, -d))

first = [-1]*(n+1)
pathcolor = [[] for i in range(n)]
tree = BIT(len(tour))

for i in range(len(tour)):
    v, c, d = tour[i]
    if first[v] == -1:
        first[v] = i
    pathcolor[c].append(i)
    tree.add(i+1, d)

q_color = [[] for i in range(n)]
for qu in query:
    q_color[qu[0]].append(qu)


ans = [None]*len(query)
for color in range(1, n):
    for x, y, u, v, ind in q_color[color]:
        change = []
        for i in pathcolor[color]:
            cost = y-tour[i][2]
            change.append(cost)
            tree.add(i+1, cost)
        u_i, v_i = first[u], first[v]
        if u_i > v_i:
            u_i, v_i = v_i, u_i
        ans[ind] = tree.sum(v_i+1)-tree.sum(u_i+1)
        for i in range(len(pathcolor[color])):
            tree.add(pathcolor[color][i]+1, -change[i])

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in 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 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={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    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 bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,init=True):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.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 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]

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    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]
    
    # return func of [l,r)
    def query(self,l,r):
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][r-(1<<N)])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][r-(1<<N)]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][r-(1<<N)]):
            b=a
        return b
    
    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,func=lambda prv_v,nx,dist:prv_v+dist)
tr.EulerTour(0)
dep=tr.depth
et=tr.ETtable
 
ad=[deque([0]) for i in range(n)]
an=[deque([0]) for i in range(n)]
index=[deque() 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(q):
    x,y,u,v=LI_()
    y+=1
    lca=tr.LCA(root,u,v)
    path=dist[u]+dist[v]-dist[lca]*2
    
    ui=min(bisect.bisect_left(index[x],tr.ETin[u]),len(index[x]))
    vi=min(bisect.bisect_left(index[x],tr.ETin[v]),len(index[x]))
    ai=min(bisect.bisect_left(index[x],tr.ETin[lca]),len(index[x]))
    
    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)

Submission status: Time Limit Exceeded

Solution code:
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in 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 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={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    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 bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,init=True):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+1,root_v=0):
        q=deque()
        q.append(x)
        depth=[None]*self.size
        depth[x]=root_v
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        depth[nb]=depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return depth
    
    def LCA_init(self,root):
        self.EulerTour(root,func=lambda prv,nx,dist:prv+dist,root_v=0)
        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)
        #show((xin,xout),(yin,yout),(a,b),id_of_min_dep_in_et)
        return self.ETtable[id_of_min_dep_in_et]

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    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]
    
    # return func of [l,r)
    def query(self,l,r):
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][r-(1<<N)])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][r-(1<<N)]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][r-(1<<N)]):
            b=a
        return b
    
    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,func=lambda prv_v,nx,dist:prv_v+dist)
dep=tr.EulerTour(root)
et=tr.ETtable

ad=[deque([0]) for i in range(n)]
an=[deque([0]) for i in range(n)]
index=[deque() 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(q):
    x,y,u,v=LI_()
    y+=1
    lca=tr.LCA(root,u,v)
    path=dist[u]+dist[v]-dist[lca]*2
    
    ui=min(bisect.bisect_left(index[x],tr.ETin[u]),len(index[x]))
    vi=min(bisect.bisect_left(index[x],tr.ETin[v]),len(index[x]))
    ai=min(bisect.bisect_left(index[x],tr.ETin[lca]),len(index[x]))
    
    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)