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
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][::-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][::-1]:
                if u in visited:
                    continue
                stack += [-v, u]
        else:
            child = path.pop()
            cc, dpd = dp[(min(-v, child), max(-v, child))]
            mmn[cc].append(mmn[cc][-1]-1)
            iin[cc].append(ii)
            msn[cc].append(msn[cc][-1]-dpd)
            S[ii] = v
    # オイラーツアー
#    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]])

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

Submission status: Accepted

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

    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, 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 len(mmn[x])-1 == 0:
            diff = 0
        else:
            ll, mm, ms, lncc = iin[x], mmn[x], msn[x], len(mmn[x])-2
            uvcs = []
            for target_i in [F[u], F[v], F[cc]]:
                ind, lw, hw =  (len(mmn[x])-2)//2, 0, len(mmn[x]) - 2
                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()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
class LCA:
    def __init__(self,v,Edges,root=0):
        self.v=v
        self.Edges=Edges
        self.maxLog=18
        self.Parent=[[-1]*v for _ in range(self.maxLog+1)]
        self.Depth=[0]*v
        self.__bfs(root)
        for i in range(self.maxLog):
            for j in range(v):
                if self.Parent[i][j]!=-1:
                    self.Parent[i+1][j]=self.Parent[i][self.Parent[i][j]]
    def __bfs(self,root):
        Visited=[False]*self.v
        Visited[root]=True
        q=deque([root])
        while q:
            fr=q.pop()
            for to in self.Edges[fr]:
                if Visited[to]:
                    continue
                self.Parent[0][to]=fr
                self.Depth[to]=self.Depth[fr]+1
                Visited[to]=True
                q.append(to)
    def lca(self,a,b):
        if self.Depth[a]>self.Depth[b]:
            a,b=b,a
        for i in range(self.maxLog):
            if (self.Depth[b]-self.Depth[a])&(1<<i):
                b=self.Parent[i][b]
        if a==b:
            return b
        for i in reversed(range(self.maxLog-1)):
            if self.Parent[i][a]!=self.Parent[i][b]:
                a=self.Parent[i][a]
                b=self.Parent[i][b]
        return self.Parent[0][a]

def Eulertour(Edges,n,root=0):
    Euler=[]
    Depth=[-1]*n
    Depth[root]=0
    que=deque([root])
    que2=deque()
    Visited=[False]*n
    while que:
        fr=que.pop()
        Euler.append((Depth[fr],fr))
        if Visited[fr]:
            continue
        for to in Edges[fr]:
            if Visited[to]:
                que.append(to)
            else:
                Depth[to]=Depth[fr]+1
                que2.append(to)
        que.extend(que2)
        que2=deque()
        Visited[fr]=True
    return Euler

n,q=map(int,input().split())
Edgedict=[dict() for _ in range(n)]
for _ in range(n-1):
    a,b,c,d=map(int,input().split())
    a-=1; b-=1
    Edgedict[a][b]=(c,d)
    Edgedict[b][a]=(c,d)
Queries=[tuple(map(int,input().split())) for _ in range(q)]
Euler=Eulertour(Edgedict,n)
lca=LCA(n,Edgedict)
Q=[[] for _ in range(n)]
for i,(x,y,u,v) in enumerate(Queries):
    u-=1; v-=1
    Q[u].append([i,x,y,True])
    Q[v].append([i,x,y,True])
    Q[lca.lca(u,v)].append([i,x,y,False])
Ans=[0]*q
dist=0
C_len=[0]*n
C_cnt=[0]*n
for i in range(1,len(Euler)):
    idx=Euler[i][1]
    c,l=Edgedict[Euler[i-1][1]][idx]
    if Euler[i-1][0]<Euler[i][0]:
        dist+=l
        C_len[c]+=l
        C_cnt[c]+=1
        for q_idx,x,y,flag in Q[idx]:
            if flag:
                Ans[q_idx]+=dist+C_cnt[x]*y-C_len[x]
            else:
                Ans[q_idx]-=(dist+C_cnt[x]*y-C_len[x])*2
    else:
        dist-=l
        C_len[c]-=l
        C_cnt[c]-=1
print(*Ans,sep='\n')

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
class LCA:
    def __init__(self,V,edges,depth,parent,root=0):
        self.edges=edges
        self.maxLog=18
        self.parent=[[-1]*V for _ in range(self.maxLog+1)]
        self.parent[0]=parent
        self.depth=depth
        for i in range(self.maxLog):
            for j in range(V):
                if self.parent[i][j]!=-1:
                    self.parent[i+1][j]=self.parent[i][self.parent[i][j]]
    def lca(self,a,b):
        if self.depth[a]>self.depth[b]:
            a,b=b,a
        for i in range(self.maxLog):
            if (self.depth[b]-self.depth[a])&(1<<i):
                b=self.parent[i][b]
        if a==b:
            return b
        for i in reversed(range(self.maxLog-1)):
            if self.parent[i][a]!=self.parent[i][b]:
                a=self.parent[i][a]
                b=self.parent[i][b]
        return self.parent[0][a]

from collections import deque
def Eulertour(Edges,n,root=0):
    Euler=[]
    Depth=[-1]*n
    Depth[root]=0
    Parent=[-1]*n
    que=deque([root])
    que2=deque()
    Visited=[False]*n
    while que:
        fr=que.pop()
        Euler.append((Depth[fr],fr))
        if Visited[fr]:
            continue
        for to in Edges[fr]:
            if Visited[to]:
                que.append(to)
            else:
                Depth[to]=Depth[fr]+1
                Parent[to]=fr
                que2.append(to)
        que.extend(que2)
        que2=deque()
        Visited[fr]=True
    return Euler,Depth,Parent

n,q=map(int,input().split())
Edgedict=[dict() for _ in range(n)]
for _ in range(n-1):
    a,b,c,d=map(int,input().split())
    a-=1; b-=1
    Edgedict[a][b]=(c,d)
    Edgedict[b][a]=(c,d)
Queries=[tuple(map(int,input().split())) for _ in range(q)]
Euler,Depth,Parent=Eulertour(Edgedict,n)
lca=LCA(n,Edgedict,Depth,Parent)
Q=[[] for _ in range(n)]
for i,(x,y,u,v) in enumerate(Queries):
    u-=1; v-=1
    Q[u].append([i,x,y,True])
    Q[v].append([i,x,y,True])
    Q[lca.lca(u,v)].append([i,x,y,False])
Ans=[0]*q
dist=0
C_len=[0]*n
C_cnt=[0]*n
for i in range(1,len(Euler)):
    idx=Euler[i][1]
    c,l=Edgedict[Euler[i-1][1]][idx]
    if Euler[i-1][0]<Euler[i][0]:
        dist+=l
        C_len[c]+=l
        C_cnt[c]+=1
        for q_idx,x,y,flag in Q[idx]:
            if flag:
                Ans[q_idx]+=dist+C_cnt[x]*y-C_len[x]
            else:
                Ans[q_idx]-=(dist+C_cnt[x]*y-C_len[x])*2
    else:
        dist-=l
        C_len[c]-=l
        C_cnt[c]-=1
print(*Ans,sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

N, Q = map(int, input().split())
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
        a, b, c, d = map(int, input().split())
        edge[a].append((b, c, d))
        edge[b].append((a, c, d))
        
depth = [0] * (N+1)
U = 17
ancestor = [[0] * (U+1) for _ in range(N+1)]

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 edge[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

task = [[] for _ in range(N+1)]
for i in range(Q):
        x, y, u, v = map(int, input().split())
        task[u].append((i, x, y, 1))
        task[v].append((i, x, y, 1))
        task[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 task[x]:
                answer[i] += coef * (total - sums[c] + nums[c]*d)
        for y, c, d in edge[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
from copy import deepcopy
from operator import add, itemgetter
class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

def getpar(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[p] = None
    stack = [p]
    visited = set([p])
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            stack.append(vf)
    return par

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res

def eulertour(Par, Cld, st):
    #P[par]にはNoneをいれる
    Cld = deepcopy(Cld)
    N = len(Cld)
    St = [None]*N
    En = [None]*N
    et = []
    sign = []
    vf = st
    cnt = 0
    depth = [0]*N
    while vf is not None:
        vn = vf
        et.append(vn)
        if St[vn] is None:
            St[vn] = cnt
        En[vn] = cnt
        cnt += 1
        if Cld[vn]:
            vf = Cld[vn].pop()
            sign.append(1)
            depth[vf] = depth[vn] + 1
        else:
            vf = P[vn]
            sign.append(-1)
    return St, En, et, sign[:-1], depth

N, Q = map(int, input().split())
Edge = [[] for _ in range(N)]
Edgelen = [0]*(N-1)
Edgenum = {}
Color = [[] for _ in range(N)]
for i in range(N-1):
    a, b, c, d = map(int, sys.stdin.readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
    Edgelen[i] = d
    Edgenum[(a, b)] = i
    Edgenum[(b, a)] = i
    Color[c].append(i) 

P = getpar(Edge, 0)
C = getcld(P)
St, En, et, sign, depth = eulertour(P, C, 0)
etnum = [Edgenum[(v1, v2)] for v1, v2 in zip(et, et[1:])]
etnuminv = [[] for _ in range(N-1)]
for i, e in enumerate(etnum):
    etnuminv[e].append(i)
etl = [Edgelen[num]*sign[i] for i, num in enumerate(etnum)]

LCA = Segtree(et, None, initialize = True, segf = lambda x, y: x if y is None or (x is not None and depth[x] < depth[y]) else y)
Leng = Segtree([0]+etl, 0, initialize = True, segf = add)

Query = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
Ans = [None]*Q
CQ = [[] for _ in range(N)]
for i, (x, y, u, v) in enumerate(Query):
    CQ[x].append((i, y, u-1, v-1))

for col, cq in enumerate(CQ):
    if not cq:
        continue
    inf = 2*10**9
    for vidx in Color[col]:
        Leng.update(1+etnuminv[vidx][0], inf)
        Leng.update(1+etnuminv[vidx][1], -inf)
    
    for i, y, u, v in cq:
        if St[u] > St[v]:
            u, v = v, u
        su = St[u]
        sv = St[v]
        lca = LCA.query(su, sv+1)
        dis = Leng.query(0, su+1) + Leng.query(0,sv+1) - 2*Leng.query(0,St[lca]+1)
        disq, disr = divmod(dis, inf)
        Ans[i] = disr + disq*y
    for vidx in Color[col]:
        Leng.update(1+etnuminv[vidx][0], Edgelen[vidx])
        Leng.update(1+etnuminv[vidx][1], -Edgelen[vidx])
print('\n'.join(map(str, Ans)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
 
INF = 10**6
 
class RMQ:
    def __init__(self, a):
        self.n = len(a)
        self.size = 2**(self.n - 1).bit_length()
        self.data = [(INF, INF) for _ in range(2*self.size-1)]
        self.initialize(a)
 
    # Initialize data
    def initialize(self, a):
        for i in range(self.n):
            self.data[self.size + i - 1] = a[i][:]
        for i in range(self.size-2, -1, -1):
            self.data[i] = min(self.data[i*2 + 1], self.data[i*2 + 2])[:]
    
    # Update ak as x
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])[:]
    
    # Min value in [l, r)
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = (INF, INF)
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])[:]
            if L & 1:
                s = min(s, self.data[L-1])[:]
                L += 1
            L >>= 1; R >>= 1
        return s
 
class LCA:
    def __init__(self, edge, root):
        self.itr = 0
        self.edge = edge[:]
        self.path = [0] * (2*n-1)
        self.depth = [0] * (2*n-1)
        self.color = [0] * (2*n-1)
        self.weight = [0] * (2*n-1)
        self.index = [0] * n
        self.euler_tour(-1, root, 0, 0, 0, 0)
        dat = list(zip(self.depth, self.path))
        self.rmq = RMQ(dat)
    
    # Lowest ancestor of u, v
    def get_lca(self, u, v):
        l, r = self.index[u], self.index[v]
        if l > r:
            l, r = r, l
        return self.rmq.query(l, r+1)[1]
    
    def euler_tour(self, prev, v, d, k, c, w):
        self.index[v] = k
        self.path[self.itr] = v
        self.depth[self.itr] = d
        self.color[self.itr] = c
        self.weight[self.itr] = w
        self.itr += 1
        k += 1
        for dest, c, w in self.edge[v]:
            if prev == dest:
                continue
            k = self.euler_tour(v, dest, d + 1, k, c, w)
            self.path[self.itr] = v
            self.depth[self.itr] = d
            self.color[self.itr] = -c
            self.weight[self.itr] = -w
            self.itr += 1
            k += 1
        return k
        
n, q = [int(item) for item in input().split()] 
edge = [[] for _ in range(n)]
 
for _ in range(n-1):
    u, v, c, w = [int(item) for item in input().split()]
    u -= 1; v -= 1
    edge[u].append((v, c, w))
    edge[v].append((u, c, w))
 
lca = LCA(edge, 0)
memo = [dict() for _ in range(n)]
lca_memo = dict()
 
query = []
for _ in range(q):
    x, y, u, v = [int(item) for item in input().split()]
    u -= 1; v -= 1
    if u > v:
        u, v = v, u
    if (u, v) in lca_memo:
        ca = lca_memo[(u, v)]
    else:
        ca = lca.get_lca(u, v)
        lca_memo[(u, v)] = ca
    memo[u][x] = None
    memo[v][x] = None
    memo[ca][x] = None
    query.append((x, y, ca, u, v))
 
colors = [0] * n
c_depth = [0] * n
depth = 0
for p, c, w in zip(lca.path[1:], lca.color[1:], lca.weight[1:]):
    color = abs(c)
    if c < 0:
        colors[color] -= 1
    else:
        colors[color] += 1
    c_depth[color] += w
    depth += w
 
    for key in memo[p].keys():
        if memo[p][key] != None:
            break
        memo[p][key] = (colors[key], c_depth[key])
    memo[p][0] = depth 
 
ans = []
for x, y, ca, u, v in query:
    # Calc basic distance
    val = memo[u][0] + memo[v][0] - memo[ca][0] * 2
    # Append color diff
    val += (memo[v][x][0] + memo[u][x][0] - memo[ca][x][0] * 2) * y 
    val -= (memo[v][x][1] + memo[u][x][1] - memo[ca][x][1] * 2)
    ans.append(val)
print("\n".join(map(str,ans)))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,a,b = LI()
    print(min(a*n,b))
    return

#B
def B():
    n,d = LI()
    x = LIR(n)
    f = defaultdict(lambda : 0)
    for i in range(1000000):
        f[i*i] = 1
    ans = 0
    for i in range(n):
        for j in range(i+1,n):
            s = 0
            for k in range(d):
                s += (x[i][k]-x[j][k])**2
            if f[s]:
                ans += 1
    print(ans)
    return

#C
def C():
    l,r = LI()
    if r-l > 2019:
        print(0)
        quit()
    ans = float("inf")
    for i in range(l,r+1):
        for j in range(i+1,r+1):
            if i*j%2019 < ans:
                ans = i*j%2019
    print(ans)
    return

#D
def D():
    n = I()
    a = LI()
    for i in range(n):
        a[i] *= 2
    x = a[0]
    for i in range(1,n):
        if i%2:
            x -= a[i]
        else:
            x += a[i]
    b = [x//2]
    for i in range(n-1):
        b.append(abs(b[-1]-a[i]))
    print(*b)
    return

#E
def E():
    n,k = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    if k == 1:
        if n == 1:
            print(1)
            quit()
        else:
            print(0)
            quit()
    if k == 2:
        print(2)
        quit()
    d = [0]*n
    v.append([])
    v.append([])
    q = deque([0])
    bfs = [1]*n
    bfs[0] = 0
    f = [0]*n
    while q:
        x= q.popleft()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                q.append(y)
    ans = 1
    q = deque([0])
    dp = [None]*n
    dp[0] = k
    bfs = [1]*n
    bfs[0] = 0
    while q:
        x = q.popleft()
        m = len(v[x])
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                dp[y] = k-m
                m -= 1
                q.append(y)
    for i in dp:
        ans *= i
        ans %= mod
    print(ans)
    return

#F
def F():
    def lca(x,y):
        k = depth[x]-depth[y]
        while k > 0:
            x = par[x][int(math.log(k,2))]
            k = depth[x]-depth[y]
        k = -k
        while k > 0:
            y = par[y][int(math.log(k,2))]
            k = depth[y]-depth[x]
        if x == y:
            return x
        for i in range(M+1)[::-1]:
            if i < len(par[x]):
                if par[x][i] != par[y][i]:
                    x = par[x][i]
                    y = par[y][i]
        return par[x][0]

    def euler_tour(x,p,color):
        for i,c,d,k in f[x]:
            if k:
                query[i] -= 2*(-color[c][0]+color[c][1]*d)
            else:
                query[i] += -color[c][0]+color[c][1]*d
        for y,c,d in v[x]:
            if y != p:
                color[c][0] += d
                color[c][1] += 1
                euler_tour(y,x,color)
                color[c][0] -= d
                color[c][1] -= 1

    M = 16 #2^17 >= 10^5
    n,Q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b,c,d = LI()
        a -= 1
        b -= 1
        c -= 1
        v[a].append((b,c,d))
        v[b].append((a,c,d))
    par = [[] for i in range(n)]
    dist = [-1]*n
    dist[0] = 0
    depth = [0]*n
    q = deque([0])
    while q:
        x = q.popleft()
        for y,c,d in v[x]:
            if dist[y] < 0:
                dist[y] = dist[x]+d
                depth[y] = depth[x]+1
                q.append(y)
                par[y].append(x)

    l = [i for i in range(n)]
    l.sort(key = lambda x:depth[x])
    for i in range(M):
        k = 1<<(i+1)
        for x in l[::-1]:
            if depth[x] < k:break
            par[x].append(par[par[x][i]][i])
    f = [[] for i in range(n)] #各頂点にqueryの情報を持たせる ← すごい
    query = [0]*Q #オイラーツアー、LCAを用いた距離計算により各クエリの答えを計算
    for i in range(Q):
        x,y,a,b = LI()
        x -= 1
        a -= 1
        b -= 1
        f[a].append((i,x,y,0))
        f[b].append((i,x,y,0))
        l = lca(a,b)
        f[l].append((i,x,y,1))
        query[i] = dist[a]+dist[b]-2*dist[l]
    color = [[0,0] for i in range(n)] #色ごとにオイラーツアーでdist_sum(color),num(color)を計算(その色の距離,その色の数)
    euler_tour(0,-1,color)
    for i in query:
        print(i)
    return


#Solve
if __name__ == "__main__":
    F()