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**8)


class SegmentTree1():
    """
    1-indexed Segment Tree
    """
    def __init__(self, n_, ele_id, operation_func):
        self.n = 1 << (n_ - 1).bit_length()  # size
        self.data = [ele_id] * (2 * self.n)  # binary tree
        self.ele_id = ele_id  # identity element
        self.operation_func = operation_func  # binary operation of monoid

    def __getitem__(self, idx):
        return self.data[idx + self.n]

    def build(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n] = data_init[i]
        for i in range(self.n - 1, 0, -1):
            self.data[i] = self.operation_func(self.data[2 * i],
                                               self.data[2 * i + 1])

    def update(self, idx, x):
        # change idx-th element to x (idx : 0-indexed)
        idx += self.n
        self.data[idx] = x
        while idx > 1:
            idx = idx >> 1
            self.data[idx] = self.operation_func(self.data[2 * idx],
                                                 self.data[2 * idx + 1])

    def query(self, l, r):
        # query for interval [l, r) (l, r : 0-indexed)
        l += self.n
        r += self.n
        ret = self.ele_id
        while l < r:
            if l & 1:  # right child
                ret = self.operation_func(ret, self.data[l])
                l += 1
            if r & 1:  # right child
                r -= 1
                ret = self.operation_func(ret, self.data[r])
            # go to parent-nodes
            l = l >> 1
            r = r >> 1
        return ret


class Tree():
    def __init__(self, n, graph, v_root):
        self.n = n  # number of nodes
        self.graph = graph  # adjacent list of graph
        self.v_root = v_root  # root node

        # euler tour
        self.first_idx = [2 * self.n] * self.n
        self.euler_tour = []
        self.euler_depth_topo = []
        self.euler_depth_real = []
        self.euler_tour_dfs(self.v_root, -1, 0, 0)

        depth_list = [(di, i) for i, di in enumerate(self.euler_depth_topo)]
        INF = (2 * self.n, -1)
        operation_func = lambda a, b: a if a[0] < b[0] else b
        self.st_rmq = SegmentTree1(2 * self.n - 1, INF, operation_func)
        self.st_rmq.build(depth_list)

    def euler_tour_dfs(self, v, v_par, depth_topo, depth_real):
        self.first_idx[v] = len(self.euler_tour)
        self.euler_tour.append(v)
        self.euler_depth_topo.append(depth_topo)
        self.euler_depth_real.append(depth_real)
        for v_next, c, d in self.graph[v]:
            if v_next == v_par:
                continue
            self.euler_tour_dfs(v_next, v, depth_topo + 1, depth_real + d)
            self.euler_tour.append(v)
            self.euler_depth_topo.append(depth_topo)
            self.euler_depth_real.append(depth_real)

    def depth_topo(self, v):
        return self.euler_depth_topo[self.first_idx[v]]

    def depth_real(self, v):
        return self.euler_depth_real[self.first_idx[v]]

    def lca(self, u, v):
        u_idx, v_idx = self.first_idx[u], self.first_idx[v]
        if u_idx > v_idx:
            u_idx, v_idx = v_idx, u_idx
        _, idx = self.st_rmq.query(u_idx, v_idx + 1)
        return self.euler_tour[idx]

    def dist(self, u, v):
        lca_uv = self.lca(u, v)
        return self.depth(u) + self.depth(v) - 2 * self.depth(lca_uv)


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

tree = Tree(n, graph, 0)

query = []
memo = [set() for i in range(n)]
for _ in range(q):
    x, y, u, v = map(int, input().split())
    u -= 1
    v -= 1
    lca_uv = tree.lca(u, v)
    memo[u].add(x)
    memo[v].add(x)
    memo[lca_uv].add(x)

    query.append((x, y, u, v, lca_uv))

n_color = [0] * n
d_color = [0] * n
n_color_memo = {}
d_color_memo = {}


def dfs(v, v_par, depth):
    for c in memo[v]:
        n_color_memo[(v, c)] = n_color[c]
        d_color_memo[(v, c)] = d_color[c]

    for v_next, c, d in graph[v]:
        if v_next == v_par:
            continue
        n_color[c] += 1
        d_color[c] += d
        dfs(v_next, v, depth + d)
        n_color[c] -= 1
        d_color[c] -= d


dfs(0, -1, 0)

for x, y, u, v, lca in query:
    depth_u = tree.depth_real(u)
    depth_u += -d_color_memo[(u, x)] + y * n_color_memo[(u, x)]
    depth_v = tree.depth_real(v)
    depth_v += -d_color_memo[(v, x)] + y * n_color_memo[(v, x)]
    depth_lca = tree.depth_real(lca)
    depth_lca += -d_color_memo[(lca, x)] + y * n_color_memo[(lca, x)]

    ans = depth_u + depth_v - 2 * depth_lca
    print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,Q = map(int,readline().split())
data = np.array(read().split(),np.int64)

ABCD = data[:4*N-4].reshape(-1,4).tolist()

graph = [[] for _ in range(N+1)]
for a,b,c,d in ABCD:
    graph[a].append((b,c,d))
    graph[b].append((a,c,d))

color = [0] * (N+1) # 自身と親を結ぶ辺の色
length = [0] * (N+1) # 自身と親を結ぶ辺の長さ

def EulerTour(graph,start=1):
    """
    1-indexed graph
    graphを破壊しているので場合によっては注意
    """
    V = len(graph)
    par = [0] * V
    depth = [0] * V; depth[start] = 0
    tour = [start]; st = [start]
    while st:
        x = st[-1]
        if not graph[x]:
            st.pop()
            tour.append(par[x])
            continue
        y,c,d = graph[x].pop()
        if y == par[x]:
            continue
        par[y] = x
        color[y] = c
        length[y] = d
        depth[y] = depth[x] + 1
        st.append(y)
        tour.append(y)
    return tour,depth

tour,depth = EulerTour(graph)

Ltour = len(tour)
tour_arr = np.array(tour)
depth_arr = np.array(depth)
tour_d = depth_arr[tour_arr]
idx = np.arange(len(depth))
idx[tour_arr] = np.arange(Ltour)

# depth最小を実現するインデックスのsparse tableを作る
sp = np.empty((Ltour.bit_length(),Ltour),np.int32)
sp[0] = np.arange(Ltour)
for n in range(1,Ltour.bit_length()):
    prev,width = sp[n-1],1<<(n-1)
    x = prev[:-width]; y = prev[width:]
    condition = tour_d[x] > tour_d[y]
    sp[n] = prev
    sp[n,:-width][condition] = y[condition]

def LCA(A,B):
    AB = np.vstack([A,B]).T
    LR = idx[AB]
    LR.sort(axis=1)
    # [L,R] におけるRmQ
    L = LR[:,0]; R = LR[:,1]
    x = R-L
    n = np.zeros_like(x) # 2^n <= R-L
    for _ in range(20):
        x >>= 1
        n[x>0] += 1
    x = sp[n,L]; y = sp[n,R-(1<<n)+1]
    return np.where(tour_d[x] < tour_d[y], tour_arr[x], tour_arr[y])

XYUV = data[4*N-4:]
U = XYUV[2::4]; V = XYUV[3::4]
lca = LCA(U,V)

answer = [0] * Q
task = [[] for _ in range(N+1)]
for i,((x,y,u,v),w) in enumerate(zip(XYUV.reshape(-1,4).tolist(),lca.tolist())):
    # x,yの条件下での距離の何倍かをanswer[i]に加算する
    task[u].append((x,y,1,i))
    task[v].append((x,y,1,i))
    task[w].append((x,y,-2,i))

color_cnt = [0] * N
color_sum = [0] * N
d = 0 # いじらないときの距離

for fr,to in zip(tour,tour[1:]):
    d1 = depth[fr]; d2 = depth[to]
    if d1 > d2:
        # 上る前にクエリ処理
        for x,y,coef,i in task[fr]:
            answer[i] += coef * (d - color_sum[x] + color_cnt[x] * y)
    if d1 < d2:
        c = color[to]; l = length[to]
        color_cnt[c] += 1
        color_sum[c] += l; d += l
    else:
        c = color[fr]; l = length[fr]
        color_cnt[c] -= 1
        color_sum[c] -= l; d -= l

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,Q = map(int,readline().split())
data = np.array(read().split(),np.int64)

ABCD = data[:4*N-4].reshape(-1,4).tolist()

graph = [[] for _ in range(N+1)]
for a,b,c,d in ABCD:
    graph[a].append((b,c,d))
    graph[b].append((a,c,d))

color = [0] * (N+1) # 自身と親を結ぶ辺の色
length = [0] * (N+1) # 自身と親を結ぶ辺の長さ

def EulerTour(graph,start=1):
    """
    1-indexed graph
    graphを破壊しているので場合によっては注意
    """
    V = len(graph)
    par = [0] * V
    depth = [0] * V; depth[start] = 0
    tour = [start]; st = [start]
    while st:
        x = st[-1]
        if not graph[x]:
            st.pop()
            tour.append(par[x])
            continue
        y,c,d = graph[x].pop()
        if y == par[x]:
            continue
        par[y] = x
        color[y] = c
        length[y] = d
        depth[y] = depth[x] + 1
        st.append(y)
        tour.append(y)
    return tour,depth

tour,depth = EulerTour(graph)

Ltour = len(tour)
tour_arr = np.array(tour)
depth_arr = np.array(depth)
tour_d = depth_arr[tour_arr]
idx = np.arange(len(depth))
idx[tour_arr] = np.arange(Ltour)

# depth最小を実現するインデックスのsparse tableを作る
sp = np.empty((Ltour.bit_length(),Ltour),np.int32)
sp[0] = np.arange(Ltour)
for n in range(1,Ltour.bit_length()):
    prev,width = sp[n-1],1<<(n-1)
    x = prev[:-width]; y = prev[width:]
    condition = tour_d[x] > tour_d[y]
    sp[n] = prev
    sp[n,:-width][condition] = y[condition]

def LCA(A,B):
    AB = np.vstack([A,B]).T
    LR = idx[AB]
    LR.sort(axis=1)
    # [L,R] におけるRmQ
    L = LR[:,0]; R = LR[:,1]
    x = R-L
    n = np.zeros_like(x) # 2^n <= R-L
    for _ in range(20):
        x >>= 1
        n[x>0] += 1
    x = sp[n,L]; y = sp[n,R-(1<<n)+1]
    return np.where(tour_d[x] < tour_d[y], tour_arr[x], tour_arr[y])

XYUV = data[4*N-4:]
U = XYUV[2::4]; V = XYUV[3::4]
lca = LCA(U,V)

answer = [0] * Q
task = [[] for _ in range(N+1)]
for i,((x,y,u,v),w) in enumerate(zip(XYUV.reshape(-1,4),lca)):
    # x,yの条件下での距離の何倍かをanswer[i]に加算する
    task[u].append((x,y,1,i))
    task[v].append((x,y,1,i))
    task[w].append((x,y,-2,i))

color_cnt = [0] * N
color_sum = [0] * N
d = 0 # いじらないときの距離

for fr,to in zip(tour,tour[1:]):
    d1 = depth[fr]; d2 = depth[to]
    if d1 > d2:
        # 上る前にクエリ処理
        for x,y,coef,i in task[fr]:
            answer[i] += coef * (d - color_sum[x] + color_cnt[x] * y)
    if d1 < d2:
        c = color[to]; l = length[to]
        color_cnt[c] += 1
        color_sum[c] += l; d += l
    else:
        c = color[fr]; l = length[fr]
        color_cnt[c] -= 1
        color_sum[c] -= l; d -= l

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

Submission status: Accepted

Solution code:
# 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 True:
        if len(stack) == 0:
            break
        v, cc, dpd = stack.pop()
        if v > 0:
            parent = path[-1]
            path.append(v)
            vs.add(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
                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()

Submission status: Accepted

Solution code:
# 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
    mmn, msn, iin = [[0] for _ in range(N)], [[0] for _ in range(N)], [[0] for _ in range(N)]

    pvs, stack, path = set(), [(1, 0, 0)], [0]
    # dfs while版 
    while True:
        if len(stack) == 0:
            break
        v, cc, dpd = stack.pop()
        if v > 0:
            parent = path[-1]
            path.append(v)
            pvs.add(v)
            vs.add(v)

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

            S.append(v)
            for u, ucc, udpd in d[v]:
                if u in pvs:
                    continue
                    # 閉路あり
                    for i, c in enumerate(path):
                        if c == u:
                            break
                    return path[i+1:]  + [u]
                if u in vs:
                    continue
                stack += [(-v, ucc, udpd), (u, ucc, udpd)]
        else:
            pvs.remove(path[-1])
            path.pop()
            mmn[cc].append(mmn[cc][-1]-1)
            msn[cc].append(msn[cc][-1]-dpd)
            iin[cc].append(len(S))
            S.append(v)

    return S, F, depth, depthh, mmn, msn, 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(ll, target, min_i, max_i):
    # l[index] <= target < l[index+1] となるindexを返す
    if ll[max_i] <= target:
        return max_i
    if target < ll[min_i]:
        return None
    index = len(ll)//2
    while True:
        if ll[index] <= target:
            if target < ll[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, mmn, msn, 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]])

        r = depthh[u] + depthh[v] - 2*depthh[cc]
        index = bsearch(iin[x], F[u], 0, len(iin[x])-1)
        r += mmn[x][index] * y - msn[x][index]
        index = bsearch(iin[x], F[v], 0, len(iin[x])-1)
        r += mmn[x][index] * y - msn[x][index]

        index = bsearch(iin[x], F[cc], 0, len(iin[x])-1)
        r -= 2 * (mmn[x][index] * y - msn[x][index])
        print(r)

if __name__ == '__main__':
    process()

Submission status: Accepted

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

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(ll, target, min_i, max_i):
    # l[index] <= target < l[index+1] となるindexを返す
    if ll[max_i] <= target:
        return max_i
    if target < ll[min_i]:
        return None
    index = len(ll)//2
    while True:
        if ll[index] <= target:
            if target < ll[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 = [[] for _ in range(N+1)]
    dp = {}
    for v in range(N-1):
        a, b, c, d = map(int, readline().split())
        G[a].append(b)
        G[b].append(a)
        dp[(min(a,b), max(a,b))] = c, d

    S = [1]*(2*N+1)
    F = [0]*(N+1)
    stack = []
    for u in G[1]:
        stack += [-1, u]

    visited = set([1])
    depth, depthh = [0]*(N+1), [0]*(N+1)
    mmn = [[0] for _ in range(N)]
    msn = [[0] for _ in range(N)]
    iin = [[0] for _ in range(N)]
    path = [1]
    ii = 0

    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        ii += 1
        if v > 0:
            visited.add(v)
            parent = path[-1]
            path.append(v)
            #print(parent)

            cc, dpd = dp[(min(v,parent), max(v,parent))]
            F[v], S[ii] = ii, v
            depth[v], depthh[v] = depth[parent] + 1, depthh[parent] + dpd

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

            for u in G[v]:
                if u in visited:
                    continue
                stack += [-v, u]
        else:
            child = path.pop()
            cc, dpd = dp[(min(-v, child), max(-v, child))]
            S[ii] = v
            mmn[cc].append(mmn[cc][-1]-1)
            iin[cc].append(ii)
            msn[cc].append(msn[cc][-1]-dpd)
    # オイラーツアー
#    print(S)
#    print(depth)
#    print(F)
#    print(iin)
    stree = SegTree([(depth[abs(v)], i) for i, v in enumerate(S)], len(S), (N, None), min)

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

        cc = abs(S[stree.query(fu, fv+1)[1]])

        ll, mm, ms = iin[x], mmn[x], msn[x]
        uvcs = []
        for target_i in [F[u], F[v], F[cc]]:
            index = bsearch(ll, target_i, 0, len(ll)-1)
            uvcs.append((mm[index], ms[index]))
        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()

Submission status: Accepted

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

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

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

    S = [1]*(2*N+1)
    F = [0]*(N+1)
    stack = []
    for u in G[1]:
        stack += [-1, u]

    visited = set([1])
    depth, depthh = [0]*(N+1), [0]*(N+1)
    mmn = [[0] for _ in range(N)]
    msn = [[0] for _ in range(N)]
    iin = [[] for _ in range(N)]
    path = [1]
    ii = 0

    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        ii += 1
        if v > 0:
            visited.add(v)
            parent = path[-1]
            path.append(v)
            #print(parent)

            cc, dpd = dp[(min(v,parent), max(v,parent))]
            F[v], S[ii] = ii, v
            depth[v], depthh[v] = depth[parent] + 1, depthh[parent] + dpd

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

            for u in G[v]:
                if u in visited:
                    continue
                stack += [-v, u]
        else:
            child = path.pop()
            cc, dpd = dp[(min(-v, child), max(-v, child))]
            S[ii] = v
            mmn[cc].append(mmn[cc][-1]-1)
            iin[cc].append(ii)
            msn[cc].append(msn[cc][-1]-dpd)
    # オイラーツアー
#    print(S)
#    print(depth)
#    print(F)
#    print(iin)
    stree = SegTree([(depth[abs(v)], i) for i, v in enumerate(S)], len(S), (N, None), min)

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

        cc = abs(S[stree.query(fu, fv+1)[1]])

        ll, mm, ms = iin[x], mmn[x], msn[x]
        uvcs = []
        for target_i in [F[u], F[v], F[cc]]:
            if not ll:
                uvcs.append((0,0))
                continue
            ind, lw, hw =  (len(ll)-1)//2, 0, len(ll)-1
            if target_i < ll[0] or target_i >= ll[-1]:
                uvcs.append((0,0))
                continue
            while True:
                if ll[ind] <= target_i:
                    if target_i < 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()