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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
edge=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c,d=map(int1,input().split())
    d+=1
    edge[a].append((b,c,d))
    edge[b].append((a,c,d))
U=defaultdict(list)
V=defaultdict(list)
Query=[]
for i in range(Q):
    x,y,u,v=map(int1,input().split())
    Query.append((x,y,u,v))
    y+=1
    U[u].append((x,y,i))
    V[v].append((x,y,i))

diff=[0]*Q
S=[0]*(2*N-1)

def EulerTour(start,n,edges):
    used=[False]*n
    et=[]
    left=[-1]*n
    right=[-1]*n
    depth=[]
    stack=[(start,-1,-1)]
    cur_depth=-1
    col=[[0,0] for _ in range(N)]
    while stack:
        v,c,d=stack.pop()
        if et:
            S[len(et)]=S[len(et)-1]+d
        if v>=0:
            col[c][0]+=d
            col[c][1]+=1
            used[v]=True
            cur_depth+=1
            left[v]=right[v]=len(et)
            et.append(v)
            depth.append(cur_depth)
            for nv,c,d in edges[v]:
                if not used[nv]:
                    stack.append((~v,c,-d))
                    stack.append((nv,c,d))
        else:
            col[c][0]+=d
            col[c][1]-=1
            cur_depth-=1
            right[~v]=len(et)
            et.append(~v)
            depth.append(cur_depth)
        while U[v]:
            qc,qd,qi=U[v].pop()
            diff[qi]+=col[qc][0]-col[qc][1]*qd
        while V[v]:
            qc,qd,qi=V[v].pop()
            diff[qi]-=col[qc][0]-col[qc][1]*qd
    return left,depth

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

s=SegmentTree(2*N-1,lambda a,b:min(a,b,key=lambda t:t[0]),(INF,INF))
left,depth=EulerTour(0,N,edge)
for i in range(2*N-1):
    s.update(i,(depth[i],i))

for i,(x,y,u,v) in enumerate(Query):
    p,q=min(left[u],left[v]),max(left[u],left[v])+1
    res=s.query(p,q)
    print(S[left[v]]+S[left[u]]-S[res[1]]*2+diff[i])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
edge=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c,d=map(int1,input().split())
    d+=1
    edge[a].append((b,c,d))
    edge[b].append((a,c,d))
U=defaultdict(list)
V=defaultdict(list)
Query=[]
for i in range(Q):
    x,y,u,v=map(int1,input().split())
    Query.append((x,y,u,v))
    y+=1
    U[u].append((x,y,i))
    V[v].append((x,y,i))

diff=[0]*Q
S=[0]*(2*N-1)

def EulerTour(start,n,edges):
    used=[False]*n
    et=[]
    left=[-1]*n
    right=[-1]*n
    depth=[]
    stack=[(start,-1,-1)]
    cur_depth=-1
    col=[[0,0] for _ in range(N)]
    while stack:
        v,c,d=stack.pop()
        if et:
            S[len(et)]=S[len(et)-1]+d
        if v>=0:
            col[c][0]+=d
            col[c][1]+=1
            used[v]=True
            cur_depth+=1
            left[v]=right[v]=len(et)
            et.append(v)
            depth.append(cur_depth)
            for nv,c,d in edges[v]:
                if not used[nv]:
                    stack.append((~v,c,-d))
                    stack.append((nv,c,d))
        else:
            col[c][0]+=d
            col[c][1]-=1
            cur_depth-=1
            right[~v]=len(et)
            et.append(~v)
            depth.append(cur_depth)
        while U[v]:
            qc,qd,qi=U[v].pop()
            diff[qi]+=col[qc][0]-col[qc][1]*qd
        while V[v]:
            qc,qd,qi=V[v].pop()
            diff[qi]-=col[qc][0]-col[qc][1]*qd
    return left,depth

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

s=SegmentTree(2*N-1,lambda a,b:min(a,b,key=lambda t:t[0]),(INF,INF))
left,depth=EulerTour(0,N,edge)
for i in range(2*N-1):
    s.update(i,(depth[i],i))

for i,(x,y,u,v) in enumerate(Query):
    res=s.query(u,v+1)
    print(S[left[v]]+S[left[u]]-S[res[1]]*2+diff[i])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6+1) #再帰関数の上限,10**5以上の場合python


def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None


#N, Q = map(int, input().split())
N, Q = map(int, input().split())
#A = tuple(map(int, input().split())) #1行ベクトル
#L = tuple(int(input()) for i in range(N)) #改行ベクトル
#S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

edge = [[] for i in range(N)]
for i in range(N-1):#木の場合M=N-1
    a,b,c,w = map(int,input().split())
    edge[a-1].append((b-1,c-1,w))
    edge[b-1].append((a-1,c-1,w)) #有向のばあいコメントアウト



#ダブリングによるLCA, 前処理NlogN, 呼び出しlogN, 安定  
def dfs(start):
    q=[(start,-1,0,0)]
    pars=[-1]*N
    depth=[-1]*N
    dist=[-1]*N
    while len(q):
        e,p,d,dis=q.pop()#ここをpopleftにすると幅優先探索BFSになる
        if depth[e]!=-1:continue
        pars[e]=p
        depth[e]=d
        dist[e]=dis
        for ne,c,w in edge[e]:
            q.append((ne,e,d+1,dis+w))
    return pars,depth,dist
pars,d,dist=dfs(0)
ln=N.bit_length()
dp=[[-1]*N for _ in range(ln+1)]
dp[0]=pars
for i in range(1,ln+1):
    for j in range(N):
        dp[i][j]=dp[i-1][dp[i-1][j]]


# LCAの計算
def lca(u, v):
    du = d[u]; dv = d[v]
    if du > dv:
        du, dv = dv, du
        u,v=v,u
    dif=dv-du
    for i in range(ln+1):
        if (dif>>i)&1:
            v=dp[i][v]
    if u==v:return u
    for i in range(ln,-1,-1):
        pu=dp[i][u];pv=dp[i][v]
        if pu!=pv:
            u,v=pu,pv
    return pars[u]

q=Q
qs = tuple(tuple(map(int, input().split())) for i in range(Q)) #改行行列
ans=[0]*Q
qn=[[] for _ in range(N)]
for i,(x,y,u,v) in enumerate(qs):
    ans[i]=dist[u-1]+dist[v-1]-dist[lca(u-1,v-1)]
    qn[u-1].append((i,x-1,y,1))
    qn[v-1].append((i,x-1,y,1))
    qn[lca(u-1,v-1)].append((i,x-1,y,-2))
cnt=[0]*Q
#printe(qn)

qc=[[0,0] for _ in range(Q)]
cc=[[0,0] for _ in range(N-1)]

dfq=[(0,None,0,-1)]
def dfs2(e):
    for qi,x,y,sgn in qn[e]:
        ans[qi]+=(y*cc[x][0]-cc[x][1])*sgn
    for ne,c,nd in edge[e]:
        if ne==pars[e]:continue
        if c!=None:
            cc[c][0]+=1
            cc[c][1]+=nd
        dfs2(ne)
        if c!=None:
            cc[c][0]-=1
            cc[c][1]-=nd
dfs2(0)
printl(ans)

# n=N
# A = [0]*q
# C = [[] for _ in range(n)]
# num = [0]*n
# cum = [0]*n
# for i in range(q):
#   x, y, u, v = map(int, input().split())
#   u -= 1
#   v -= 1
#   a = lca(u, v)
#   C[u].append((i, x, y, 1))
#   C[v].append((i, x, y, 1))
#   C[a].append((i, x, y, -2))
# dist = 0
# stack = [0]
# def dfs2(v):
#   global dist
#   for i, x, y, b in C[v]:
#     A[i] += (dist + num[x]*y - cum[x]) * b
#   for nv, c, d in edge[v]:
#     c+=1
#     if nv ==pars[v]:continue
#     dist += d
#     num[c] += 1
#     cum[c] += d
#     dfs2(nv)
#     dist -= d
#     num[c] -= 1
#     cum[c] -= d
# dfs2(0)
# print(*A, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6+1) #再帰関数の上限,10**5以上の場合python


def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None


#N, Q = map(int, input().split())
N, Q = map(int, input().split())
#A = tuple(map(int, input().split())) #1行ベクトル
#L = tuple(int(input()) for i in range(N)) #改行ベクトル
#S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

edge = [[] for i in range(N)]
for i in range(N-1):#木の場合M=N-1
    a,b,c,w = map(int,input().split())
    edge[a-1].append((b-1,c-1,w))
    edge[b-1].append((a-1,c-1,w)) #有向のばあいコメントアウト



#ダブリングによるLCA, 前処理NlogN, 呼び出しlogN, 安定  
def dfs(start):
    q=[(start,-1,0,0)]
    pars=[-1]*N
    depth=[-1]*N
    dist=[-1]*N
    while len(q):
        e,p,d,dis=q.pop()#ここをpopleftにすると幅優先探索BFSになる
        if depth[e]!=-1:continue
        pars[e]=p
        depth[e]=d
        dist[e]=dis
        for ne,c,w in edge[e]:
            q.append((ne,e,d+1,dis+w))
    return pars,depth,dist
pars,d,dist=dfs(0)
ln=N.bit_length()
dp=[[-1]*N for _ in range(ln+1)]
dp[0]=pars
for i in range(1,ln+1):
    for j in range(N):
        dp[i][j]=dp[i-1][dp[i-1][j]]


# LCAの計算
def lca(u, v):
    du = d[u]; dv = d[v]
    if du > dv:
        du, dv = dv, du
        u,v=v,u
    dif=dv-du
    for i in range(ln+1):
        if (dif>>i)&1:
            v=dp[i][v]
    if u==v:return u
    for i in range(ln,-1,-1):
        pu=dp[i][u];pv=dp[i][v]
        if pu!=pv:
            u,v=pu,pv
    return pars[u]

q=Q
qs = tuple(tuple(map(int, input().split())) for i in range(Q)) #改行行列
ans=[0]*Q
qn=[[] for _ in range(N)]
for i,(x,y,u,v) in enumerate(qs):
    ans[i]=dist[u-1]+dist[v-1]-dist[lca(u-1,v-1)]
    qn[u-1].append((i,x-1,y,1))
    qn[v-1].append((i,x-1,y,1))
    qn[lca(u-1,v-1)].append((i,x-1,y,-2))
cnt=[0]*Q
#printe(qn)

qc=[[0,0] for _ in range(Q)]
cc=[[0,0] for _ in range(N-1)]

dfq=[(0,None,0,-1)]
def dfs2(e,c,d,p):
    if c!=None:
        cc[c][0]+=1
        cc[c][1]+=d
    for qi,x,y,sgn in qn[e]:
        ans[qi]+=(y*cc[x][0]-cc[x][1])*sgn
    for ne,nc,nd in edge[e]:
        if ne==pars[e]:continue
        dfs2(ne,nc,nd,e)
    if c!=None:
        cc[c][0]-=1
        cc[c][1]-=d
dfs2(0,-1,0,None)
printl(ans)

# n=N
# A = [0]*q
# C = [[] for _ in range(n)]
# num = [0]*n
# cum = [0]*n
# for i in range(q):
#   x, y, u, v = map(int, input().split())
#   u -= 1
#   v -= 1
#   a = lca(u, v)
#   C[u].append((i, x, y, 1))
#   C[v].append((i, x, y, 1))
#   C[a].append((i, x, y, -2))
# dist = 0
# stack = [0]
# def dfs2(v):
#   global dist
#   for i, x, y, b in C[v]:
#     A[i] += (dist + num[x]*y - cum[x]) * b
#   for nv, c, d in edge[v]:
#     c+=1
#     if nv ==pars[v]:continue
#     dist += d
#     num[c] += 1
#     cum[c] += d
#     dfs2(nv)
#     dist -= d
#     num[c] -= 1
#     cum[c] -= d
# dfs2(0)
# print(*A, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6+1) #再帰関数の上限,10**5以上の場合python


def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None


#N, Q = map(int, input().split())
N, Q = map(int, input().split())
#A = tuple(map(int, input().split())) #1行ベクトル
#L = tuple(int(input()) for i in range(N)) #改行ベクトル
#S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

edge = [[] for i in range(N)]
for i in range(N-1):#木の場合M=N-1
    a,b,c,w = map(int,input().split())
    edge[a-1].append((b-1,c-1,w))
    edge[b-1].append((a-1,c-1,w)) #有向のばあいコメントアウト



#ダブリングによるLCA, 前処理NlogN, 呼び出しlogN, 安定  
def dfs(start):
    q=[(start,-1,0,0)]
    pars=[-1]*N
    depth=[-1]*N
    dist=[-1]*N
    while len(q):
        e,p,d,dis=q.pop()#ここをpopleftにすると幅優先探索BFSになる
        if depth[e]!=-1:continue
        pars[e]=p
        depth[e]=d
        dist[e]=dis
        for ne,c,w in edge[e]:
            q.append((ne,e,d+1,dis+w))
    return pars,depth,dist
pars,d,dist=dfs(0)
ln=N.bit_length()
dp=[[-1]*N for _ in range(ln+1)]
dp[0]=pars
for i in range(1,ln+1):
    for j in range(N):
        dp[i][j]=dp[i-1][dp[i-1][j]]


# LCAの計算
def lca(u, v):
    du = d[u]; dv = d[v]
    if du > dv:
        du, dv = dv, du
        u,v=v,u
    dif=dv-du
    for i in range(ln+1):
        if (dif>>i)&1:
            v=dp[i][v]
    if u==v:return u
    for i in range(ln,-1,-1):
        pu=dp[i][u];pv=dp[i][v]
        if pu!=pv:
            u,v=pu,pv
    return pars[u]

q=Q
qs = tuple(tuple(map(int, input().split())) for i in range(Q)) #改行行列
ans=[0]*Q
qn=[[] for _ in range(N)]
for i,(x,y,u,v) in enumerate(qs):
    ans[i]=dist[u-1]+dist[v-1]-dist[lca(u-1,v-1)]
    qn[u-1].append((i,x-1,y,1))
    qn[v-1].append((i,x-1,y,1))
    qn[lca(u-1,v-1)].append((i,x-1,y,2))
cnt=[0]*Q
#printe(qn)

qc=[[0,0] for _ in range(Q)]
cc=[[0,0] for _ in range(N-1)]

dfq=[(0,None,0,-1)]
def dfs2(e,c,d,p):
    if c!=None:
        cc[c][0]+=1
        cc[c][1]+=d
    for qi,x,y,sgn in qn[e]:
        ans[qi]+=(y*cc[x][0]-cc[x][1])*sgn
    for ne,nc,nd in edge[e]:
        if ne==pars[e]:continue
        dfs2(ne,nc,nd,e)
    if c!=None:
        cc[c][0]-=1
        cc[c][1]-=d
dfs2(0,-1,0,None)
printl(ans)

# n=N
# A = [0]*q
# C = [[] for _ in range(n)]
# num = [0]*n
# cum = [0]*n
# for i in range(q):
#   x, y, u, v = map(int, input().split())
#   u -= 1
#   v -= 1
#   a = lca(u, v)
#   C[u].append((i, x, y, 1))
#   C[v].append((i, x, y, 1))
#   C[a].append((i, x, y, -2))
# dist = 0
# stack = [0]
# def dfs2(v):
#   global dist
#   for i, x, y, b in C[v]:
#     A[i] += (dist + num[x]*y - cum[x]) * b
#   for nv, c, d in edge[v]:
#     c+=1
#     if nv ==pars[v]:continue
#     dist += d
#     num[c] += 1
#     cum[c] += d
#     dfs2(nv)
#     dist -= d
#     num[c] -= 1
#     cum[c] -= d
# dfs2(0)
# print(*A, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():

    #N, Q = map(int, input().split())
    N, Q = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    edge = [[] for i in range(N)]
    for i in range(N-1):#木の場合M=N-1
        a,b,c,w = map(int,input().split())
        edge[a-1].append((b-1,c-1,w))
        edge[b-1].append((a-1,c-1,w)) #有向のばあいコメントアウト

    qs = tuple(tuple(map(int, input().split())) for i in range(Q)) #改行行列

    #ダブリングによるLCA, 前処理NlogN, 呼び出しlogN, 安定  
    def dfs(start):
        q=[(start,-1,0,0)]
        pars=[-1]*N
        depth=[-1]*N
        dist=[-1]*N
        while len(q):
            e,p,d,dis=q.pop()#ここをpopleftにすると幅優先探索BFSになる
            if depth[e]!=-1:continue
            pars[e]=p
            depth[e]=d
            dist[e]=dis
            for ne,c,w in edge[e]:
                q.append((ne,e,d+1,dis+w))
        return pars,depth,dist
    pars,d,dist=dfs(0)
    ln=N.bit_length()
    dp=[[-1]*N for _ in range(ln+1)]
    dp[0]=pars
    for i in range(1,ln+1):
        for j in range(N):
            dp[i][j]=dp[i-1][dp[i-1][j]]
    
    
    # LCAの計算
    def lca(u, v):
        du = d[u]; dv = d[v]
        if du > dv:
            du, dv = dv, du
            u,v=v,u
        dif=dv-du
        for i in range(ln+1):
            if (dif>>i)&1:
                v=dp[i][v]
        if u==v:return u
        for i in range(ln,-1,-1):
            pu=dp[i][u];pv=dp[i][v]
            if pu!=pv:
                u,v=pu,pv
        return pars[u]
    
    ans=[0]*Q
    qn=[[] for _ in range(N)]
    for i,(x,y,u,v) in enumerate(qs):
        ans[i]=dist[u-1]+dist[v-1]-dist[lca(u-1,v-1)]
        qn[u-1].append((i,x-1,y))
        qn[v-1].append((i,x-1,y))
    cnt=[0]*Q
    #printe(qn)

    qc=[[0,0] for _ in range(Q)]
    cc=[[0,0] for _ in range(N-1)]
    def dfs2(e,c,d,p):
        if c!=None:
            cc[c][0]+=1
            cc[c][1]+=d
        for qi,x,y in qn[e]:
            if cnt[qi]==0:
                qc[qi][0]-=cc[x][0]
                qc[qi][1]-=cc[x][1]
            elif cnt[qi]==1:
                qc[qi][0]+=cc[x][0]
                qc[qi][1]+=cc[x][1]
                ans[qi]+=y*qc[qi][0]-qc[qi][1]
            cnt[qi]+=1
        for ne,nc,nd in edge[e]:
            if ne==p:continue
            dfs2(ne,nc,nd,e)
        if c!=None:
            cc[c][0]+=1
            cc[c][1]+=d
    dfs2(0,None,0,-1)
    printl(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

class LCA:
    def __init__(self, edge, root):
        self.l = len(edge)
        self.stack = []
        self.stack.append((root, 0))
        self.vs = []
        self.depth = [0]*self.l
        self.firstVisited = [-1]*self.l
        while self.stack:
            v, d = self.stack[-1]
            if self.firstVisited[v] == -1:
                self.firstVisited[v] = len(self.vs)
            self.vs.append(v)
            self.depth[v] = d
            if edge[v]:
                self.stack.append((edge[v].pop(), d+1))
            else:
                self.stack.pop()
        
        self.n = len(self.vs)
        self.INF = (self.l, self.l)
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [self.INF]*(self.N0 << 1)
        for i, v in enumerate(self.vs, self.N0):
            self.seg[i] = (self.depth[v], v)
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = min(self.seg[2*i], self.seg[2*i+1])
    
    def _query(self, l, r):
        res = self.INF
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = min(res, self.seg[r-1])
            if l & 1:
                res = min(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res

    def query(self, u, v):
        fu, fv = self.firstVisited[u], self.firstVisited[v]
        if fu > fv:
            fu, fv = fv, fu
        return self._query(fu, fv+1)[1]

n, q = map(int, input().split())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b, c, d = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append((b, c, d))
  T[b].append((a, c, d))
G = [[] for _ in range(n)]
edge = [[] for _ in range(n)]
stack = [(0, -1)]
while stack:
  v, par = stack.pop()
  for nv, c, d in T[v]:
    if nv == par:
      continue
    G[v].append((nv, c, d))
    edge[v].append(nv)
    stack.append((nv, v))

seg = LCA(edge, 0)
A = [0]*q
C = [[] for _ in range(n)]
num = [0]*n
cum = [0]*n
for i in range(q):
  x, y, u, v = map(int, input().split())
  u -= 1
  v -= 1
  a = seg.query(u, v)
  C[u].append((i, x, y, 1))
  C[v].append((i, x, y, 1))
  C[a].append((i, x, y, -1))
dist = 0
stack = [0]
def dfs(v):
  global dist
  for i, x, y, b in C[v]:
    A[i] += (dist + num[x]*y - cum[x]) * b
  for nv, c, d in G[v]:
    dist += d
    num[c] += 1
    cum[c] += d
    dfs(nv)
    dist -= d
    num[c] -= 1
    cum[c] -= d
dfs(0)
print(*A, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,init=True):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+1,root_v=0):
        q=deque()
        q.append((-1,x))
        depth=[None]*self.size
        depth[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if depth[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    depth[nb]=func(depth[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        self.ETtable=et[:]
        self.ETdepth=[depth[i] for i in et]
        self.ETid=vid[:]
        return depth,et,vid

    def FastEulerTour(self,x,func=lambda prv,nx,dist:prv+1,root_v=0):
        q=deque()
        q.append(x)
        depth=[None]*self.size
        depth[x]=root_v
        self.ETtable=[]
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                #cb,ce=q.pop()
                #et.append(ce)
                for nb,d in self.edges[ce]:
                    if depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        #q.append((nb,ce))
                        #q.append((ce,nb))
                        depth[nb]=depth[ce]+1
            self.ETtable.append(ce)
            
        self.ETid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(self.ETtable):
            if self.ETid[j][0]==-1:
                self.ETid[j][0]=i
            else:
                self.ETid[j][1]=i
        
        self.ETdepth=[depth[i] for i in self.ETtable]
        return depth
    
    def LCA_init(self,root):
        self.EulerTour(root,func=lambda prv,nx,dist:prv+dist,root_v=0)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETid[x]
        yin,yout=self.ETid[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        #show((xin,xout),(yin,yout),(a,b),id_of_min_dep_in_et)
        return self.ETtable[id_of_min_dep_in_et]

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1

        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][r-(1<<N)])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][r-(1<<N)]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][r-(1<<N)]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])
        
    def print(self):
        for i in self.table:
            print(*i)

show_flg=False
show_flg=True
ans=0


n,q=LI()
ls=[]
col=dict()
e_len=dict()
for i in range(n-1):
    a,b,c,d=LI_()
    d+=1
    ls+=[(a,b,d)]
    if a>b:
        a,b=b,a
    col[a*n+b]=c
    e_len[a*n+b]=d

tr=Tree(init=False)
tr.listin(ls,index=0)

root=0
dist=tr.dfs(root,func=lambda prv_v,nx,dist:prv_v+dist)
dep=tr.FastEulerTour(root)