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

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

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

depth = [0] * (N+1)
U = 17
ancestor = [[0] * (U+1) for _ in range(N+1)] # 2**i だけ遡った頂点の番号、行き過ぎは0

q = [(1,0,0)]
while q:
    qq = []
    for x,d,parent in q:
        depth[x] = d
        ax = ancestor[x]
        ax[0] = parent
        for i in range(d.bit_length() - 1):
            ax[i+1] = ancestor[ax[i]][i]
        for y, _, _ in graph[x]:
            if y == parent:
                continue
            qq.append((y, d+1, x))
    q = qq

def LCA(x,y):
    dx = depth[x]
    dy = depth[y]
    if dx > dy:
        x,y = y,x
        dx,dy = dy,dx
    diff = dy - dx
    while diff:
        step = diff & (-diff)
        y = ancestor[y][step.bit_length() - 1]
        diff -= step
    while x != y:
        j = 0
        while ancestor[x][j] != ancestor[y][j]:
            j += 1
        if j == 0:
            return ancestor[x][0]
        x = ancestor[x][j-1]
        y = ancestor[y][j-1]
    return x

tasks = [[] for _ in range(N+1)]
for i,(x,y,u,v) in enumerate(query):
    tasks[u].append((i,x,y,1))
    tasks[v].append((i,x,y,1))
    tasks[LCA(u,v)].append((i,x,y,-2))

answer = [0] * Q

def dfs(x = 1, sums = [0] * (N+1), nums = [0] * (N+1), total = 0, parent = 0):
    for i,c,d,coef in tasks[x]:
        answer[i] += coef * (total - sums[c] + nums[c] * d)
    for y,c,d in graph[x]:
        if y == parent:
            continue
        sums[c] += d
        nums[c] += 1
        total += d
        dfs(y, sums, nums, total, x)
        sums[c] -= d
        nums[c] -= 1
        total -= d
    return

dfs()

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

Submission status: Accepted

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

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

def set_ancestor(x=1, d=0, parent=0):
    depth[x] = d
    ax = ancestor[x]
    ax[0] = parent
    for i in range(d.bit_length() - 1):
        ax[i+1] = ancestor[ax[i]][i]
    for y, _, _ in graph[x]:
        if y == parent:
            continue
        set_ancestor(y, d+1, x)

depth = [0] * (N+1)
U = 17
ancestor = [[0] * (U+1) for _ in range(N+1)] # 2**i だけ遡った頂点の番号、行き過ぎは0
set_ancestor()

def LCA(x,y):
    dx = depth[x]
    dy = depth[y]
    if dx > dy:
        x,y = y,x
        dx,dy = dy,dx
    diff = dy - dx
    while diff:
        step = diff & (-diff)
        y = ancestor[y][step.bit_length() - 1]
        diff -= step
    while x != y:
        j = 0
        while ancestor[x][j] != ancestor[y][j]:
            j += 1
        if j == 0:
            return ancestor[x][0]
        x = ancestor[x][j-1]
        y = ancestor[y][j-1]
    return x

tasks = [[] for _ in range(N+1)]
for i,(x,y,u,v) in enumerate(query):
    tasks[u].append((i,x,y,1))
    tasks[v].append((i,x,y,1))
    tasks[LCA(u,v)].append((i,x,y,-2))

answer = [0] * Q

def dfs(x = 1, sums = [0] * (N+1), nums = [0] * (N+1), total = 0, parent = 0):
    for i,c,d,coef in tasks[x]:
        answer[i] += coef * (total - sums[c] + nums[c] * d)
    for y,c,d in graph[x]:
        if y == parent:
            continue
        sums[c] += d
        nums[c] += 1
        total += d
        dfs(y, sums, nums, total, x)
        sums[c] -= d
        nums[c] -= 1
        total -= d
    return

dfs()

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

Submission status: Accepted

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

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

def set_ancestor(x=1, d=0, parent=0):
    depth[x] = d
    ax = ancestor[x]
    ax[0] = parent
    for i in range(d.bit_length() - 1):
        ax[i+1] = ancestor[ax[i]][i]
    for y, _, _ in graph[x]:
        if y == parent:
            continue
        set_ancestor(y, d+1, x)

depth = [0] * (N+1)
U = 17
ancestor = [[0] * (U+1) for _ in range(N+1)] # 2**i だけ遡った頂点の番号、行き過ぎは0
set_ancestor()

def LCA(x,y):
    dx = depth[x]
    dy = depth[y]
    if dx > dy:
        x,y = y,x
        dx,dy = dy,dx
    diff = dy - dx
    while diff:
        step = diff & (-diff)
        y = ancestor[y][step.bit_length() - 1]
        diff -= step
    while x != y:
        j = 0
        while ancestor[x][j] != ancestor[y][j]:
            j += 1
        if j == 0:
            return ancestor[x][0]
        x = ancestor[x][j-1]
        y = ancestor[y][j-1]
    return x

tasks = [[] for _ in range(N+1)]
for i,(x,y,u,v) in enumerate(query):
    tasks[u].append((i,x,y,1))
    tasks[v].append((i,x,y,1))
    tasks[LCA(u,v)].append((i,x,y,-2))

answer = [0] * Q# 頂点、色に対して、距離、自色距離、自色個数)を入れる

def dfs(x, sums = defaultdict(int), nums = defaultdict(int), total = 0, parent = 0):
    for i,c,d,coef in tasks[x]:
        answer[i] += coef * (total - sums[c] + nums[c] * d)
    for y,c,d in graph[x]:
        if y == parent:
            continue
        sums[c] += d
        nums[c] += 1
        total += d
        dfs(y, sums, nums, total, x)
        sums[c] -= d
        nums[c] -= 1
        total -= d
    return

dfs(1)

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

Submission status: Accepted

Solution code:
from collections import deque,defaultdict
import sys
sys.setrecursionlimit(10**7)
N,Q=map(int,input().split())
table=[[] for i in range(N)]
ddcost=defaultdict(tuple)
for i in range(N-1):
    a,b,c,d=map(int,input().split())
    a,b,c=a-1,b-1,c-1
    table[a].append(b)
    table[b].append(a)
    ddcost[(min(a,b),max(b,a))]=(c,d)
#print(table)
#print(ddcost)
H=deque()
H.append(0)
visit=[-1]*N
visit[0]=0
parent=[[-1]*N for i in range(18)]
while H:
    x=H.popleft()
    for y in table[x]:
        if visit[y]!=-1:
            continue
        parent[0][y]=x
        visit[y]=visit[x]+1
        H.append(y)
for k in range(17):
    for i in range(N):
        if parent[k][i]<0:
            parent[k+1][i]=-1
        else:
            parent[k + 1][i]=parent[k][parent[k][i]]
def lca(u,v):
    if visit[u]>visit[v]:
        u,v=v,u
    for k in range(18):
        if ((visit[v]-visit[u] )>>k)&1:
            v=parent[k][v]
    if u==v:
        return u
    for k in range(17,-1,-1):
        if parent[k][u]!=parent[k][v]:
            u=parent[k][u]
            v=parent[k][v]
    return parent[0][u]

query=[]
sakidori=[set() for i in range(N)]
for i in range(Q):
    x,y,u,v=map(int,input().split())
    x,u,v=x-1,u-1,v-1
    if u>=v:
        u,v=v,u
    pa=lca(u,v)
    sakidori[u].add(x)
    sakidori[v].add(x)
    sakidori[pa].add(x)
    query.append((x,y,u,v,pa))
ddcolorsum=defaultdict(int)
ddcolornum=defaultdict(int)
W=deque()
colorsum=[0]*(N)
colornum=[0]*(N)
dist=[0]*N
vi=[0]*N
W.append((0,0,1))

while W:
    #print(W)
    pa,ci,vector=W.pop()
    if vector==-1:
        color,dis=ddcost[(min(pa,ci),max(pa,ci))]
        colorsum[color]-=dis
        colornum[color]-=1
        #print(colorsum, colornum, pa, ci, vector)
        continue
    if pa==0 and ci==0:
        for y in table[ci]:
            W.append((ci, y, 1))
        for co in sakidori[0]:
            ddcolorsum[(0,co)]=0
            ddcolornum[(0,co)]=0
        continue
    color,dis=ddcost[(min(pa,ci),max(pa,ci))]
    dist[ci]=dist[pa]+dis
    colorsum[color]+=dis
    colornum[color]+=1
    for co in sakidori[ci]:
        ddcolorsum[(ci, co)] = colorsum[co]
        ddcolornum[(ci, co)] = colornum[co]
    #print(colorsum,colornum,pa,ci,vector)
    W.append((pa,ci,-1))
    for y in table[ci]:
        if y==pa:
            continue
        W.append((ci,y,1))
#print(ddcolorsum)
#print(ddcolornum)
#print(dist)
def dista(x,y,u):
    return dist[u]-ddcolorsum[(u,x)]+y*ddcolornum[(u,x)]
for x,y,u,v,pa in query:
    #print(x,y,u,v,pa)
    #print(dista(x,y,u),dista(x,y,v),dista(x,y,pa))
    print(dista(x,y,u)+dista(x,y,v)-2*dista(x,y,pa))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 5 + 5)


def solve(n, links, queries):
    def _query(a, b, data, m0, INF):
        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 = first_appear[u]
        fv = first_appear[v]
        if fu > fv:
            fu, fv = fv, fu
        return euler_tour[min(_query(fu, fv + 1, data, m0, INF))[1]]

    def dfs(v, p, dep):
        first_appear[v] = len(euler_tour)
        depth[v] = dep
        euler_tour.append(v)
        for u, _, _ in links[v]:
            if u == p:
                continue
            dfs(u, v, dep + 1)
            euler_tour.append(v)

    def dfs2(v, p, tmp_dists, total_dist):
        for x, arr in v_queries[v].items():
            arr[0] = total_dist - tmp_dists[x][0]
            arr[1] = tmp_dists[x][1]
        for u, uc, ud in links[v]:
            if u == p:
                continue
            tmp_dists[uc][0] += ud
            tmp_dists[uc][1] += 1
            dfs2(u, v, tmp_dists, total_dist + ud)
            tmp_dists[uc][0] -= ud
            tmp_dists[uc][1] -= 1

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

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

    dfs(0, -1, 0)
    # print(euler_tour)
    # print(first_appear)
    # print(depth)

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

    v_queries = [{} for _ in range(n)]
    lca = []
    for i, (x, y, u, v) in enumerate(queries):
        w = query(u, v)
        lca.append(w)
        v_queries[u][x] = [0, 0]
        v_queries[v][x] = [0, 0]
        if w != 0:
            v_queries[w][x] = [0, 0]

    tmp_dists = defaultdict(lambda: [0, 0])
    dfs2(0, -1, tmp_dists, 0)

    ans = []
    for w, (x, y, u, v) in zip(lca, queries):
        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][x]
        dw = qw[0] + qw[1] * y
        ans.append(du + dv - 2 * dw)

    return ans


n, q = list(map(int, input().split()))
links = [set() 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].add((b, c, d))
    links[b].add((a, c, d))
queries = []
for line in lines[n - 1:]:
    x, y, u, v = map(int, line.split())
    u -= 1
    v -= 1
    queries.append((x, y, u, v))

ans = solve(n, links, queries)

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

Submission status: Runtime Error

Solution code:
class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num = 2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.seg = [ide_ele]*2*self.num
        # set_val
        for i in range(self.n):
            self.seg[i+self.num] = init_val[i]
        # built
        for i in range(self.num-1, 0, -1):
            self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])

    def update(self, k, x):
        k += self.num
        self.seg[k] = x
        while k:
            k = k >> 1
            self.seg[k] = self.segfunc(self.seg[2*k], self.seg[2*k+1])

    def query(self, l, r):
        if r <= l:
            return self.ide_ele
        l += self.num
        r += self.num
        res = self.ide_ele
        while l < r:
            if r & 1:
                r -= 1
                res = self.segfunc(res, self.seg[r])
            if l & 1:
                res = self.segfunc(res, self.seg[l])
                l += 1
            l = l >> 1
            r = r >> 1
        return res

def segfunc(x, y):
    if x <= y:
        return x
    else:
        return y

ide_ele = 10**18

class LCA:
    def __init__(self, g, root):
        # g: adjacency list
        # root
        self.n = len(g)
        self.root = root

        s = [self.root]
        self.parent = [-1]*self.n
        self.child = [[] for _ in range(self.n)]
        visit = [-1]*self.n
        visit[self.root] = 0
        while s:
            v = s.pop()
            for u in g[v]:
                if visit[u] == -1:
                    self.parent[u] = v
                    self.child[v].append(u)
                    visit[u] = 0
                    s.append(u)

        # Euler tour
        tank = [self.root]
        self.eulerTour = []
        self.left = [0]*self.n
        self.right = [-1]*self.n
        self.depth = [-1]*self.n

        eulerNum = -1
        de = -1

        while tank:
            v = tank.pop()
            if v >= 0:
                eulerNum += 1
                self.eulerTour.append(v)
                self.left[v] = eulerNum
                self.right[v] = eulerNum
                tank.append(~v)
                de += 1
                self.depth[v] = de
                for u in self.child[v]:
                    tank.append(u)
            else:
                de -= 1
                if ~v != self.root:
                    self.eulerTour.append(self.parent[~v])
                    eulerNum += 1
                    self.right[self.parent[~v]] = eulerNum

        #A = [self.depth[e] for e in self.eulerTour]
        A = [0]*(2*self.n-1)
        for i, e in enumerate(self.eulerTour):
            A[i] = self.depth[e]*(2*self.n-1)+i
        self.seg = SegTree(A, ide_ele, segfunc)

    def getLCA(self, u, v):
        # u, v: 0-indexed
        p = min(self.left[u], self.left[v])
        q = max(self.right[u], self.left[v])+1
        m = self.seg.query(p, q)
        return self.eulerTour[m%(2*self.n-1)]

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

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        # i: 0-indexed
        i += 1 # to 1-indexed
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        # return sum of [i, j)
        # i, j: 0-indexed
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

    def lower_bound(self, x):
        s = 0
        pos = 0
        depth = self.n.bit_length()
        v = 1 << depth
        for i in range(depth, -1, -1):
            k = pos + v
            if k <= self.n and s + self.bit[k] < x:
                    s += self.bit[k]
                    pos += v
            v >>= 1
        return pos

import sys
import io, os
input = sys.stdin.buffer.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

from collections import deque
q = deque([])
q.append(0)
dist = [BIT(n+1) for _ in range(n)]
cnt = [[-1]*(n-1) for _ in range(n)]
visit = [-1]*n
for i in range(n-1):
    cnt[0][i] = 0
visit[0] =0
while q:
    v = q.pop()
    for c, d, u in edge[v]:
        if visit[u] == -1:
            for i in range(n-1):
                dist[u].add(i, dist[v].sum(i, i+1))
                cnt[u][i] = cnt[v][i]
            dist[u].add(c, d)
            cnt[u][c] += 1
            visit[u] = 0
            q.append(u)

lca = LCA(g, 0)
for i in range(Q):
    x, y, u, v = map(int, input().split())
    x, u, v = x-1, u-1, v-1
    l = lca.getLCA(u, v)

    dl = dist[l].sum(0, dist[l].n)
    dl -= dist[l].sum(x, x+1)
    dl += cnt[l][x]*y

    du = dist[u].sum(0, dist[u].n)
    du -= dist[u].sum(x, x+1)
    du += cnt[u][x]*y

    dv = dist[v].sum(0, dist[v].n)
    dv -= dist[v].sum(x, x+1)
    dv += cnt[v][x]*y

    ans = du+dv-2*dl
    print(ans)

Submission status: Runtime Error

Solution code:
class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num = 2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.seg = [ide_ele]*2*self.num
        # set_val
        for i in range(self.n):
            self.seg[i+self.num] = init_val[i]
        # built
        for i in range(self.num-1, 0, -1):
            self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])

    def update(self, k, x):
        k += self.num
        self.seg[k] = x
        while k:
            k = k >> 1
            self.seg[k] = self.segfunc(self.seg[2*k], self.seg[2*k+1])

    def query(self, l, r):
        if r <= l:
            return self.ide_ele
        l += self.num
        r += self.num
        res = self.ide_ele
        while l < r:
            if r & 1:
                r -= 1
                res = self.segfunc(res, self.seg[r])
            if l & 1:
                res = self.segfunc(res, self.seg[l])
                l += 1
            l = l >> 1
            r = r >> 1
        return res

def segfunc(x, y):
    if x <= y:
        return x
    else:
        return y

ide_ele = 10**18

class LCA:
    def __init__(self, g, root):
        # g: adjacency list
        # root
        self.n = len(g)
        self.root = root

        s = [self.root]
        self.parent = [-1]*self.n
        self.child = [[] for _ in range(self.n)]
        visit = [-1]*self.n
        visit[self.root] = 0
        while s:
            v = s.pop()
            for u in g[v]:
                if visit[u] == -1:
                    self.parent[u] = v
                    self.child[v].append(u)
                    visit[u] = 0
                    s.append(u)

        # Euler tour
        tank = [self.root]
        self.eulerTour = []
        self.left = [0]*self.n
        self.right = [-1]*self.n
        self.depth = [-1]*self.n

        eulerNum = -1
        de = -1

        while tank:
            v = tank.pop()
            if v >= 0:
                eulerNum += 1
                self.eulerTour.append(v)
                self.left[v] = eulerNum
                self.right[v] = eulerNum
                tank.append(~v)
                de += 1
                self.depth[v] = de
                for u in self.child[v]:
                    tank.append(u)
            else:
                de -= 1
                if ~v != self.root:
                    self.eulerTour.append(self.parent[~v])
                    eulerNum += 1
                    self.right[self.parent[~v]] = eulerNum

        #A = [self.depth[e] for e in self.eulerTour]
        A = [0]*(2*self.n-1)
        for i, e in enumerate(self.eulerTour):
            A[i] = self.depth[e]*(2*self.n-1)+i
        self.seg = SegTree(A, ide_ele, segfunc)

    def getLCA(self, u, v):
        # u, v: 0-indexed
        p = min(self.left[u], self.left[v])
        q = max(self.right[u], self.left[v])+1
        m = self.seg.query(p, q)
        return self.eulerTour[m%(2*self.n-1)]

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

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        # i: 0-indexed
        i += 1 # to 1-indexed
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        # return sum of [i, j)
        # i, j: 0-indexed
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

    def lower_bound(self, x):
        s = 0
        pos = 0
        depth = self.n.bit_length()
        v = 1 << depth
        for i in range(depth, -1, -1):
            k = pos + v
            if k <= self.n and s + self.bit[k] < x:
                    s += self.bit[k]
                    pos += v
            v >>= 1
        return pos

import sys
import io, os
#input = sys.stdin.buffer.readline
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

from collections import deque
q = deque([])
q.append(0)
dist = [BIT(n) for _ in range(n)]
cnt = [[-1]*(n-1) for _ in range(n)]
visit = [-1]*n
for i in range(n-1):
    cnt[0][i] = 0
visit[0] =0
while q:
    v = q.pop()
    for c, d, u in edge[v]:
        if visit[u] == -1:
            for i in range(n-1):
                dist[u].add(i, dist[v].sum(i, i+1))
                cnt[u][i] = cnt[v][i]
            dist[u].add(c, d)
            cnt[u][c] += 1
            visit[u] = 0
            q.append(u)

lca = LCA(g, 0)
for i in range(Q):
    x, y, u, v = map(int, input().split())
    x, u, v = x-1, u-1, v-1
    l = lca.getLCA(u, v)

    dl = dist[l].sum(0, dist[l].n)
    dl -= dist[l].sum(x, x+1)
    dl += cnt[l][x]*y

    du = dist[u].sum(0, dist[u].n)
    du -= dist[u].sum(x, x+1)
    du += cnt[u][x]*y

    dv = dist[v].sum(0, dist[v].n)
    dv -= dist[v].sum(x, x+1)
    dv += cnt[v][x]*y

    ans = du+dv-2*dl
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
from copy import deepcopy
import sys
from time import time

start = time()

input = lambda: sys.stdin.readline()[:-1]
read = sys.stdin.read

class EulerTour:
    def __init__(self, N):
        self.N = N
        self.G = [[] for _ in range(N)]
    
    def add_edge(self, a, b):
        self.G[a].append(b)
        self.G[b].append(a)
    
    def from_graph(self, G, copy=False):
        if copy: self.G = deepcopy(G)
        else: self.G = G
            
    def build(self, root=0, lca=True):
        self.root = root
        self._dfs(root)
        self.In = [0]*self.N
        self.Out = [0]*self.N
        for i, v in enumerate(self.node_list):
            if self.In[v] == 0: self.In[v] = i
            self.Out[v] = i
        if lca:
            self.seg = SegTree(len(self.node_list))
            self.seg.build([self.d[self.node_list[i]] for i in range(len(self.node_list))])
    
    def lca(self, a, b):
        if self.root in (a,b):
            return self.root
        a_out, b_in = self.Out[a], self.In[b]
        if a_out > b_in:
            a_out, b_in = self.Out[b], self.In[a]
        if a_out > b_in:
            a_out, b_in = self.Out[b], self.Out[a]
        if a_out > b_in:
            a_out, b_in = self.Out[a], self.Out[b]
        idx = self.seg.find(a_out, b_in+1)
        return self.node_list[idx]
            
    def _dfs(self, root=0):
        self.idx2edge = {}
        self.edge2idx = {}
        self.node_list = []
        self.edge_list = []
        seen = [0]*len(self.G)
        prev = [0]*len(self.G)
        self.d =[-1]*len(self.G)
        todo = [~root, root]
        count = 0
        while todo:
            a = todo.pop()
            if a >= 0:
                seen[a] = 1
                self.d[a] = self.d[prev[a]] + 1
                edge = (prev[a], a)
                self.idx2edge[count] = edge
                self.edge2idx[edge] = count
                self.edge_list.append(count)
                self.node_list.append(a)
                count += 1
                for b in reversed(self.G[a]):
                    if seen[b]: continue
                    todo.append(~b)
                    todo.append(b)
                    prev[b] = a
            else: 
                edge = (prev[~a], ~a)
                idx = self.edge2idx[edge]
                self.edge_list.append(-idx)
                if ~a != root: self.node_list.append(prev[~a])
                    
class SegTree:
    """ segment tree with point modification and range product. """
    # # https://yukicoder.me/submissions/452850
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)
    
    def find(self, L, R):
        x = self.fold(L,R)
        while R-L>1:
            M = (R+L)//2
            if self.fold(L,M)==x: R = M
            else: L = M
        return L

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
  
def argmax(arr):
    return arr.index(max(arr))

def main():
  N,Q = map(int,input().split())
  abcd = [tuple(map(int,input().split())) for _ in range(N-1)]
  G = [{} for _ in range(N)]
  et = EulerTour(N)
  for a,b,c,d in abcd:
    G[a-1][b-1] = (c,d)
    G[b-1][a-1] = (c,d)
    et.add_edge(a-1,b-1)

  root = argmax([len(G[i]) for i in range(N)])
  et.build(root)
  csum,cnum,d = bfs(G,root)
  assert time() - start < 1
  ans = [0]*Q
  xyuv = tuple(map(int,read().split()))
  for i in range(len(xyuv)//4):
    x,y,u,v = xyuv[i*4:(i+1)*4]
    u,v = u-1,v-1
    w = et.lca(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')
    
if __name__=="__main__":
  main()