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,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=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        depth[nb]=depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return depth
    
    def LCA_init(self,root):
        self.FastEulerTour(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.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[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)
et=tr.ETtable


ad=[[0] for i in range(n)]
an=[[0] for i in range(n)]
index=[[] for i in range(n)]
for i in range(2*n-1-1):
    a,b=et[i],et[i+1]
    sign=1 if dep[a]<dep[b] else -1
    if a>b:
        a,b=b,a
    c=col[a*n+b]
    dd=e_len[a*n+b]*sign
    an[c]+=[an[c][-1]+sign]
    ad[c]+=[ad[c][-1]+dd]
    index[c]+=[i]

for i in range(q):
    x,y,u,v=LI_()
    y+=1
    lca=tr.LCA(root,u,v)
    dist_u=dist[u]-dist[lca]
    dist_v=dist[v]-dist[lca]
    path=dist_u+dist_v
    
    ui=bisect.bisect_left(index[x],tr.ETin[u])
    vi=bisect.bisect_left(index[x],tr.ETin[v])
    #show(vi,bisect.bisect(index[x],vid[v][0]),(index[x],vid[v][0]))
    ai=bisect.bisect_left(index[x],tr.ETin[lca])
    ui=min(ui,len(index[x]))
    vi=min(vi,len(index[x]))
    ai=min(ai,len(index[x]))
    
    c_dist_u=ad[x][ui]-ad[x][ai]
    c_dist_v=ad[x][vi]-ad[x][ai]
    c_path=c_dist_u+c_dist_v
    c_n_u=an[x][ui]-an[x][ai]
    c_n_v=an[x][vi]-an[x][ai]
    c_n=c_n_u+c_n_v
    #ri=bisect.bisect_right(index[x],r)
    ans=path-c_path+c_n*y
    #show(ans,'col',x,(lca,(u,v)),path,(vid[lca][0],(vid[u][0],vid[v][0])),(ai,(ui,vi)),c_path,(c_dist_u,c_dist_v),index[x],'# c_path',(c_n_u,c_n_v))
    
    print(ans)

Submission status: Accepted

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=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        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)
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        
        self.ETdepth=[depth[i] for i in self.ETtable]
        return depth
    
    def LCA_init(self,root):
        self.FastEulerTour(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.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[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)
et=tr.ETtable
#vid=tr.ETid

ad=[[0] for i in range(n)]
an=[[0] for i in range(n)]
index=[[] for i in range(n)]
for i in range(2*n-1-1):
    a,b=et[i],et[i+1]
    sign=1 if dep[a]<dep[b] else -1
    if a>b:
        a,b=b,a
    c=col[a*n+b]
    dd=e_len[a*n+b]*sign
    an[c]+=[an[c][-1]+sign]
    ad[c]+=[ad[c][-1]+dd]
    index[c]+=[i]
    

for i in range(q):
    x,y,u,v=LI_()
    y+=1
    lca=tr.LCA(root,u,v)
    dist_u=dist[u]-dist[lca]
    dist_v=dist[v]-dist[lca]
    path=dist_u+dist_v
    
    ui=bisect.bisect_left(index[x],tr.ETin[u])
    vi=bisect.bisect_left(index[x],tr.ETin[v])
    #show(vi,bisect.bisect(index[x],vid[v][0]),(index[x],vid[v][0]))
    ai=bisect.bisect_left(index[x],tr.ETin[lca])
    ui=min(ui,len(index[x]))
    vi=min(vi,len(index[x]))
    ai=min(ai,len(index[x]))
    
    
    c_dist_u=ad[x][ui]-ad[x][ai]
    c_dist_v=ad[x][vi]-ad[x][ai]
    c_path=c_dist_u+c_dist_v
    c_n_u=an[x][ui]-an[x][ai]
    c_n_v=an[x][vi]-an[x][ai]
    c_n=c_n_u+c_n_v
    #ri=bisect.bisect_right(index[x],r)
    ans=path-c_path+c_n*y
    #show(ans,'col',x,(lca,(u,v)),path,(vid[lca][0],(vid[u][0],vid[v][0])),(ai,(ui,vi)),c_path,(c_dist_u,c_dist_v),index[x],'# c_path',(c_n_u,c_n_v))
    
    print(ans)

Submission status: Accepted

Solution code:
# ABC133 オイラーツアー
import sys
from collections import defaultdict
readline = sys.stdin.readline
N, Q = map(int, readline().split())

def dfs_w(v, d):
    vs = set([1])
    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 stack:
        v, cc, dpd = stack.pop()
        if v > 0:
            parent = path[-1]
            path.append(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
                vs.add(u)
                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[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 = 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())

def dfs_w(v, d):
    vs = set([1])
    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 stack:
        v, cc, dpd = stack.pop()
        if v > 0:
            parent = path[-1]
            path.append(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
                vs.add(u)
                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:
import bisect
from collections import deque


class LowestCommonAncestor():
    """根付き木に対して、二頂点の共通の祖先で最も近いところにある頂点を求める
    初期化(ダブリング配列parent[k][v]の構築): O(NlogN)
    lcaを求めるクエリ: O(logN)
    """
    def __init__(self, tree, root):
        self.n = len(tree)
        self.depth = [0] * self.n
        self.log_size = (self.n).bit_length()
        self.parent = [[-1] * self.n for i in range(self.log_size)]

        # 親を2^0回たどって到達する頂点、つまり現在の頂点に対する親の頂点を求める
        # parent[0][現在の頂点] = 親の頂点
        q = deque([(root, -1, 0)]) # (現在の地点, 親の頂点, 現在の頂点と親の頂点間の距離) 
        while q:
            v, par, dist = q.pop()
            self.parent[0][v] = par
            self.depth[v] = dist
            for child_v, _, _ in tree[v]:
                if child_v != par:
                    self.depth[child_v] = dist + 1
                    q.append((child_v, v, dist + 1))

        # ダブリングで親を2^k回たどって到達する頂点を求める
        for k in range(1, self.log_size):
            for v in range(self.n):
                self.parent[k][v] = self.parent[k-1][self.parent[k-1][v]]
            
    def lca(self, u, v):
        # u, vのうち深いところにある方から|depth[u] - depth[v]|だけ親をたどる
        if self.depth[u] > self.depth[v]:
            u, v = v, u
        for k in range(self.log_size):
            if (self.depth[v] - self.depth[u] >> k) & 1:
                v = self.parent[k][v]
        if u == v:
            return u
          
        # 二分探索でLCAを求める
        for k in reversed(range(self.log_size)):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]
 

def euler_tour(tree: list, root: int):
    """根をrootとしたときの辺に対するオイラーツアーを行う
    posの部分木が区間[begin[pos], end[pos])に対応する
    """
    n = len(tree)
    trail = []
    weight = []
    color = []
    begin = [-1] * n
    end = [-1] * n
    par = {root: -1}
    stack = [(root, 0, 0)]

    while stack:
        v, c, col = stack.pop()
        if v >= 0:  # 行きがけ順の処理
            trail.append(v)
            weight.append(c)
            color.append(col)
            begin[v] = len(trail) - 1
            end[v] = len(trail)
            stack.append((~v, -c, col))
            for nxt_v, nxt_c, nxt_col in tree[v]:
                if nxt_v not in par:
                    par[nxt_v] = v
                    stack.append((nxt_v, nxt_c, nxt_col))

        else:  # 帰りがけ順の処理
            if ~v == root:
                continue
            trail.append(par[~v])
            weight.append(c)
            color.append(col)
            end[par[~v]] = len(trail)

    return trail, weight, color, begin, end


n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n - 1)]
query = [list(map(int, input().split())) for i in range(q)]

tree = [[] for i in range(n)]
for a, b, col, dist in info:
    a -= 1
    b -= 1
    tree[a].append((b, dist, col))
    tree[b].append((a, dist, col))

trail, weight, color, begin, end = euler_tour(tree, 0)

# 辺の重みを色ごとに累積和する
w_col = [[0] for i in range(n)]
for i in range(len(weight)):
    col = color[i]
    w_col[col].append(weight[i] + w_col[col][-1])

# 辺の個数を色ごとに累積和する
cnt_col = [[0] for i in range(n)]
for i in range(len(weight)):
    col = color[i]
    cnt_col[col].append(int(2 * (weight[i] >= 1)) - 1 + cnt_col[col][-1])

# 色ごとのインデックス
ind = [[] for i in range(n)]
for i in range(len(weight)):
    col = color[i]
    ind[col].append(i)

# 辺の重みを累積和にする
for i in range(len(weight) - 1):
    weight[i + 1] += weight[i]

lca = LowestCommonAncestor(tree, 0)
for x, y, u, v in query:
    u -= 1
    v -= 1
    lca_uv = lca.lca(u, v)

    ans = weight[begin[u]] + weight[begin[v]] - 2 * weight[begin[lca_uv]]

    l = bisect.bisect_right(ind[x], begin[u])
    r = bisect.bisect_right(ind[x], begin[v])
    mid = bisect.bisect_right(ind[x], begin[lca_uv])
    
    cnt = cnt_col[x][r] + cnt_col[x][l] - 2 * cnt_col[x][mid]
    w = w_col[x][r] + w_col[x][l] - 2 * w_col[x][mid]
    
    print(abs(ans) + abs(cnt) * y - abs(w))