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: Time Limit Exceeded

Solution code:
# verified: ABC014-D
# calculate LCA O(logN) for each query

# kprev[k][i]: 2^k parent of node i 
# if there is no node returns "None"
# Depth[i]: Depth of node i from rootNode

class Doubling():
    def __init__(self, graph, Depth, prev, rootNode=0):
        self.graph = graph
        self.N = len(graph)
        self.Log_N = (self.N-1).bit_length()
        self.rootNode = rootNode
        # BFSしない
        self.prev = prev 
        self.Depth = Depth

        # construct
        self.kprev = [self.prev]
        S = self.prev
        for k in range(self.Log_N):
            T = [None]*self.N
            for i in range(self.N):
                if S[i] is None:
                    continue
                T[i] = S[S[i]]
            self.kprev.append(T)
            S = T

    # LCA
    def LCAquery(self, u, v):
        dd = self.Depth[v] - self.Depth[u]
        if dd < 0:
            u, v = v, u
            dd = -dd
        
        # set same Depth
        for k in range(self.Log_N+1):
            if dd & 1:
                v = self.kprev[k][v]
            dd >>= 1
        
        if u == v:
            return u
        
        for k in reversed(range(self.Log_N)):
            pu = self.kprev[k][u]
            pv = self.kprev[k][v]
            if pu != pv:
                u, v = pu, pv
        
        return self.kprev[0][u]

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from bisect import bisect_right

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

Query = [list(map(int, input().split())) for _ in range(Q)]


D = [-1]*N
D[0] = 0
EulerTour = [(0, +1)]
Color = [0]*N
Weight = [0]*N
PointFront = [0]*N
prev = [None]*N
Depth = [0]*N
def dfs(p):
    PointFront[p] = len(EulerTour)
    EulerTour.append((p, +1))
    for np, c, d in graph[p]:
        if D[np] == -1:
            Color[np] = c
            Weight[np] = d
            D[np] = D[p] + d
            Depth[np] = Depth[p] + 1
            prev[np] = p
            dfs(np)
    EulerTour.append((p, -1))

def dfs2():
    stack = [0]
    while stack:
        p = stack[-1]
        for np, c, d in graph[p]:
            if D[np] == -1:
                PointFront[np] = len(EulerTour)
                EulerTour.append((np, +1))
                Color[np] = c
                Weight[np] = d
                D[np] = D[p] + d
                Depth[np] = Depth[p] + 1
                prev[np] = p
                stack.append(np)
                break
        if p == stack[-1]:
            EulerTour.append((p, -1))    
            stack.pop()
            

dfs(0)


Indexes = [[] for _ in range(N)]
Weights = [[0] for _ in range(N)]
Colors = [[0] for _ in range(N)]
for i, (p, num) in enumerate(EulerTour):
    if p == 0: continue
    w = Weight[p]*num
    c = Color[p]
    Weights[c].append(Weights[c][-1]+w)
    Colors[c].append(Colors[c][-1]+num)
    Indexes[c].append(i)



# point までにある color 指定された時のスコア
def fixed_score(point, color, replace):
    ind = bisect_right(Indexes[color], PointFront[point])
    return D[point] - Weights[color][ind] + Colors[color][ind]*replace


def main():
    doubling = Doubling(graph, Depth, prev)
    ans = []
    for x, y, u, v in Query:
        u -= 1; v -= 1
        lca = doubling.LCAquery(u, v)
        ans.append(fixed_score(u, x, y) + fixed_score(v, x, y) - 2*fixed_score(lca, x, y))
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# verified: ABC014-D
# calculate LCA O(logN) for each query

# kprev[k][i]: 2^k parent of node i 
# if there is no node returns "None"
# Depth[i]: Depth of node i from rootNode

class Doubling():
    def __init__(self, graph, Depth, prev, rootNode=0):
        self.graph = graph
        self.N = len(graph)
        self.Log_N = (self.N-1).bit_length()
        self.rootNode = rootNode
        # BFSしない
        self.prev = prev 
        self.Depth = Depth

        # construct
        self.kprev = [self.prev]
        S = self.prev
        for k in range(self.Log_N):
            T = [None]*self.N
            for i in range(self.N):
                if S[i] is None:
                    continue
                T[i] = S[S[i]]
            self.kprev.append(T)
            S = T

    # LCA
    def LCAquery(self, u, v):
        dd = self.Depth[v] - self.Depth[u]
        if dd < 0:
            u, v = v, u
            dd = -dd
        
        # set same Depth
        for k in range(self.Log_N+1):
            if dd & 1:
                v = self.kprev[k][v]
            dd >>= 1
        
        if u == v:
            return u
        
        for k in reversed(range(self.Log_N)):
            pu = self.kprev[k][u]
            pv = self.kprev[k][v]
            if pu != pv:
                u, v = pu, pv
        
        return self.kprev[0][u]

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10**6)
from bisect import bisect_right

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

Query = [list(map(int, input().split())) for _ in range(Q)]


D = [-1]*N
D[0] = 0
EulerTour = [(0, +1)]
Color = [0]*N
Weight = [0]*N
PointFront = [0]*N
prev = [None]*N
Depth = [0]*N
# def dfs(p):
#     PointFront[p] = len(EulerTour)
#     EulerTour.append((p, True))
#     for np, c, d in graph[p]:
#         if D[np] == -1:
#             Color[np] = c
#             Weight[np] = d
#             D[np] = D[p] + d
#             dfs(np)
#     EulerTour.append((p, False))

def dfs2():
    stack = [0]
    while stack:
        p = stack[-1]
        for np, c, d in graph[p]:
            if D[np] == -1:
                PointFront[np] = len(EulerTour)
                EulerTour.append((np, +1))
                Color[np] = c
                Weight[np] = d
                D[np] = D[p] + d
                Depth[np] = Depth[p] + 1
                prev[np] = p
                stack.append(np)
                break
        if p == stack[-1]:
            EulerTour.append((p, -1))    
            stack.pop()
            

dfs2()


Indexes = [[] for _ in range(N)]
Weights = [[0] for _ in range(N)]
Colors = [[0] for _ in range(N)]
for i, (p, num) in enumerate(EulerTour):
    if p == 0: continue
    w = Weight[p]*num
    c = Color[p]
    Weights[c].append(Weights[c][-1]+w)
    Colors[c].append(Colors[c][-1]+num)
    Indexes[c].append(i)



# point までにある color 指定された時のスコア
def fixed_score(point, color, replace):
    ind = bisect_right(Indexes[color], PointFront[point])
    return D[point] - Weights[color][ind] + Colors[color][ind]*replace


def main():
    doubling = Doubling(graph, Depth, prev)
    ans = []
    for x, y, u, v in Query:
        u -= 1; v -= 1
        lca = doubling.LCAquery(u, v)
        ans.append(fixed_score(u, x, y) + fixed_score(v, x, y) - 2*fixed_score(lca, x, y))
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# verified: ABC014-D
# calculate LCA O(logN) for each query

# kprev[k][i]: 2^k parent of node i 
# if there is no node returns "None"
# Depth[i]: Depth of node i from rootNode

class Doubling():
    def __init__(self, graph, rootNode=0):
        self.graph = graph
        self.N = len(graph)
        self.Log_N = (self.N-1).bit_length()
        self.rootNode = rootNode
        # BFS
        self.prev = [None]*self.N
   
        self.Depth = [-1]*self.N
        q = [self.rootNode]
        self.Depth[self.rootNode] = 0
        d = 0
        while q:
            qq = []
            d += 1
            for p in q:
                for np, _, _ in self.graph[p]:
                    if self.Depth[np] == -1:
                        self.prev[np] = p
                        self.Depth[np] = d
                        qq.append(np)
            q = qq

        # construct
        self.kprev = [self.prev]
        S = self.prev
        for k in range(self.Log_N):
            T = [None]*self.N
            for i in range(self.N):
                if S[i] is None:
                    continue
                T[i] = S[S[i]]
            self.kprev.append(T)
            S = T

    # LCA
    def LCAquery(self, u, v):
        dd = self.Depth[v] - self.Depth[u]
        if dd < 0:
            u, v = v, u
            dd = -dd
        
        # set same Depth
        for k in range(self.Log_N+1):
            if dd & 1:
                v = self.kprev[k][v]
            dd >>= 1
        
        if u == v:
            return u
        
        for k in reversed(range(self.Log_N)):
            pu = self.kprev[k][u]
            pv = self.kprev[k][v]
            if pu != pv:
                u, v = pu, pv
        
        return self.kprev[0][u]

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10**6)
from bisect import bisect_right

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

Query = [list(map(int, input().split())) for _ in range(Q)]

doubling = Doubling(graph)

D = [-1]*N
D[0] = 0
EulerTour = [(0, True)]
Color = [0]*N
Weight = [0]*N
PointFront = [0]*N
PointFront[0] = 0

# def dfs(p):
#     PointFront[p] = len(EulerTour)
#     EulerTour.append((p, True))
#     for np, c, d in graph[p]:
#         if D[np] == -1:
#             Color[np] = c
#             Weight[np] = d
#             D[np] = D[p] + d
#             dfs(np)
#     EulerTour.append((p, False))

def dfs2():
    stack = [0]
    while stack:
        p = stack[-1]
        for np, c, d in graph[p]:
            if D[np] == -1:
                PointFront[np] = len(EulerTour)
                EulerTour.append((np, +1))
                Color[np] = c
                Weight[np] = d
                D[np] = D[p] + d
                stack.append(np)
                break
        if p == stack[-1]:
            EulerTour.append((p, -1))    
            stack.pop()
            

dfs2()
Indexes = [[] for _ in range(N)]
Weights = [[0] for _ in range(N)]
Colors = [[0] for _ in range(N)]
for i, (p, num) in enumerate(EulerTour):
    if p == 0: continue
    w = Weight[p]*num
    c = Color[p]
    Weights[c].append(Weights[c][-1]+w)
    Colors[c].append(Colors[c][-1]+num)
    Indexes[c].append(i)

# point までにある color 指定された時のスコア
def fixed_score(point, color, replace):
    ind = bisect_right(Indexes[color], PointFront[point])
    return D[point] - Weights[color][ind] + Colors[color][ind]*replace


def main():
    ans = []
    for x, y, u, v in Query:
        u -= 1; v -= 1
        lca = doubling.LCAquery(u, v)
        ans.append(fixed_score(u, x, y) + fixed_score(v, x, y) - 2*fixed_score(lca, x, y))
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# verified: ABC014-D
# calculate LCA O(logN) for each query

# kprev[k][i]: 2^k parent of node i 
# if there is no node returns "None"
# Depth[i]: Depth of node i from rootNode

class Doubling():
    def __init__(self, graph, rootNode=0):
        self.graph = graph
        self.N = len(graph)
        self.Log_N = (self.N-1).bit_length()
        self.rootNode = rootNode
        # BFS
        self.prev = [None]*self.N
   
        self.Depth = [-1]*self.N
        q = [self.rootNode]
        self.Depth[self.rootNode] = 0
        d = 0
        while q:
            qq = []
            d += 1
            for p in q:
                for np, _, _ in self.graph[p]:
                    if self.Depth[np] == -1:
                        self.prev[np] = p
                        self.Depth[np] = d
                        qq.append(np)
            q = qq

        # construct
        self.kprev = [self.prev]
        S = self.prev
        for k in range(self.Log_N):
            T = [None]*self.N
            for i in range(self.N):
                if S[i] is None:
                    continue
                T[i] = S[S[i]]
            self.kprev.append(T)
            S = T

    # LCA
    def LCAquery(self, u, v):
        dd = self.Depth[v] - self.Depth[u]
        if dd < 0:
            u, v = v, u
            dd = -dd
        
        # set same Depth
        for k in range(self.Log_N+1):
            if dd & 1:
                v = self.kprev[k][v]
            dd >>= 1
        
        if u == v:
            return u
        
        for k in reversed(range(self.Log_N)):
            pu = self.kprev[k][u]
            pv = self.kprev[k][v]
            if pu != pv:
                u, v = pu, pv
        
        return self.kprev[0][u]

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10**6)
from bisect import bisect_right

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

Query = [list(map(int, input().split())) for _ in range(Q)]

doubling = Doubling(graph)

D = [-1]*N
D[0] = 0
EulerTour = [(0, True)]
Color = [None]*N
Weight = [None]*N
PointFront = [None]*N
PointFront[0] = 0

# def dfs(p):
#     PointFront[p] = len(EulerTour)
#     EulerTour.append((p, True))
#     for np, c, d in graph[p]:
#         if D[np] == -1:
#             Color[np] = c
#             Weight[np] = d
#             D[np] = D[p] + d
#             dfs(np)
#     EulerTour.append((p, False))

def dfs2():
    stack = [0]
    while stack:
        p = stack[-1]
        update = False
        for np, c, d in graph[p]:
            if D[np] == -1:
                update = True
                PointFront[np] = len(EulerTour)
                EulerTour.append((np, +1))
                Color[np] = c
                Weight[np] = d
                D[np] = D[p] + d
                stack.append(np)
                break
        if not update:
            EulerTour.append((p, -1))    
            stack.pop()
            

dfs2()
Indexes = [[] for _ in range(N)]
Weights = [[0] for _ in range(N)]
Colors = [[0] for _ in range(N)]
for i, (p, num) in enumerate(EulerTour):
    if p == 0: continue
    w = Weight[p]*num
    c = Color[p]
    Weights[c].append(Weights[c][-1]+w)
    Colors[c].append(Colors[c][-1]+num)
    Indexes[c].append(i)

# point までにある color 指定された時のスコア
def fixed_score(point, color, replace):
    ind = bisect_right(Indexes[color], PointFront[point])
    return D[point] - Weights[color][ind] + Colors[color][ind]*replace


def main():
    ans = []
    for x, y, u, v in Query:
        u -= 1; v -= 1
        lca = doubling.LCAquery(u, v)
        ans.append(fixed_score(u, x, y) + fixed_score(v, x, y) - 2*fixed_score(lca, x, y))
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# verified: ABC014-D
# calculate LCA O(logN) for each query

# kprev[k][i]: 2^k parent of node i 
# if there is no node returns "None"
# Depth[i]: Depth of node i from rootNode

class Doubling():
    def __init__(self, graph, rootNode=0):
        self.graph = graph
        self.N = len(graph)
        self.Log_N = (self.N-1).bit_length()
        self.rootNode = rootNode
        # BFS
        self.prev = [None]*self.N
   
        self.Depth = [-1]*self.N
        q = [self.rootNode]
        self.Depth[self.rootNode] = 0
        d = 0
        while q:
            qq = []
            d += 1
            for p in q:
                for np, _, _ in self.graph[p]:
                    if self.Depth[np] == -1:
                        self.prev[np] = p
                        self.Depth[np] = d
                        qq.append(np)
            q = qq

        # construct
        self.kprev = [self.prev]
        S = self.prev
        for k in range(self.Log_N):
            T = [None]*self.N
            for i in range(self.N):
                if S[i] is None:
                    continue
                T[i] = S[S[i]]
            self.kprev.append(T)
            S = T

    # LCA
    def LCAquery(self, u, v):
        dd = self.Depth[v] - self.Depth[u]
        if dd < 0:
            u, v = v, u
            dd = -dd
        
        # set same Depth
        for k in range(self.Log_N+1):
            if dd & 1:
                v = self.kprev[k][v]
            dd >>= 1
        
        if u == v:
            return u
        
        for k in reversed(range(self.Log_N)):
            pu = self.kprev[k][u]
            pv = self.kprev[k][v]
            if pu != pv:
                u, v = pu, pv
        
        return self.kprev[0][u]

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10**6)
from bisect import bisect_right

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

Query = [list(map(int, input().split())) for _ in range(Q)]

doubling = Doubling(graph)

D = [-1]*N
D[0] = 0
EulerTour = [(0, True)]
Color = [None]*N
Weight = [None]*N
PointFront = [None]*N
PointFront[0] = 0

# def dfs(p):
#     PointFront[p] = len(EulerTour)
#     EulerTour.append((p, True))
#     for np, c, d in graph[p]:
#         if D[np] == -1:
#             Color[np] = c
#             Weight[np] = d
#             D[np] = D[p] + d
#             dfs(np)
#     EulerTour.append((p, False))

def dfs2():
    stack = [0]
    while stack:
        p = stack[-1]
        update = False
        for np, c, d in graph[p]:
            if D[np] == -1:
                update = True
                PointFront[np] = len(EulerTour)
                EulerTour.append((np, True))
                Color[np] = c
                Weight[np] = d
                D[np] = D[p] + d
                stack.append(np)
                break
        if not update:
            EulerTour.append((p, False))    
            stack.pop()
            

dfs2()
Indexes = [[] for _ in range(N)]
Weights = [[0] for _ in range(N)]
Colors = [[0] for _ in range(N)]
for i, (p, go) in enumerate(EulerTour):
    if p == 0: continue
    w = Weight[p] if go else -Weight[p]
    num = +1 if go else -1
    c = Color[p]
    Weights[c].append(Weights[c][-1]+w)
    Colors[c].append(Colors[c][-1]+num)
    Indexes[c].append(i)

# point までにある color 指定された時のスコア
def fixed_score(point, color, replace):
    ind_euler = PointFront[point]
    ind = bisect_right(Indexes[color], ind_euler)
    return D[point] - Weights[color][ind] + Colors[color][ind]*replace


for x, y, u, v in Query:
    u -= 1; v -= 1
    lca = doubling.LCAquery(u, v)
    u_fixed = fixed_score(u, x, y)
    v_fixed = fixed_score(v, x, y)
    l_fixed = fixed_score(lca, x, y)
    ans = u_fixed + v_fixed - 2*l_fixed
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# verified: ABC014-D
# calculate LCA O(logN) for each query

# kprev[k][i]: 2^k parent of node i 
# if there is no node returns "None"
# Depth[i]: Depth of node i from rootNode

class Doubling():
    def __init__(self, graph, rootNode=0):
        self.graph = graph
        self.N = len(graph)
        self.Log_N = (self.N-1).bit_length()
        self.rootNode = rootNode
        # BFS
        self.prev = [None]*self.N
   
        self.Depth = [-1]*self.N
        q = [self.rootNode]
        self.Depth[self.rootNode] = 0
        d = 0
        while q:
            qq = []
            d += 1
            for p in q:
                for np, _, _ in self.graph[p]:
                    if self.Depth[np] == -1:
                        self.prev[np] = p
                        self.Depth[np] = d
                        qq.append(np)
            q = qq

        # construct
        self.kprev = [self.prev]
        S = self.prev
        for k in range(self.Log_N):
            T = [None]*self.N
            for i in range(self.N):
                if S[i] is None:
                    continue
                T[i] = S[S[i]]
            self.kprev.append(T)
            S = T

    # LCA
    def LCAquery(self, u, v):
        dd = self.Depth[v] - self.Depth[u]
        if dd < 0:
            u, v = v, u
            dd = -dd
        
        # set same Depth
        for k in range(self.Log_N+1):
            if dd & 1:
                v = self.kprev[k][v]
            dd >>= 1
        
        if u == v:
            return u
        
        for k in reversed(range(self.Log_N)):
            pu = self.kprev[k][u]
            pv = self.kprev[k][v]
            if pu != pv:
                u, v = pu, pv
        
        return self.kprev[0][u]

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from bisect import bisect_right

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

Query = [list(map(int, input().split())) for _ in range(Q)]

doubling = Doubling(graph)

D = [-1]*N
D[0] = 0
EulerTour = []
Color = [None]*N
Weight = [None]*N
PointFront = [None]*N

def dfs(p):
    PointFront[p] = len(EulerTour)
    EulerTour.append((p, True))
    for np, c, d in graph[p]:
        if D[np] == -1:
            Color[np] = c
            Weight[np] = d
            D[np] = D[p] + d
            dfs(np)
    EulerTour.append((p, False))

dfs(0)
Indexes = [[] for _ in range(N)]
Weights = [[0] for _ in range(N)]
Colors = [[0] for _ in range(N)]
for i, (p, go) in enumerate(EulerTour):
    if p == 0: continue
    w = Weight[p] if go else -Weight[p]
    num = +1 if go else -1
    c = Color[p]
    Weights[c].append(Weights[c][-1]+w)
    Colors[c].append(Colors[c][-1]+num)
    Indexes[c].append(i)

# point までにある color 指定された時のスコア
def fixed_score(point, color, replace):
    ind_euler = PointFront[point]
    ind = bisect_right(Indexes[color], ind_euler)
    return D[point] - Weights[color][ind] + Colors[color][ind]*replace


for x, y, u, v in Query:
    u -= 1; v -= 1
    lca = doubling.LCAquery(u, v)
    u_fixed = fixed_score(u, x, y)
    v_fixed = fixed_score(v, x, y)
    l_fixed = fixed_score(lca, x, y)
    ans = u_fixed + v_fixed - 2*l_fixed
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.buffer.readline()[:-1]

class LCA():
	def __init__(self, adj_given, root_given):
		self.adj = adj = adj_given
		self.root = root_given
		self.n = n = len(adj)
		self.maxlog = 0
		while (1 << self.maxlog) < n:
			self.maxlog += 1
		maxlog = self.maxlog
		self.par = [[-1 for _ in range(n)] for _ in range(maxlog)]
		self.dep = [0 for _ in range(n)]
		self.num_key = [[0] for _ in range(n)]
		self.num_value = [[0] for _ in range(n)]
		self.sum_value = [[0] for _ in range(n)]
		self.first = [10**6 for _ in range(n)]
		self.first[self.root] = 0
		self.visited = 1
		self.cnt = 1
		self.dist = [0 for _ in range(n)]

	def dfs(self, x, pa, de, co, le):
		par = self.par
		dep = self.dep
		root = self.root
		
		par[0][x] = pa
		dep[x] = de

		if x != root and self.visited < n:
			self.num_key[co].append(self.cnt)
			self.num_value[co].append(self.num_value[co][-1] + 1)
			self.sum_value[co].append(self.sum_value[co][-1] + le)
			if self.first[x] == 10**6:
				self.visited += 1
				self.first[x] = self.cnt
			self.cnt += 1
			self.dist[x] = self.dist[pa] + le

		for v, c, l in adj[x]:
			if v != pa:
				self.dfs(v, x, de+1, c, l)

		if x != root and self.visited < n:
			self.num_key[co].append(self.cnt)
			self.num_value[co].append(self.num_value[co][-1] - 1)
			self.sum_value[co].append(self.sum_value[co][-1] - le)
			self.cnt += 1

		return

	def calc(self):
		root = self.root
		par = self.par
		maxlog = self.maxlog
		self.dfs(root, -1, 0, -1, 0)

		for k in range(maxlog-1):
			for v in range(n):
				if par[k][v] < 0:
					continue
				else:
					par[k+1][v] = par[k][par[k][v]]
		return

	def get_lca(self, u, v):
		par = self.par
		dep = self.dep
		maxlog = self.maxlog
		if dep[u] > dep[v]:
			u, v = v, u
		for k in range(maxlog):
			if ((dep[v] - dep[u]) >> k) & 1:
				v = par[k][v]

		if u == v:
			return u
		else:
			for k in range(maxlog-1, -1, -1):
				if par[k][u] != par[k][v]:
					u = par[k][u]
					v = par[k][v]
			return par[0][u]

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

lca = LCA(adj, 0)
lca.calc()

for _ in range(q):
	x, y, u, v = map(int, input().split())
	x, u, v = x-1, u-1, v-1
	a = lca.get_lca(u, v)
	id_u = max(bisect(lca.num_key[x], lca.first[u])-1, 0)
	id_v = max(bisect(lca.num_key[x], lca.first[v])-1, 0)
	id_a = max(bisect(lca.num_key[x], lca.first[a])-1, 0)

	dist_u = lca.dist[u] + lca.num_value[x][id_u] * y - lca.sum_value[x][id_u]
	dist_v = lca.dist[v] + lca.num_value[x][id_v] * y - lca.sum_value[x][id_v]
	dist_a = lca.dist[a] + lca.num_value[x][id_a] * y - lca.sum_value[x][id_a]
	print(dist_u + dist_v - 2 * dist_a)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.buffer.readline()[:-1]


class LCA():
	def __init__(self, adj_given, root_given):
		self.adj = adj = adj_given
		self.root = root_given
		self.n = n = len(adj)
		self.maxlog = 0
		while (1 << self.maxlog) < n:
			self.maxlog += 1
		maxlog = self.maxlog
		self.par = [[-1 for _ in range(n)] for _ in range(maxlog)]
		self.dep = [0 for _ in range(n)]
		self.num_key = [[0] for _ in range(n)]
		self.num_value = [[0] for _ in range(n)]
		self.sum_value = [[0] for _ in range(n)]
		self.first = [10**6 for _ in range(n)]
		self.first[self.root] = 0
		self.cnt = 1
		self.dist = [0 for _ in range(n)]

	def dfs(self, x, pa, de, co, le):
		par = self.par
		dep = self.dep
		root = self.root
		
		par[0][x] = pa
		dep[x] = de

		if x != root:
			self.num_key[co].append(self.cnt)
			self.num_value[co].append(self.num_value[co][-1] + 1)
			self.sum_value[co].append(self.sum_value[co][-1] + le)
			self.first[x] = min(self.first[x], self.cnt)
			self.cnt += 1
			self.dist[x] = self.dist[pa] + le

		for v, c, l in adj[x]:
			if v != pa:
				self.dfs(v, x, de+1, c, l)

		if x != root:
			self.num_key[co].append(self.cnt)
			self.num_value[co].append(self.num_value[co][-1] - 1)
			self.sum_value[co].append(self.sum_value[co][-1] - le)
			self.cnt += 1

		return

	def calc(self):
		root = self.root
		par = self.par
		maxlog = self.maxlog
		self.dfs(root, -1, 0, -1, 0)

		for k in range(maxlog-1):
			for v in range(n):
				if par[k][v] < 0:
					continue
				else:
					par[k+1][v] = par[k][par[k][v]]
		return

	def get_lca(self, u, v):
		par = self.par
		dep = self.dep
		maxlog = self.maxlog
		if dep[u] > dep[v]:
			u, v = v, u
		for k in range(maxlog):
			if ((dep[v] - dep[u]) >> k) & 1:
				v = par[k][v]

		if u == v:
			return u
		else:
			for k in range(maxlog-1, -1, -1):
				if par[k][u] != par[k][v]:
					u = par[k][u]
					v = par[k][v]
			return par[0][u]

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

lca = LCA(adj, 0)
lca.calc()

for _ in range(q):
	x, y, u, v = map(int, input().split())
	x, u, v = x-1, u-1, v-1
	a = lca.get_lca(u, v)
	id_u = max(bisect(lca.num_key[x], lca.first[u])-1, 0)
	id_v = max(bisect(lca.num_key[x], lca.first[v])-1, 0)
	id_a = max(bisect(lca.num_key[x], lca.first[a])-1, 0)

	dist_u = lca.dist[u] + lca.num_value[x][id_u] * y - lca.sum_value[x][id_u]
	dist_v = lca.dist[v] + lca.num_value[x][id_v] * y - lca.sum_value[x][id_v]
	dist_a = lca.dist[a] + lca.num_value[x][id_a] * y - lca.sum_value[x][id_a]
	print(dist_u + dist_v - 2 * dist_a)