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: Runtime Error

Solution code:
from copy import deepcopy
from collections import deque

N,Q=map(int,input().split())
G=[{} for _ in range(N)]
for i in range(N-1):
  a,b,c,d = map(int,input().split())
  G[a-1][b-1] = (c,d)
  G[b-1][a-1] = (c,d)
  
# https://tjkendev.github.io/procon-library/python/graph/lca-dst.html
S = []
F = [0]*N
depth = [0]*N
seen = [0]*N
def dfs(v, d):
    F[v] = len(S)
    depth[v] = d
    seen[v] = 1
    S.append(v)
    for w in G[v].keys():
        if seen[w]:continue
        dfs(w, d+1)
        S.append(v)
dfs(0, 0)

# Disjoint Sparse Tableの構築
INF = (N, None)

LV = (2*N-1).bit_length()
N0 = 2**LV
table = [[None]*N0 for i in range(LV)]

S0 = [INF]*N0
for i, v in enumerate(S):
    S0[i] = (depth[v], v)

sz = N0; hf = N0 >> 1
for k in range(LV):
    table_k = table[k]
    for i in range(hf, N0, sz):
        table_k[i-1] = r = S0[i-1]
        for j in range(i-2, i-hf-1, -1):
            table_k[j] = r = min(S0[j], r)

        table_k[i] = r = S0[i]
        for j in range(i+1, i+hf):
            table_k[j] = r = min(S0[j], r)
    sz >>= 1; hf >>= 1

# LCAの計算
def query(u, v):
    if u == v:
        return u
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu

    k2 = (fu ^ fv).bit_length()
    table_l = table[LV - k2]
    ans = table_l[fu]
    if fv & ((1 << k2) - 1):
        ans = min(ans, table_l[fv])
    return ans[1]
  
def bfs(G,s):
    N = len(G)
    seen = [0]*N
    csum = [{} for _ in range(N)]
    cnum = [{} for _ in range(N)]
    d = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while todo:
      a = todo.popleft()
      for b in G[a].keys():
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d_ = G[a][b][1]
          d[b] = d[a] + d_
          c_ = G[a][b][0]
          csum[b] = deepcopy(csum[a])
          cnum[b] = deepcopy(cnum[a])
          if csum[b].get(c_):
            csum[b][c_] += d_
            cnum[b][c_] += 1
          else:
            csum[b][c_] = d_
            cnum[b][c_] = 1
    return csum,cnum,d
  
root = 0
csum,cnum,d = bfs(G,root)
ans = [0]*Q
xyuv = [tuple(map(int,input().split())) for _ in range(Q)]
for i,(x,y,u,v) in enumerate(xyuv):
  u,v = u-1,v-1
  w = query(u,v)
  cs1,cn1 = ((csum[u][x],cnum[u][x]) if csum[u].get(x) else (0,0))
  cs2,cn2 = ((csum[v][x],cnum[v][x]) if csum[v].get(x) else (0,0))
  cs3,cn3 = ((csum[w][x],cnum[w][x]) if csum[w].get(x) else (0,0))
  diff1 = cn1*y - cs1
  diff2 = cn2*y - cs2
  diff3 = cn3*y - cs3
  ans[i] = d[u]+diff1 - (d[w]+diff3) + d[v]+diff2 - (d[w]+diff3)
print(*ans,sep='\n')

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

from networkx import DiGraph, tree_all_pairs_lowest_common_ancestor

N, Q, *I = map(int, open(0).read().split())
ABCD, XYUV = I[:4 * (N - 1)], I[4 * (N - 1):]

E = [[] for _ in range(N)]
for a, b, c, d in zip(*[iter(ABCD)] * 4):
    E[a - 1].append((b - 1, c, d))
    E[b - 1].append((a - 1, c, d))

dep = [0] * N
dist = [0] * N
G = DiGraph()

S = [(0, -1)]
while S:
    cur, par = S.pop()
    for nxt, _, d in E[cur]:
        if nxt == par:
            continue

        G.add_edge(cur, nxt)
        dep[nxt] = 1 + dep[cur]
        dist[nxt] = d + dist[cur]
        S.append((nxt, cur))


lca = tree_all_pairs_lowest_common_ancestor(
    G, 0,
    ((u - 1, v - 1) for x, y, u, v in zip(*[iter(XYUV)] * 4))
)

memo = [[] for _ in range(N)]
ans = []
for i, (x, y, u, v) in enumerate(zip(*[iter(XYUV)] * 4)):
    u -= 1
    v -= 1

    (_, _), c = next(lca)

    ans.append(dist[u] + dist[v] - 2 * dist[c])

    memo[u].append((x, y, i))
    memo[v].append((x, y, i))
    memo[c].append((x, y, ~i))

c_sum = [0] * (N + 1)
c_num = [0] * (N + 1)
def solve(cur, par=-1):
    for c, val, i in memo[cur]:
        if i >= 0:
            ans[i] += c_num[c] * val - c_sum[c]
        else:
            ans[~i] += -2 * (c_num[c] * val - c_sum[c])

    for nxt, c, d in E[cur]:
        if nxt == par:
            continue

        c_sum[c] += d
        c_num[c] += 1
        solve(nxt, cur)
        c_num[c] -= 1
        c_sum[c] -= d
solve(0)

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5+5)
from collections import defaultdict,deque
input = sys.stdin.readline
class LCA:

    def __init__(self,n):
        self.size = n+1
        self.bitlen = n.bit_length()
        self.lca = [[0]*self.size for i in range(self.bitlen)]
        self.depth = [-1]*self.size
        self.dis = [-1]*self.size
        self.depth[1] = 0
        self.dis[1] = 0
    def make(self,root):
        q = deque([root])
        while q:
            now = q.popleft()
            for nex,c,w in e[now]:
                if self.depth[nex]>= 0:
                    continue
                self.depth[nex] = self.depth[now]+1
                self.dis[nex] = self.dis[now]+w
                self.lca[0][nex] = now
                q.append(nex)
        for i in range(1,self.bitlen):
            for j in range(self.size):
                if self.lca[i-1][j] > 0:
                    self.lca[i][j] = self.lca[i-1][self.lca[i-1][j]]
    
    def search(self,x,y):
        dx = self.depth[x]
        dy = self.depth[y]
        if dx < dy:
            x,y = y,x
            dx,dy = dy,dx
        dif = dx-dy
        while dif:
            s = dif & (-dif)
            x = self.lca[s.bit_length()-1][x]
            dif -= s
        while x != y:
            j = 0
            while self.lca[x][j] != self.lca[y][j]:
                j += 1
            if j == 0:
                return self.lca[x][0]
            x = self.lca[x][j-1]
            y = self.lca[y][j-1]
        return x

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

Q = [[] for i in range(n+1)]
ans = []
for i in range(q):
    x,y,u,v = map(int,input().split())
    a = lca.search(u,v)
    ans.append(lca.dis[u]+lca.dis[v]-2*lca.dis[a])
    Q[u].append((x,y,i,1))
    Q[v].append((x,y,i,1))
    Q[a].append((x,y,i,-2))


count = defaultdict(int)
weight = defaultdict(int)
def dfs1(now,p):
    for x,y,ind,z in Q[now]:
        ans[ind] += z*(y*count[x]-weight[x])
    for nex,c,w in e[now]:
        if nex == p:
            continue
        count[c] += 1
        weight[c] += w
        dfs1(nex,now)
        count[c] -= 1
        weight[c] -= w
    
dfs1(1,0)

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5+5)
from collections import defaultdict,deque
input = sys.stdin.readline

def bfs():
    q = deque([1])
    while q:
        now = q.popleft()
        for nex,c,w in e[now]:
            if depth[nex]>= 0:
                continue
            depth[nex] = depth[now]+1
            dis[nex] = dis[now]+w
            lca[0][nex] = now
            q.append(nex)

def dfs1(now,p,count1,count2):
    for cou in dcount[now]:
        dcount[now][cou] = count1[cou]
    for wei in dweight[now]:
        dweight[now][wei] = count2[wei]

    for nex,c,w in e[now]:
        if nex == p:
            continue
        count1[c] += 1
        count2[c] += w
        dfs1(nex,now,count1,count2)
        count1[c] -= 1
        count2[c] -= w
n,q = map(int,input().split())
e = [[] for i in range(n+1)]

for i in range(n-1):
    a,b,c,d = map(int,input().split())
    e[a].append((b,c,d))
    e[b].append((a,c,d))
size = n+1
bitlen = 19
lca = [[0]*size for i in range(bitlen)]
depth = [-1]*size
dis = [-1]*size
depth[1] = 0
dis[1] = 0

bfs()
for i in range(1,bitlen):
    for j in range(1,size):
        if lca[i-1][j] > 0:
            lca[i][j] = lca[i-1][lca[i-1][j]]
    
def search(x,y):
    dx = depth[x]
    dy = depth[y]
    if dx < dy:
        x,y = y,x
        dx,dy = dy,dx
    dif = dx-dy
    while dif:
        s = dif & (-dif)
        x = lca[s.bit_length()-1][x]
        dif -= s
    if x == y:
        return x
    for i in range(bitlen-1,-1,-1):
        if lca[i][x] != lca[i][y]:
            x = lca[i][x]
            y = lca[i][y]
    return lca[0][x]


Q = [[] for i in range(n+1)]
ans = []
for i in range(q):
    x,y,u,v = map(int,input().split())
    a = lca.search(u,v)
    ans.append(dis[u]+dis[v]-2*dis[a])
    Q[u].append((x,y,i,1))
    Q[v].append((x,y,i,1))
    Q[a].append((x,y,i,-2))


count = [0]*n
weight = [0]*n

def dfs1(now,p):
    for x,y,ind,z in Q[now]:
        ans[ind] += z*(y*count[x]-weight[x])
    for nex,c,w in e[now]:
        if nex == p:
            continue
        count[c] += 1
        weight[c] += w
        dfs1(nex,now)
        count[c] -= 1
        weight[c] -= w
    
dfs1(1,0)

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5+5)
from collections import defaultdict
input = sys.stdin.readline

n,q = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(n-1):
    a,b,c,d = map(int,input().split())
    e[a].append((b,c,d))
    e[b].append((a,c,d))
size = n+1
bitlen = n.bit_length()
lca = [[0]*size for i in range(bitlen)]
depth = [-1]*size
dis = [-1]*size
depth[1] = 0
dis[1] = 0
def dfs(now,par):
    for nex in e[now]:
        if nex[0] == par:
            continue
        depth[nex[0]] = depth[now]+1
        dis[nex[0]] = dis[now]+nex[2]
        lca[0][nex[0]] = now
        dfs(nex[0],now)

dfs(1,0)
for i in range(1,bitlen):
    for j in range(1,size):
        if lca[i-1][j] > 0:
            lca[i][j] = lca[i-1][lca[i-1][j]]
    
def search(x,y):
    dx = depth[x]
    dy = depth[y]
    if dx < dy:
        x,y = y,x
        dx,dy = dy,dx
    dif = dx-dy
    while dif:
        s = dif & (-dif)
        x = lca[x][s.bit_length()-1]
        dif -= s
    if x == y:
        return x
    for i in range(bitlen-1,-1,-1):
        if lca[x][i] != lca[y][i]:
            x = lca[x][i]
            y = lca[y][i]
    return lca[x][0]


Q = []
dcount = defaultdict(lambda : defaultdict(int))
dweight = defaultdict(lambda : defaultdict(int))
for i in range(q):
    x,y,u,v = map(int,input().split())
    a = search(u,v)
    dcount[u][x] = 0
    dcount[v][x] = 0
    dcount[a][x] = 0
    dweight[u][x] = 0
    dweight[v][x] = 0
    dweight[a][x] = 0
    Q.append((x,y,u,v,a))

def dfs1(now,p,count1,count2):
    for cou in dcount[now]:
        dcount[now][cou] = count1[cou]
    for wei in dweight[now]:
        dweight[now][wei] = count2[wei]

    for nex,c,w in e[now]:
        if nex == p:
            continue
        count1[c] += 1
        count2[c] += w
        dfs1(nex,now,count1,count2)
        count1[c] -= 1
        count2[c] -= w
    
dfs1(1,0,defaultdict(int),defaultdict(int))

for x,y,u,v,a in Q:
    cal = dis[u]+dis[v]-2*dis[a]
    cal += y*(dcount[u][x]+dcount[v][x]-2*dcount[a][x]) - dweight[u][x]-dweight[v][x]+2*dweight[a][x]
    print(cal)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5+5)
from collections import defaultdict
input = sys.stdin.readline

n,q = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(n-1):
    a,b,c,d = map(int,input().split())
    e[a].append((b,c,d))
    e[b].append((a,c,d))
size = n+1
bitlen = n.bit_length()
lca = [[0]*bitlen for i in range(size)]
depth = [-1]*size
def dfs(now,par,dep):
    if depth[now] >= 0:
        return depth[now]
    depth[now] = dep
    for nex in e[now]:
        if nex[0] == par or depth[nex[0]] >= 0:
            continue
        dfs(nex[0],now,dep+1)
    return depth[now]

dfs(root,0,0)
lca[0] = depth
for i in range(1,bitlen):
    for j in range(size):
        if lca[j][i-1] > 0:
            lca[j][i] = lca[lca[j][i-1]][i-1]
    
def search(x,y):
    dx = depth[x]
    dy = depth[y]
    if dx < dy:
        x,y = y,x
        dx,dy = dy,dx
    dif = dx-dy
    while dif:
        s = dif & (-dif)
        x = lca[x][s.bit_length()-1]
        dif -= s
    if x == y:
        return x
    for i in range(bitlen-1,-1,-1):
        if lca[x][i] != lca[y][i]:
            x = lca[x][i]
            y = lca[y][i]
        else:
            break
    return lca[x][0]


Q = []
dcount = defaultdict(lambda : defaultdict(int))
dweight = defaultdict(lambda : defaultdict(int))
for i in range(q):
    x,y,u,v = map(int,input().split())
    a = search(u,v)
    dcount[u][x] = 0
    dcount[v][x] = 0
    dcount[a][x] = 0
    dweight[u][x] = 0
    dweight[v][x] = 0
    dweight[a][x] = 0
    Q.append((x,y,u,v,a))

dis = [0]*(n+1)

def dfs1(now,p,count1,count2):
    for cou in dcount[now]:
        dcount[now][cou] = count1[cou]
    for wei in dweight[now]:
        dweight[now][wei] = count2[wei]

    for nex,c,w in e[now]:
        if nex == p:
            continue
        count1[c] += 1
        count2[c] += w
        dis[nex] =dis[now]+w
        dfs1(nex,now,count1,count2)
        count1[c] -= 1
        count2[c] -= w
    
dfs1(1,0,defaultdict(int),defaultdict(int))

for x,y,u,v,a in Q:
    cal = dis[u]+dis[v]-2*dis[a]
    cal += y*(dcount[u][x]+dcount[v][x]-2*dcount[a][x]) - dweight[u][x]-dweight[v][x]+2*dweight[a][x]
    print(cal)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
edge=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c,d=map(int1,input().split())
    d+=1
    edge[a].append((b,c,d))
    edge[b].append((a,c,d))
U=defaultdict(list)
V=defaultdict(list)
Query=[]
for i in range(Q):
    x,y,u,v=map(int1,input().split())
    Query.append((x,y,u,v))
    y+=1
    U[u].append((x,y,i))
    V[v].append((x,y,i))

diff=[0]*Q
S=[0]*(2*N-1)

def EulerTour(start,n,edges):
    used=[False]*n
    et=[]
    left=[-1]*n
    right=[-1]*n
    depth=[]
    stack=[(start,-1,-1)]
    cur_depth=-1
    col=[[0,0] for _ in range(N)]
    while stack:
        v,c,d=stack.pop()
        if et:
            S[len(et)]=S[len(et)-1]+d
        if v>=0:
            col[c][0]+=d
            col[c][1]+=1
            used[v]=True
            cur_depth+=1
            left[v]=right[v]=len(et)
            et.append(v)
            depth.append(cur_depth)
            for nv,c,d in edges[v]:
                if not used[nv]:
                    stack.append((~v,c,-d))
                    stack.append((nv,c,d))
        else:
            col[c][0]+=d
            col[c][1]-=1
            cur_depth-=1
            right[~v]=len(et)
            et.append(~v)
            depth.append(cur_depth)
        while U[v]:
            qc,qd,qi=U[v].pop()
            diff[qi]+=col[qc][0]-col[qc][1]*qd
        while V[v]:
            qc,qd,qi=V[v].pop()
            diff[qi]-=col[qc][0]-col[qc][1]*qd
    return left,depth

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

s=SegmentTree(2*N-1,lambda a,b:min(a,b,key=lambda t:t[0]),(INF,INF))
left,depth=EulerTour(0,N,edge)
for i in range(2*N-1):
    s.update(i,(depth[i],i))

for i,(x,y,u,v) in enumerate(Query):
    res=s.query(left[u],left[v]+1)
    print(S[left[v]]+S[left[u]]-S[res[1]]*2+diff[i])

Submission status: Runtime Error

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=[]
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=[[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(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)