Problem p02986 (python)

Fixed submission:
import sys
from collections import defaultdict
readline = sys.stdin.readline
 
N, Q = map(int, readline().split())

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

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

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

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

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

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

    for i, v in enumerate(S):
        data[M0-1+i] = (depth[v], i)
    for i in range(M0-2, -1, -1):
        data[i] = min(data[2*i+1], data[2*i+2])

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

        minx = INF
        a, b = fu, fv+1
        a += M0; b += M0
        while a < b:
            if b & 1:
                b -= 1
                minx = min(minx, data[b-1])
            if a & 1:
                minx = min(minx, data[a-1])
                a += 1
            a >>= 1; b >>= 1
        cc = S[minx[1]]
        if lnc[x] == 0:
            diff = 0
        else:
            ll, mm, ms, lncc = iin[x], mmn[x], msn[x], lnc[x]-1
            uvcs = []
            for target_i in [F[u], F[v], F[cc]]:
                ind, lw, hw =  (lnc[x]-1)//2, 0, lnc[x]-1
                if target_i < F[ll[0]] or target_i >= F[ll[lncc]]:
                    uvcs.append((0,0))
                else:
                    while True:
                        if F[ll[ind]] <= target_i:
                            if target_i < F[ll[ind+1]]:
                                uvcs.append((mm[ind+1], ms[ind+1]))
                                break
                            ind, lw = (ind+1 + hw)//2, ind+1
                            continue
                        ind, hw = (ind-1 + lw)//2, ind-1
            diff = (uvcs[0][0] + uvcs[1][0] - 2 * uvcs[2][0]) * y - (uvcs[0][1] + uvcs[1][1] - 2 * uvcs[2][1])
        print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

if __name__ == '__main__':
    process()

Buggy submission (verdict: Runtime Error):
# ABC133 オイラーツアー
import sys
from collections import defaultdict
readline = sys.stdin.readline
N, Q = map(int, readline().split())

vs = set()
def dfs_w(v, d):

    S, F, depth, depthh = [], [None]+[0]*N, [-1] + [0]*N, [0] + [0]*N
    iin = [[(0, 0, 0)] for _ in range(N)]

    stack, path = [(1, 0, 0)], [0]
    while stack:
        v, cc, dpd = stack.pop()
        if v > 0:
            parent = path[-1]
            path.append(v)

            F[v] = len(S)
            depth[v], depthh[v] = depth[parent] + 1, depthh[parent] + dpd
            iin[cc].append((iin[cc][-1][0]+1, iin[cc][-1][1]+dpd, len(S)))

            S.append(v)
            for u, ucc, udpd in d[v]:
                if u in vs:
                    continue
                vs.add(u)
                stack += [(-v, ucc, udpd), (u, ucc, udpd)]
        else:
            path.pop()
            iin[cc].append((iin[cc][-1][0]-1, iin[cc][-1][1]-dpd, len(S)))
            S.append(v)

    return S, F, depth, depthh, iin

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

def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

def process():
    G = [set() for _ in range(N+1)]
    for _ in range(N-1):
        a, b, c, d = map(int, readline().split())
        G[a].add((b,c,d))
        G[b].add((a,c,d))

    S, F, depth, depthh, iin = dfs_w(1, G)

    stree = SegTree([(depth[abs(v)], i) for i, v in enumerate(S)], len(S), (N, None), min)
    for _ in range(Q):
        x, y, u, v = map(int, readline().split())
        fu, fv = sorted([F[u], F[v]])
        cc = abs(S[stree.query(fu, fv+1)[1]])

        (fuy, fuv, _), (fvy, fvv, _), (fccy, fccv, _) = [iin[x][bsearch(index, 0, len(iin[x])-1, lambda j: iin[x][j][2])] for index in [fu, fv, F[cc]]]
        r = depthh[u] + depthh[v] - 2*depthh[cc] + (fuy + fvy - 2 * fccy) * y - (fuv + fvv - 2 * fccv)
        print(r)

if __name__ == '__main__':
    process()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)
 
readline = sys.stdin.readline
write = sys.stdout.write
 
N = int(readline())
G = [None]*N
for v in range(N):
    k, *G[v] = map(int, readline().split())
print(G)
 
S = []
F = [0]*N
depth = [0]*N
def dfs(v, d):
    F[v] = len(S)
    depth[v] = d
    S.append(v)
    for w in G[v]:
        dfs(w, d+1)
        S.append(v)
dfs(0, 0)
 
 
INF = (N, None)
 
M = 2*N
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
 
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1
 
def query(a, b):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]
 
 
Q = int(readline())
ans = []
for q in range(Q):
    u, v = map(int, readline().split())
    ans.append(query(u, v))
write("\n".join(map(str, ans)))
write("\n")

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)
readline = sys.stdin.readline

N, Q = map(int, readline().split())
INF = (N, None)
M = 2*N
M0 = 2**(M-1).bit_length()
ii = -1

def dfs(bb, v, d, dd, cc, dpd, G, dp,
        S, F, w2i, depth, depthh, mmn, msn, iin):
    global ii
    ii += 1
    F[v] = ii
    depth[v] = d
    depthh[v] = dd
    S[ii] = v
    mmn[cc].append(mmn[cc][-1]+1)
    msn[cc].append(msn[cc][-1]+dpd)
    iin[cc].append(v)
    w2i[v] = ii
    for w in G[v]:
        if w == bb:
            continue
        cc, dpd = dp[(min(v,w), max(v,w))]
        dfs(v, w, d+1, dd+dpd, cc, dpd, G, dp,
        S, F, w2i, depth, depthh, mmn, msn, iin)
#        bb, v, d, dd = v, w, d+1, dd+dpd
        ii += 1
        S[ii] = v
        mmn[cc].append(mmn[cc][-1]-1)
        msn[cc].append(msn[cc][-1]-dpd)
        iin[cc].append(-w)
        w2i[-w] = ii

def _query(a, b, data):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1
 
def query(u, v, S, F, data):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1, data))[1]]

def b_s(ll, mm, ms, ind, lw, hw, target_i, lncc, w2i):
    if target_i < w2i[ll[0]] or target_i >= w2i[ll[lncc]]:
        return 0, 0
    while True:
        if w2i[ll[ind]] <= target_i:
            if target_i < w2i[ll[ind+1]]:
                return (mm[ind+1], ms[ind+1])
            ind, lw = (ind+1 + hw)//2, ind+1
            continue
        ind, hw = (ind-1 + lw)//2, ind-1

def iro(u, v, cc, x, y,
        mmn, msn, iin, lnc, w2i):
    u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[u], lnc[x]-1, w2i)
    v_n, v_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1, w2i)
    c_n, c_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[cc], lnc[x]-1, w2i)
    return (u_n + v_n - 2 * (c_n)) * y - (u_d + v_d - 2 * (c_d))


def main():
    G = [[] for _ in range(N)]
    dp = {}

    for v in range(N-1):
        a, b, c, d = map(int, readline().split())
        a, b = a-1, b-1
        G[a].append(b)
        G[b].append(a)
        dp[(min(a,b), max(a,b))] = c, d
     
    S, F, w2i = [0]*(2*N), [0]*N, [0]*(2*N)
    depth = depthh = [0]*N
    mmn, msn, iin = [[0] for _ in range(N)], [[0] for _ in range(N)], [[] for _ in range(N)]

    dfs(None, 0, 0, 0, 0,0,
            G, dp,
            S, F, w2i, depth, depthh, mmn, msn, iin)
    lnc = [len(x)-1 for x in mmn]
     
    data = [INF]*(2*M0)
    for i, v in enumerate(S):
        data[M0-1+i] = (depth[v], i)
    for i in range(M0-2, -1, -1):
        data[i] = min(data[2*i+1], data[2*i+2])
     

    for q in range(Q):
        x, y, u, v = map(int, readline().split())
        u, v = u-1, v-1
        cc = query(u, v, S, F, data)
        if lnc[x] == 0:
            diff = 0
        else:
            diff = iro(u, v, cc, x, y, mmn, msn, iin, lnc, w2i)
        print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)
 
readline = sys.stdin.readline
write = sys.stdout.write
 
N, Q = map(int, readline().split())
G = []
g = defaultdict(list)
dp = {}
cdd = {}

for v in range(N-1):
    a, b, c, d = map(int, readline().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)
    dp["{}-{}".format(min(a,b), max(a,b))] = d
    cdd["{}-{}".format(min(a,b), max(a,b))] = c
cc = set()
i = 0
imkr = set()
while True:
    cc.add(i)
    G.append([])
    for vv in g[i]:
        if vv not in cc:
            G[i].append(vv)
            imkr.add(vv)
    if len(imkr) == 0:
        break
    i = imkr.pop()
 
S = []
F = [0]*N
depth = [0]*N
depthh = [0]*N
vn = [[] for _ in range(N)]
sn = [[] for _ in range(N)]
iin = [[] for _ in range(N)]
aii = []
w2i = [0]*(2*N)

ii = 0
def dfs(bb, v, d, dd, cc, dpd):
    global ii
    F[v] = len(S)
    depth[v] = d
    depthh[v] = dd
    S.append(v)
    vn[cc].append(1)
    sn[cc].append(dpd)
    iin[cc].append(v)
    aii.append(v)
    w2i[v] = ii
    ii += 1
    for w in G[v]:
        nvn = cdd["{}-{}".format(min(v,w), max(v,w))]
        dpd = dp["{}-{}".format(min(v,w), max(v,w))]
        dfs(v, w, d+1, dd+dpd, nvn, dpd)
        S.append(v)
        vn[nvn].append(-1)
        sn[nvn].append(-dpd)
        iin[nvn].append(-w)
        aii.append(-w)
        w2i[-w] = ii
        ii += 1

dfs(None, 0, 0, 0, 0,0)
#print(S)
#print(vn)
#print(sn)
#print(iin)
#print(aii)
#print(w2i)
from itertools import accumulate
mmn = []
lnc = []
for vvv in vn:
    lnc.append(len(vvv))
    mmn.append(list(accumulate(vvv)))
msn = []
for vvv in sn:
    msn.append(list(accumulate(vvv)))
 
INF = (N, None)
 
M = 2*N
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
 
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1
 
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]

def b_s(ll, mm, ms, ind, lw, hw, target_i, lncc):
    if w2i[ll[ind]] <= target_i:
        if ind+1 >= len(ll):
            return 0, 0
        if target_i < w2i[ll[ind+1]]:
            return (mm[ind], ms[ind])
        return b_s(ll, mm, ms, (ind+1 + hw)//2, ind+1, hw, target_i, lncc)
    elif w2i[ll[ind]] > target_i:
        return b_s(ll, mm, ms, (ind + lw)//2, lw, ind-1, target_i, lncc)
    return 0, 0

def iro(u, v, cc, x, y):
    if w2i[u] < w2i[iin[x][0]]:
        u_n, u_d = 0, 0
    else:
        u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[u], lnc[x]-1)
    if w2i[v] < w2i[iin[x][0]]:
        v_n, v_d = 0, 0
    else:
        v_n, v_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1)
    if w2i[cc] < w2i[iin[x][0]]:
        c_n, c_d = 0, 0
    else:
        c_n, c_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[cc], lnc[x]-1)
    return (u_n + v_n - 2 * (c_n)) * y - (u_d + v_d - 2 * (c_d))

 
 
#x = 2
#u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[2], lnc[x]-1)
#print(u_n, u_d)
#sys.exit()
for q in range(Q):
    x, y, u, v = map(int, readline().split())
    u, v = u-1, v-1
    cc = query(u, v)
    diff = 0
    if lnc[x] == 0:
        diff = 0
    else:
        diff = iro(u, v, cc, x, y)
#    print("query, col : {} v_ind : {}".format(x, v), b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1))
    print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)
 
readline = sys.stdin.readline
write = sys.stdout.write
 
N, Q = map(int, readline().split())
G = []
g = defaultdict(list)
dp = {}
cdd = {}

for v in range(N-1):
    a, b, c, d = map(int, readline().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)
    dp["{}-{}".format(min(a,b), max(a,b))] = d
    cdd["{}-{}".format(min(a,b), max(a,b))] = c
cc = set()
for i in range(N):
    cc.add(i)
    G.append([])
    for vv in g[i]:
        if vv not in cc:
            G[i].append(vv)
 
S = []
F = [0]*N
depth = [0]*N
depthh = [0]*N
vn = [[] for _ in range(N)]
sn = [[] for _ in range(N)]
iin = [[] for _ in range(N)]
aii = []
w2i = {}

ii = 0
def dfs(bb, v, d, dd, cc, dpd):
    global ii
    F[v] = len(S)
    depth[v] = d
    depthh[v] = dd
    S.append(v)
    vn[cc].append(1)
    sn[cc].append(dpd)
    iin[cc].append(v)
    aii.append(v)
    w2i[v] = ii
    ii += 1
    for w in G[v]:
        nvn = cdd["{}-{}".format(min(v,w), max(v,w))]
        dpd = dp["{}-{}".format(min(v,w), max(v,w))]
        dfs(v, w, d+1, dd+dpd, nvn, dpd)
        S.append(v)
        vn[nvn].append(-1)
        sn[nvn].append(-dpd)
        iin[nvn].append(-w)
        aii.append(-w)
        w2i[-w] = ii
        ii += 1

dfs(None, 0, 0, 0, 0,0)
#print(S)
#print(vn)
#print(sn)
#print(iin)
#print(aii)
#print(w2i)
from itertools import accumulate
mmn = []
lnc = []
for vvv in vn:
    lnc.append(len(vvv))
    mmn.append(list(accumulate(vvv)))
msn = []
for vvv in sn:
    msn.append(list(accumulate(vvv)))
 
INF = (N, None)
 
M = 2*N
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
 
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1
 
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]

def b_s(ll, mm, ms, ind, lw, hw, target_i, lncc):
    return 0, 0
    if w2i[ll[ind]] <= target_i:
        if ind+1 >= len(ll):
            return 0, 0
        if target_i < w2i[ll[ind+1]]:
            return (mm[ind], ms[ind])
        return b_s(ll, mm, ms, (ind+1 + hw)//2, ind+1, hw, target_i, lncc)
    elif w2i[ll[ind]] > target_i:
        return b_s(ll, mm, ms, (ind + lw)//2, lw, ind-1, target_i, lncc)
    return 0, 0

def iro(u, v, cc, x, y):
    nv = w2i[u], w2i[v]
    return 0
    if w2i[u] < w2i[iin[x][0]]:
        u_n, u_d = 0, 0
    else:
        u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[u], lnc[x]-1)
    if w2i[v] < w2i[iin[x][0]]:
        v_n, v_d = 0, 0
    else:
        v_n, v_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1)
    if w2i[cc] < w2i[iin[x][0]]:
        c_n, c_d = 0, 0
    else:
        c_n, c_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[cc], lnc[x]-1)
    return (u_n + v_n - 2 * (c_n)) * y - (u_d + v_d - 2 * (c_d))

 
 
#x = 2
#u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[2], lnc[x]-1)
#print(u_n, u_d)
#sys.exit()
for q in range(Q):
    x, y, u, v = map(int, readline().split())
    u, v = u-1, v-1
    cc = query(u, v)
    diff = 0
    if lnc[x] == 0:
        diff = 0
    else:
        diff = iro(u, v, cc, x, y)
#    print("query, col : {} v_ind : {}".format(x, v), b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1))
    print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)
 
readline = sys.stdin.readline
write = sys.stdout.write
 
N, Q = map(int, readline().split())
G = []
g = defaultdict(list)
dp = {}
cdd = {}

for v in range(N-1):
    a, b, c, d = map(int, readline().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)
    dp["{}-{}".format(min(a,b), max(a,b))] = d
    cdd["{}-{}".format(min(a,b), max(a,b))] = c
cc = set()
for i in range(N):
    cc.add(i)
    G.append([])
    for vv in g[i]:
        if vv not in cc:
            G[i].append(vv)
 
S = []
F = [0]*N
depth = [0]*N
depthh = [0]*N
vn = [[] for _ in range(N)]
sn = [[] for _ in range(N)]
iin = [[] for _ in range(N)]
aii = []
w2i = {}

ii = 0
def dfs(bb, v, d, dd, cc, dpd):
    global ii
    F[v] = len(S)
    depth[v] = d
    depthh[v] = dd
    S.append(v)
    vn[cc].append(1)
    sn[cc].append(dpd)
    iin[cc].append(v)
    aii.append(v)
    w2i[v] = ii
    ii += 1
    for w in G[v]:
        nvn = cdd["{}-{}".format(min(v,w), max(v,w))]
        dpd = dp["{}-{}".format(min(v,w), max(v,w))]
        dfs(v, w, d+1, dd+dpd, nvn, dpd)
        S.append(v)
        vn[nvn].append(-1)
        sn[nvn].append(-dpd)
        iin[nvn].append(-w)
        aii.append(-w)
        w2i[-w] = ii
        ii += 1

dfs(None, 0, 0, 0, 0,0)
#print(S)
#print(vn)
#print(sn)
#print(iin)
#print(aii)
#print(w2i)
from itertools import accumulate
mmn = []
lnc = []
for vvv in vn:
    lnc.append(len(vvv))
    mmn.append(list(accumulate(vvv)))
msn = []
for vvv in sn:
    msn.append(list(accumulate(vvv)))
 
INF = (N, None)
 
M = 2*N
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
 
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1
 
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]

def b_s(ll, mm, ms, ind, lw, hw, target_i, lncc):
    return 0, 0
    if w2i[ll[ind]] <= target_i:
        if ind+1 >= len(ll):
            return 0, 0
        if target_i < w2i[ll[ind+1]]:
            return (mm[ind], ms[ind])
        return b_s(ll, mm, ms, (ind+1 + hw)//2, ind+1, hw, target_i, lncc)
    elif w2i[ll[ind]] > target_i:
        return b_s(ll, mm, ms, (ind + lw)//2, lw, ind-1, target_i, lncc)
    return 0, 0

def iro(u, v, cc, x, y):
    nv = w2i[u], w2i[v], w2i[cc]
    return 0
    if w2i[u] < w2i[iin[x][0]]:
        u_n, u_d = 0, 0
    else:
        u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[u], lnc[x]-1)
    if w2i[v] < w2i[iin[x][0]]:
        v_n, v_d = 0, 0
    else:
        v_n, v_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1)
    if w2i[cc] < w2i[iin[x][0]]:
        c_n, c_d = 0, 0
    else:
        c_n, c_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[cc], lnc[x]-1)
    return (u_n + v_n - 2 * (c_n)) * y - (u_d + v_d - 2 * (c_d))

 
 
#x = 2
#u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[2], lnc[x]-1)
#print(u_n, u_d)
#sys.exit()
for q in range(Q):
    x, y, u, v = map(int, readline().split())
    u, v = u-1, v-1
    cc = query(u, v)
    diff = 0
    if lnc[x] == 0:
        diff = 0
    else:
        diff = iro(u, v, cc, x, y)
#    print("query, col : {} v_ind : {}".format(x, v), b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1))
    print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)
 
readline = sys.stdin.readline
write = sys.stdout.write
 
N, Q = map(int, readline().split())
G = []
g = defaultdict(list)
dp = {}
cdd = {}

for v in range(N-1):
    a, b, c, d = map(int, readline().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)
    dp["{}-{}".format(min(a,b), max(a,b))] = d
    cdd["{}-{}".format(min(a,b), max(a,b))] = c
cc = set()
for i in range(N):
    cc.add(i)
    G.append([])
    for vv in g[i]:
        if vv not in cc:
            G[i].append(vv)
 
S = []
F = [0]*N
depth = [0]*N
depthh = [0]*N
vn = [[] for _ in range(N)]
sn = [[] for _ in range(N)]
iin = [[] for _ in range(N)]
aii = []
w2i = {}

ii = 0
def dfs(bb, v, d, dd, cc, dpd):
    global ii
    F[v] = len(S)
    depth[v] = d
    depthh[v] = dd
    S.append(v)
    vn[cc].append(1)
    sn[cc].append(dpd)
    iin[cc].append(v)
    aii.append(v)
    w2i[v] = ii
    ii += 1
    for w in G[v]:
        nvn = cdd["{}-{}".format(min(v,w), max(v,w))]
        dpd = dp["{}-{}".format(min(v,w), max(v,w))]
        dfs(v, w, d+1, dd+dpd, nvn, dpd)
        S.append(v)
        vn[nvn].append(-1)
        sn[nvn].append(-dpd)
        iin[nvn].append(-w)
        aii.append(-w)
        w2i[-w] = ii
        ii += 1

dfs(None, 0, 0, 0, 0,0)
#print(S)
#print(vn)
#print(sn)
#print(iin)
#print(aii)
#print(w2i)
from itertools import accumulate
mmn = []
lnc = []
for vvv in vn:
    lnc.append(len(vvv))
    mmn.append(list(accumulate(vvv)))
msn = []
for vvv in sn:
    msn.append(list(accumulate(vvv)))
 
INF = (N, None)
 
M = 2*N
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
 
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1
 
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]

def b_s(ll, mm, ms, ind, lw, hw, target_i, lncc):
    return 0, 0
    if w2i[ll[ind]] <= target_i:
        if ind+1 >= len(ll):
            return 0, 0
        if target_i < w2i[ll[ind+1]]:
            return (mm[ind], ms[ind])
        return b_s(ll, mm, ms, (ind+1 + hw)//2, ind+1, hw, target_i, lncc)
    elif w2i[ll[ind]] > target_i:
        return b_s(ll, mm, ms, (ind + lw)//2, lw, ind-1, target_i, lncc)
    return 0, 0

def iro(u, v, cc, x, y):
    u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[u], lnc[x]-1)
    v_n, v_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1)
    c_n, c_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[cc], lnc[x]-1)
    return (u_n + v_n - 2 * (c_n)) * y - (u_d + v_d - 2 * (c_d))

 
 
#x = 2
#u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[2], lnc[x]-1)
#print(u_n, u_d)
#sys.exit()
for q in range(Q):
    x, y, u, v = map(int, readline().split())
    u, v = u-1, v-1
    cc = query(u, v)
    diff = 0
    if lnc[x] == 0:
        diff = 0
    else:
        diff = iro(u, v, cc, x, y)
#    print("query, col : {} v_ind : {}".format(x, v), b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1))
    print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)
 
readline = sys.stdin.readline
write = sys.stdout.write
 
N, Q = map(int, readline().split())
G = []
g = defaultdict(list)
dp = {}
cdd = {}

for v in range(N-1):
    a, b, c, d = map(int, readline().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)
    dp["{}-{}".format(min(a,b), max(a,b))] = d
    cdd["{}-{}".format(min(a,b), max(a,b))] = c
cc = set()
for i in range(N):
    cc.add(i)
    G.append([])
    for vv in g[i]:
        if vv not in cc:
            G[i].append(vv)
 
S = []
F = [0]*N
depth = [0]*N
depthh = [0]*N
vn = [[] for _ in range(N)]
sn = [[] for _ in range(N)]
iin = [[] for _ in range(N)]
aii = []
w2i = {}

ii = 0
def dfs(bb, v, d, dd, cc, dpd):
    global ii
    F[v] = len(S)
    depth[v] = d
    depthh[v] = dd
    S.append(v)
    vn[cc].append(1)
    sn[cc].append(dpd)
    iin[cc].append(v)
    aii.append(v)
    w2i[v] = ii
    ii += 1
    for w in G[v]:
        nvn = cdd["{}-{}".format(min(v,w), max(v,w))]
        dpd = dp["{}-{}".format(min(v,w), max(v,w))]
        dfs(v, w, d+1, dd+dpd, nvn, dpd)
        S.append(v)
        vn[nvn].append(-1)
        sn[nvn].append(-dpd)
        iin[nvn].append(-w)
        aii.append(-w)
        w2i[-w] = ii
        ii += 1

dfs(None, 0, 0, 0, 0,0)
#print(S)
#print(vn)
#print(sn)
#print(iin)
#print(aii)
#print(w2i)
from itertools import accumulate
mmn = []
lnc = []
for vvv in vn:
    lnc.append(len(vvv))
    mmn.append(list(accumulate(vvv)))
msn = []
for vvv in sn:
    msn.append(list(accumulate(vvv)))
 
INF = (N, None)
 
M = 2*N
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
 
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1
 
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]

def b_s(ll, mm, ms, ind, lw, hw, target_i, lncc):
    return 0, 0
    if w2i[ll[ind]] <= target_i:
        if ind+1 >= len(ll):
            return 0, 0
        if target_i < w2i[ll[ind+1]]:
            return (mm[ind], ms[ind])
        return b_s(ll, mm, ms, (ind+1 + hw)//2, ind+1, hw, target_i, lncc)
    elif w2i[ll[ind]] > target_i:
        return b_s(ll, mm, ms, (ind + lw)//2, lw, ind-1, target_i, lncc)
    return 0, 0

def iro(u, v, cc, x, y):
    if w2i[u] < w2i[iin[x][0]]:
        u_n, u_d = 0, 0
    else:
        u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[u], lnc[x]-1)
    if w2i[v] < w2i[iin[x][0]]:
        v_n, v_d = 0, 0
    else:
        v_n, v_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1)
    if w2i[cc] < w2i[iin[x][0]]:
        c_n, c_d = 0, 0
    else:
        c_n, c_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[cc], lnc[x]-1)
    return (u_n + v_n - 2 * (c_n)) * y - (u_d + v_d - 2 * (c_d))

 
 
#x = 2
#u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[2], lnc[x]-1)
#print(u_n, u_d)
#sys.exit()
for q in range(Q):
    x, y, u, v = map(int, readline().split())
    u, v = u-1, v-1
    cc = query(u, v)
    diff = 0
    if lnc[x] == 0:
        diff = 0
    else:
        diff = iro(u, v, cc, x, y)
#    print("query, col : {} v_ind : {}".format(x, v), b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1))
    print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)
 
readline = sys.stdin.readline
write = sys.stdout.write
 
N, Q = map(int, readline().split())
G = []
g = defaultdict(list)
dp = {}
cdd = {}

for v in range(N-1):
    a, b, c, d = map(int, readline().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)
    dp["{}-{}".format(min(a,b), max(a,b))] = d
    cdd["{}-{}".format(min(a,b), max(a,b))] = c
cc = set()
for i in range(N):
    cc.add(i)
    G.append([])
    for vv in g[i]:
        if vv not in cc:
            G[i].append(vv)
 
S = []
F = [0]*N
depth = [0]*N
depthh = [0]*N
vn = [[] for _ in range(N)]
sn = [[] for _ in range(N)]
iin = [[] for _ in range(N)]
aii = []
w2i = {}

ii = 0
def dfs(bb, v, d, dd, cc, dpd):
    global ii
    F[v] = len(S)
    depth[v] = d
    depthh[v] = dd
    S.append(v)
    vn[cc].append(1)
    sn[cc].append(dpd)
    iin[cc].append(v)
    aii.append(v)
    w2i[v] = ii
    ii += 1
    for w in G[v]:
        nvn = cdd["{}-{}".format(min(v,w), max(v,w))]
        dpd = dp["{}-{}".format(min(v,w), max(v,w))]
        dfs(v, w, d+1, dd+dpd, nvn, dpd)
        S.append(v)
        vn[nvn].append(-1)
        sn[nvn].append(-dpd)
        iin[nvn].append(-w)
        aii.append(-w)
        w2i[-w] = ii
        ii += 1

dfs(None, 0, 0, 0, 0,0)
#print(S)
#print(vn)
#print(sn)
#print(iin)
#print(aii)
#print(w2i)
from itertools import accumulate
mmn = []
lnc = []
for vvv in vn:
    lnc.append(len(vvv))
    mmn.append(list(accumulate(vvv)))
msn = []
for vvv in sn:
    msn.append(list(accumulate(vvv)))
 
INF = (N, None)
 
M = 2*N
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
 
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1
 
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]

def b_s(ll, mm, ms, ind, lw, hw, target_i, lncc):
    if w2i[ll[ind]] <= target_i:
        if ind+1 >= len(ll):
            return 0, 0
        if target_i < w2i[ll[ind+1]]:
            return (mm[ind], ms[ind])
        return b_s(ll, mm, ms, (ind+1 + hw)//2, ind+1, hw, target_i, lncc)
    elif w2i[ll[ind]] > target_i:
        return b_s(ll, mm, ms, (ind + lw)//2, lw, ind-1, target_i, lncc)
    return 0, 0

def iro(u, v, cc, x, y):
    if w2i[u] < w2i[iin[x][0]]:
        u_n, u_d = 0, 0
    else:
        u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[u], lnc[x]-1)
    if w2i[v] < w2i[iin[x][0]]:
        v_n, v_d = 0, 0
    else:
        v_n, v_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1)
    if w2i[cc] < w2i[iin[x][0]]:
        c_n, c_d = 0, 0
    else:
        c_n, c_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[cc], lnc[x]-1)
    return (u_n + v_n - 2 * (c_n)) * y - (u_d + v_d - 2 * (c_d))

 
 
#x = 2
#u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[2], lnc[x]-1)
#print(u_n, u_d)
#sys.exit()
for q in range(Q):
    x, y, u, v = map(int, readline().split())
    u, v = u-1, v-1
    cc = query(u, v)
    diff = 0
    if lnc[x] == 0:
        diff = 0
    else:
        diff = iro(u, v, cc, x, y)
#    print("query, col : {} v_ind : {}".format(x, v), b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1))
    print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)
 
readline = sys.stdin.readline
write = sys.stdout.write
 
N, Q = map(int, readline().split())
G = []
g = defaultdict(list)
dp = {}
cdd = {}

for v in range(N-1):
    a, b, c, d = map(int, readline().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)
    dp["{}-{}".format(min(a,b), max(a,b))] = d
    cdd["{}-{}".format(min(a,b), max(a,b))] = c
cc = set()
for i in range(N):
    cc.add(i)
    G.append([])
    for vv in g[i]:
        if vv not in cc:
            G[i].append(vv)
 
S = []
F = [0]*N
depth = [0]*N
depthh = [0]*N
vn = [[] for _ in range(N)]
sn = [[] for _ in range(N)]
iin = [[] for _ in range(N)]
aii = []
w2i = {}

ii = 0
def dfs(bb, v, d, dd, cc, dpd):
    global ii
    F[v] = len(S)
    depth[v] = d
    depthh[v] = dd
    S.append(v)
    vn[cc].append(1)
    sn[cc].append(dpd)
    iin[cc].append(v)
    aii.append(v)
    w2i[v] = ii
    ii += 1
    for w in G[v]:
        nvn = cdd["{}-{}".format(min(v,w), max(v,w))]
        dpd = dp["{}-{}".format(min(v,w), max(v,w))]
        dfs(v, w, d+1, dd+dpd, nvn, dpd)
        S.append(v)
        vn[nvn].append(-1)
        sn[nvn].append(-dpd)
        iin[nvn].append(-w)
        aii.append(-w)
        w2i[-w] = ii
        ii += 1

dfs(None, 0, 0, 0, 0,0)
#print(S)
#print(vn)
#print(sn)
#print(iin)
#print(aii)
#print(w2i)
from itertools import accumulate
mmn = []
lnc = []
for vvv in vn:
    lnc.append(len(vvv))
    mmn.append(list(accumulate(vvv)))
msn = []
for vvv in sn:
    msn.append(list(accumulate(vvv)))
 
INF = (N, None)
 
M = 2*N
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
 
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1
 
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]

def b_s(ll, mm, ms, ind, lw, hw, target_i, lncc):
    if w2i[ll[ind]] <= target_i:
        if ind+1 >= len(ll):
            return 0, 0
        if target_i < w2i[ll[ind+1]]:
            return (mm[ind], ms[ind])
        return b_s(ll, mm, ms, (ind+1 + hw)//2, ind+1, hw, target_i, lncc)
    elif w2i[ll[ind]] > target_i:
        return b_s(ll, mm, ms, (ind + lw)//2, lw, ind-1, target_i, lncc)

def iro(u, v, cc, x, y):
    if w2i[u] < w2i[iin[x][0]]:
        u_n, u_d = 0, 0
    else:
        u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[u], lnc[x]-1)
    if w2i[v] < w2i[iin[x][0]]:
        v_n, v_d = 0, 0
    else:
        v_n, v_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1)
    if w2i[cc] < w2i[iin[x][0]]:
        c_n, c_d = 0, 0
    else:
        c_n, c_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[cc], lnc[x]-1)
    return (u_n + v_n - 2 * (c_n)) * y - (u_d + v_d - 2 * (c_d))

 
 
#x = 2
#u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[2], lnc[x]-1)
#print(u_n, u_d)
#sys.exit()
for q in range(Q):
    x, y, u, v = map(int, readline().split())
    u, v = u-1, v-1
    cc = query(u, v)
    diff = 0
    if lnc[x] == 0:
        diff = 0
    else:
        diff = iro(u, v, cc, x, y)
#    print("query, col : {} v_ind : {}".format(x, v), b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1))
    print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)
 
readline = sys.stdin.readline
write = sys.stdout.write
 
N, Q = map(int, readline().split())
G = []
g = defaultdict(list)
dp = {}
cdd = {}

for v in range(N-1):
    a, b, c, d = map(int, readline().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)
    dp["{}-{}".format(min(a,b), max(a,b))] = d
    cdd["{}-{}".format(min(a,b), max(a,b))] = c
cc = set()
for i in range(N):
    cc.add(i)
    G.append([])
    for vv in g[i]:
        if vv not in cc:
            G[i].append(vv)
 
S = []
F = [0]*N
depth = [0]*N
depthh = [0]*N
vn = [[] for _ in range(N)]
sn = [[] for _ in range(N)]
iin = [[] for _ in range(N)]
aii = []
w2i = {}

ii = 0
def dfs(bb, v, d, dd, cc, dpd):
    global ii
    F[v] = len(S)
    depth[v] = d
    depthh[v] = dd
    S.append(v)
    vn[cc].append(1)
    sn[cc].append(dpd)
    iin[cc].append(v)
    aii.append(v)
    w2i[v] = ii
    ii += 1
    for w in G[v]:
        nvn = cdd["{}-{}".format(min(v,w), max(v,w))]
        dpd = dp["{}-{}".format(min(v,w), max(v,w))]
        dfs(v, w, d+1, dd+dpd, nvn, dpd)
        S.append(v)
        vn[nvn].append(-1)
        sn[nvn].append(-dpd)
        iin[nvn].append(-w)
        aii.append(-w)
        w2i[-w] = ii
        ii += 1

dfs(None, 0, 0, 0, 0,0)
#print(S)
#print(vn)
#print(sn)
#print(iin)
#print(aii)
#print(w2i)
from itertools import accumulate
mmn = []
lnc = []
for vvv in vn:
    lnc.append(len(vvv))
    mmn.append(list(accumulate(vvv)))
msn = []
for vvv in sn:
    msn.append(list(accumulate(vvv)))
 
INF = (N, None)
 
M = 2*N
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
 
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1
 
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]

def b_s(ll, mm, ms, ind, lw, hw, target_i, lncc):
    if w2i[ll[ind]] <= target_i:
        if ind + 1 > lncc:
            #print("xx")
            #print(mm, ms)
            return (mm[hw], ms[hw])
        if target_i < w2i[ll[ind+1]]:
            return (mm[ind], ms[ind])
        return b_s(ll, mm, ms, (ind + hw)//2, ind, hw, target_i, lncc)
    elif w2i[ll[ind]] > target_i:
        if ind == 0:
            return 0, 0
        return b_s(ll, mm, ms, (ind + lw)//2, lw, ind, target_i, lncc)

def iro(u, v, cc, x, y):
    u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[u], lnc[x]-1)
    v_n, v_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1)
    c_n, c_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[cc], lnc[x]-1)
    return (u_n + v_n - 2 * (c_n)) * y - (u_d + v_d - 2 * (c_d))

 
 
ans = []
#x = 2
#u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[2], lnc[x]-1)
#print(u_n, u_d)
#sys.exit()
for q in range(Q):
    x, y, u, v = map(int, readline().split())
    u, v = u-1, v-1
    cc = query(u, v)
#    if lnc[x] == 0:
#        diff = 0
#    else:
#        diff = iro(u, v, cc, x, y)
#    print("query, col : {} v_ind : {}".format(x, v), b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1))
    print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)
 
readline = sys.stdin.readline
write = sys.stdout.write
 
N, Q = map(int, readline().split())
G = []
g = defaultdict(list)
dp = {}
cdd = {}

for v in range(N-1):
    a, b, c, d = map(int, readline().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)
    dp["{}-{}".format(min(a,b), max(a,b))] = d
    cdd["{}-{}".format(min(a,b), max(a,b))] = c
cc = set()
for i in range(N):
    cc.add(i)
    G.append([])
    for vv in g[i]:
        if vv not in cc:
            G[i].append(vv)
 
S = []
F = [0]*N
depth = [0]*N
depthh = [0]*N
vn = [[] for _ in range(N)]
sn = [[] for _ in range(N)]
iin = [[] for _ in range(N)]
aii = []
w2i = {}

ii = 0
def dfs(bb, v, d, dd, cc, dpd):
    global ii
    F[v] = len(S)
    depth[v] = d
    depthh[v] = dd
    S.append(v)
    vn[cc].append(1)
    sn[cc].append(dpd)
    iin[cc].append(v)
    aii.append(v)
    w2i[v] = ii
    ii += 1
    for w in G[v]:
        nvn = cdd["{}-{}".format(min(v,w), max(v,w))]
        dpd = dp["{}-{}".format(min(v,w), max(v,w))]
        dfs(v, w, d+1, dd+dpd, nvn, dpd)
        S.append(v)
        vn[nvn].append(-1)
        sn[nvn].append(-dpd)
        iin[nvn].append(-w)
        aii.append(-w)
        w2i[-w] = ii
        ii += 1

dfs(None, 0, 0, 0, 0,0)
#print(S)
#print(vn)
#print(sn)
#print(iin)
#print(aii)
#print(w2i)
from itertools import accumulate
mmn = []
lnc = []
for vvv in vn:
    lnc.append(len(vvv))
    mmn.append(list(accumulate(vvv)))
msn = []
for vvv in sn:
    msn.append(list(accumulate(vvv)))
 
INF = (N, None)
 
M = 2*N
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
 
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1
 
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]

def b_s(ll, mm, ms, ind, lw, hw, target_i, lncc):
    if w2i[ll[ind]] <= target_i:
        if ind + 1 > lncc:
            #print("xx")
            #print(mm, ms)
            return (mm[hw], ms[hw])
        if target_i < w2i[ll[ind+1]]:
            return (mm[ind], ms[ind])
        return b_s(ll, mm, ms, (ind + hw)//2, ind, hw, target_i, lncc)
    elif w2i[ll[ind]] > target_i:
        if ind == 0:
            return 0, 0
        return b_s(ll, mm, ms, (ind + lw)//2, lw, ind, target_i, lncc)

def iro(u, v, cc, x, y):
    u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[u], lnc[x]-1)
    v_n, v_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1)
    c_n, c_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[cc], lnc[x]-1)
    return (u_n + v_n - 2 * (c_n)) * y - (u_d + v_d - 2 * (c_d))

 
 
ans = []
#x = 2
#u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[2], lnc[x]-1)
#print(u_n, u_d)
#sys.exit()
for q in range(Q):
    x, y, u, v = map(int, readline().split())
    u, v = u-1, v-1
    cc = query(u, v)
    if lnc[x] == 0:
        diff = 0
    else:
        diff = iro(u, v, cc, x, y)
#    print("query, col : {} v_ind : {}".format(x, v), b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1))
    print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)
 
readline = sys.stdin.readline
write = sys.stdout.write
 
N, Q = map(int, readline().split())
G = []
g = defaultdict(list)
dp = {}
cdd = {}

for v in range(N-1):
    a, b, c, d = map(int, readline().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)
    dp["{}-{}".format(min(a,b), max(a,b))] = d
    cdd["{}-{}".format(min(a,b), max(a,b))] = c
cc = set()
for i in range(N):
    cc.add(i)
    G.append([])
    for vv in g[i]:
        if vv not in cc:
            G[i].append(vv)
 
S = []
F = [0]*N
depth = [0]*N
depthh = [0]*N
depthc = [defaultdict(int) for _ in range(N)]
vn = [[] for _ in range(N)]
sn = [[] for _ in range(N)]
iin = [[] for _ in range(N)]
aii = []
w2i = {}

ii = 0
def dfs(bb, v, d, dd, cc, dpd):
    global ii
    F[v] = len(S)
    depth[v] = d
    depthh[v] = dd
#    if bb != None:
#        depthc[v][cc] = depthc[bb][cc] + 1
    S.append(v)
    vn[cc].append(1)
    sn[cc].append(dpd)
    iin[cc].append(v)
    aii.append(v)
    w2i[v] = ii
    ii += 1
    for w in G[v]:
        nvn = cdd["{}-{}".format(min(v,w), max(v,w))]
        dpd = dp["{}-{}".format(min(v,w), max(v,w))]
        dfs(v, w, d+1, dd+dpd, nvn, dpd)
        S.append(v)
        vn[nvn].append(-1)
        sn[nvn].append(-dpd)
        iin[nvn].append(-w)
        aii.append(-w)
        w2i[-w] = ii
        ii += 1

dfs(None, 0, 0, 0, 0,0)
#print(S)
#print(vn)
#print(sn)
#print(iin)
#print(aii)
#print(w2i)
from itertools import accumulate
mmn = []
lnc = []
for vvv in vn:
    lnc.append(len(vvv))
    mmn.append(list(accumulate(vvv)))
msn = []
for vvv in sn:
    msn.append(list(accumulate(vvv)))
 
INF = (N, None)
 
M = 2*N
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
 
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1
 
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]

def b_s(ll, mm, ms, ind, lw, hw, target_i, lncc):
    if w2i[ll[ind]] <= target_i:
        if ind + 1 >= lncc:
            return (mm[hw], ms[hw])
        if target_i < w2i[ll[ind+1]]:
            return (mm[ind], ms[ind])
        return b_s(ll, mm, ms, (ind + hw)//2, ind, hw, target_i, lncc)
    elif w2i[ll[ind]] > target_i:
        if ind == 0:
            return 0, 0
        return b_s(ll, mm, ms, (ind + lw)//2, lw, ind, target_i, lncc)

def iro(u, v, cc, x, y):
    u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[u], lnc[x]-1)
    v_n, v_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1)
    c_n, c_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[cc], lnc[x]-1)
    return (u_n + v_n - 2 * (c_n)) * y - (u_d + v_d - 2 * (c_d))

 
 
ans = []
for q in range(Q):
    x, y, u, v = map(int, readline().split())
    u, v = u-1, v-1
    cc = query(u, v)
    if lnc[x] == 0:
        diff = 0
    else:
        diff = iro(u, v, cc, x, y)
#    print("query, col : {} v_ind : {}".format(x, v), b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1))
    print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)