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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
# N: 頂点数
# G[v]: 頂点vの子頂点 (親頂点は含まない)

# LCAの計算 (generatorで最小値を求める)
from collections import defaultdict


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


# LCAの計算 (外から呼び出す関数)
def query(u, v):
    fu = first_appear[u]
    fv = first_appear[v]
    if fu > fv:
        fu, fv = fv, fu
    return euler_tour[min(_query(fu, fv + 1))[1]]


import sys

sys.setrecursionlimit(10 ** 5 + 5)

n, q = list(map(int, input().split()))
links = [{} for _ in range(n)]
lines = sys.stdin.readlines()
for line in lines[:n - 1]:
    a, b, c, d = list(map(int, line.split()))
    a -= 1
    b -= 1
    links[a][b] = (c, d)
    links[b][a] = (c, d)
queries = []
v_queries = [{} for _ in range(n)]
for line in lines[n - 1:]:
    x, y, u, v = map(int, line.split())
    u -= 1
    v -= 1
    queries.append((x, y, u, v))
    v_queries[u][x] = [0, 0]
    v_queries[v][x] = [0, 0]

# 存在しない範囲は深さが他よりも大きくなるようにする
INF = (n, None)

# Euler Tour の構築
euler_tour = []
first_appear = [0] * n
depth = [0] * n
parents = [0] * n


def dfs(v, p, dep, tmp_dist, total_dist):
    first_appear[v] = len(euler_tour)
    depth[v] = dep
    euler_tour.append(v)
    parents[v] = p
    for x, arr in v_queries[v].items():
        arr[0] = total_dist - tmp_dist[x][0]
        arr[1] = tmp_dist[x][1]
    for u, (uc, ud) in links[v].items():
        if u == p:
            continue
        tmp_dist[uc][0] += ud
        tmp_dist[uc][1] += 1
        dfs(u, v, dep + 1, tmp_dist, total_dist + ud)
        tmp_dist[uc][0] -= ud
        tmp_dist[uc][1] -= 1
        euler_tour.append(v)


def dfs2(v, x, y, dist, cnt):
    p = parents[v]
    if p == -1:
        return dist, cnt
    c, d = links[v][p]
    if x == c:
        cnt += 1
    else:
        dist += d
    dfs2(p, x, y, dist, cnt)


tmp_dist = defaultdict(lambda: [0, 0])
dfs(0, -1, 0, tmp_dist, 0)
# print(euler_tour)
# print(first_appear)
# print(depth)
# print(v_queries)

# LCAを計算するクエリの前計算
m = 2 * n
m0 = 2 ** (m - 1).bit_length()
data = [INF] * (2 * m0)
for i, v in enumerate(euler_tour):
    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])

# print(data)

ans = []
for x, y, u, v in queries:
    w = query(u, v)
    # print(u, v, w)
    qu = v_queries[u][x]
    qv = v_queries[v][x]
    du = qu[0] + qu[1] * y
    dv = qv[0] + qv[1] * y
    if w == 0:
        ans.append(du + dv)
        continue
    qw = v_queries[w]
    if x in qw:
        qw = qw[x]
        dw = qw[0] + qw[1] * y
        ans.append(du + dv - 2 * dw)
        continue
    dist, cnt = dfs2(w, x, y, 0, 0)
    qw[x] = [dist, cnt]
    dw = dist + cnt * y
    ans.append(du + dv - 2 * dw)

print('\n'.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
from collections import deque

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

queue = deque()
queue.append(1)
height = [0] * (N+1)
height[1] = 1
cdp = [0] * (N+1)
while queue:
    v = queue.popleft()
    for child in adj[v]:
        if height[child[0]] == 0:
            idx = child[0]
            queue.append(idx)
            height[idx] = height[v] + 1
            cdp[idx] = [child[1], child[2], v]

for q in range(Q):
    x, y, u, v = map(int, input().split())
    ans = 0
    h_u = height[u]
    h_v = height[v]
    while h_u != h_v:
        if h_u < h_v:
            if cdp[v][0] == x:
                ans += y
            else:
                ans += cdp[1]
            v = cdp[2]
        else:
            if cdp[v][0] == x:
                ans += y
            else:
                ans += cdp[1]
            v = cdp[2]
    while u != v:
        if cdp[v][0] == x:
            ans += y
        else:
            ans += cdp[1]
        v = cdp[2]
        if cdp[v][0] == x:
            ans += y
        else:
            ans += cdp[1]
        v = cdp[2]
    print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 1e5 + 10;
int n, q;
int in[maxn], out[maxn];
vector<tuple<int, int, int>> g[maxn];

int pa[maxn][18], pl[maxn][18];
using PII = pair<int, int>;

PII operator+(const PII &a, const PII &b) {
  return {a.first + b.first, a.second + b.second};
}

unordered_map<int, PII> cs[maxn][17];

unordered_map<int, PII> merge_map(const unordered_map<int, PII> &a, const unordered_map<int, PII> &b) {
  if (a.size() > b.size())
    return merge_map(b, a);
  unordered_map<int, PII> r = a;
  for (auto it : b) {
    r[it.first] = r[it.first] + it.second;
  }
  return r;
}

int timer = 0;
void dfs(int x, int p = 1) {
  for (auto &it : g[x]) {
    int y, c, l;
    tie(y, c, l) = it;
    if (y != p) {
      pl[y][0] = l;
      cs[y][0][c].first += 1;
      cs[y][0][c].second += l;
    }
  }
  in[x] = timer++;
  pa[x][0] = p;
  for (int i = 1; i < 17; ++i) {
    int gf = pa[x][i-1];
    pa[x][i] = pa[gf][i-1];
    pl[x][i] = pl[gf][i-1] + pl[x][i-1];
    cs[x][i] = merge_map(cs[x][i-1], cs[gf][i-1]);
  }
  for (auto &it : g[x]) {
    int y, c, l;
    tie(y, c, l) = it;
    if (y != p) {
      dfs(y, x);
    }
  }
  out[x] = timer++;
}

inline int indirect_parent(int up, int down) {
  return in[up] <= in[down] && out[down] <= out[up];
}
int lca(int a, int b) {
  if (indirect_parent(a, b)) return a;
  if (indirect_parent(b, a)) return b;
  for (int i = 16; i >= 0; --i)
    if (!indirect_parent(pa[a][i], b))
      a = pa[a][i];
  return pa[a][0];
}
int len(int a, int b) {
  // b --> a
  int r = 0;
  for (int i = 16; i >= 0; --i) {
    if (in[pa[a][i]] >= in[b]) {
      r += pl[a][i];
      a = pa[a][i];
    }
  }
  return r;
}
PII cnt(int a, int b, int c) {
  PII r{0, 0};
  for (int i = 16; i >= 0; --i) {
    if (in[pa[a][i]] >= in[b]) {
      auto &v = cs[a][i];
      if (v.count(c)) {
        r = r + v[c];
      }
      a = pa[a][i];
    }
  }
  return r;
}

int main() {
  scanf("%d%d", &n, &q);
  for (int i = 0, a, b, c, d; i < n - 1; ++i) {
    scanf("%d%d%d%d", &a, &b, &c, &d);
    g[a].emplace_back(b, c, d);
    g[b].emplace_back(a, c, d);
  }
  dfs(1);
  for (int _ = 0, x, y, u, v; _ < q; ++_) {
    scanf("%d%d%d%d", &x, &y, &u, &v);
    int l = lca(u, v);
    int a1 = len(u, l) + len(v, l);
    PII b = cnt(u, l, x) + cnt(v, l, x);
    int ans = a1 - b.second + b.first * y;
    printf("%d\n", ans);
  }
  return 0;
}

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, q = na()
g = [[] for _ in range(n)]
es = []
for i in range(n-1):
    a, b, c, d = na()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    es.append((c, d, a, b))
es.sort()

qs = []
for i in range(q):
    x, y, u, v = na()
    qs.append((x, y, u-1, v-1, i))
qs.sort()

def addfenwick(ft, i, v):
    if v == 0 or i < 0: return
    i += 1
    while i < len(ft):
        ft[i] += v
        i += i&-i

def sumfenwick(ft, i):
    s = 0
    i += 1
    while i > 0:
        s += ft[i]
        i -= i&-i
    return s

ord = []
right = [0] * n
par = [-1] * n
dep = [0] * n

def dfs(cur, pre, g):
    global ord, right, par, dep
    ord.append(cur)
    for e in g[cur]:
        if e == pre: continue
        dep[e] = dep[cur] + 1
        dfs(e, cur, g)
        par[e] = cur
    right[cur] = len(ord)

dfs(0, -1, g)


def ntz(m):
    ret = 0
    while m&1^1:
        ret += 1
        m >>= 1
    return ret

def lca(a, b, spar, dep):
    if dep[a] < dep[b]:
        b = anc(b, dep[b] - dep[a], spar)
    else:
        a = anc(a, dep[a] - dep[b], spar)

    if a == b:
        return a

    for d in range(len(spar)-1, -1, -1):
        if spar[d][a] == -1: continue
        if spar[d][a] != spar[d][b]:
            a = spar[d][a]
            b = spar[d][b]
    return spar[0][a]

def anc(a, m, spar):
    while m > 0 and a != -1:
        a = spar[ntz(m)][a]
        m &= m-1
    return a

def lsp(par):
    n = len(par)
    m = 17
    pars = [[0]*n for _ in range(m)]
    pars[0] = par
    for j in range(1, m):
        for i in range(n):
            pars[j][i] = -1 if pars[j-1][i] == -1 else pars[j-1][pars[j-1][i]]
    return pars

ft = [0] * (n+5)
ftc = [0] * (n+5)

pw = [0] * n
for e in es:
    if par[e[2]] == e[3]:
        pw[e[2]] = e[1]
    else:
        pw[e[3]] = e[1]

iord = [0] * n
for i in range(n):
    iord[ord[i]] = i

for i in range(1, n):
    addfenwick(ft, iord[i], pw[i])
    addfenwick(ft, right[i], -pw[i])

anss = [0] * q

spar = lsp(par)
i = 0
p = 0
while i < q:
    j = i
    while j < q and qs[j][0] == qs[i][0]:
        j += 1

    while p < n-1 and es[p][0] < qs[i][0]:
        p += 1
    r = p
    while r < n-1 and es[r][0] <= qs[i][0]:
        x = es[r][2]
        y = es[r][3]
        z = x if par[x] == y else y
        addfenwick(ft, iord[z], -pw[z])
        addfenwick(ft, right[z], pw[z])
        addfenwick(ftc, iord[z], 1)
        addfenwick(ftc, right[z], -1)
        r += 1

    for u in range(i, j):
        lc = lca(qs[u][2], qs[u][3], spar, dep)
        c0 = sumfenwick(ft, iord[qs[u][2]]) + sumfenwick(ft, iord[qs[u][3]]) - 2*sumfenwick(ft, iord[lc])
        c1 = sumfenwick(ftc, iord[qs[u][2]]) + sumfenwick(ftc, iord[qs[u][3]]) - 2*sumfenwick(ftc, iord[lc])
        anss[qs[u][4]] = c0 + c1 * qs[u][1]

    r = p
    while r < n-1 and es[r][0] <= qs[i][0]:
        x = es[r][2]
        y = es[r][3]
        z = x if par[x] == y else y
        addfenwick(ft, iord[z], pw[z])
        addfenwick(ft, right[z], -pw[z])
        addfenwick(ftc, iord[z], -1)
        addfenwick(ftc, right[z], 1)
        r += 1

    i = j

for v in anss:
    print(v)