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:
import sys
sys.setrecursionlimit(100000)

class LCA(object):
    def __init__(self, to, root=0):
        self.__n = len(to)
        self.__to = to
        self.__logn = (self.__n-1).bit_length()
        self.__depth = [-1]*self.__n
        self.__dist = [-1]*self.__n
        self.__depth[root] = 0
        self.__dist[root] = 0
        self.__parents = [[-1]*self.__n for _ in range(self.__logn)]
        self.__dfs(root)
        self.__doubling()

    def __dfs(self, v):
        for u, c, d in self.__to[v]:
            if self.__depth[u] != -1:
                continue
            self.__parents[0][u] = v
            self.__depth[u] = self.__depth[v]+1
            self.__dist[u] = self.__dist[v]+d
            self.__dfs(u)

    def __doubling(self):
        for i in range(1, self.__logn):
            for v in range(self.__n):
                if self.__parents[i-1][v] == -1:
                    continue
                self.__parents[i][v] = \
                    self.__parents[i-1][self.__parents[i-1][v]]

    @property
    def depth(self):
        return self.__depth

    @property
    def dist(self):
        return self.__dist

    def get(self, u, v):
        dd = self.__depth[v] - self.__depth[u]
        if dd < 0:
            u, v = v, u
            dd *= -1
        for i in range(self.__logn):
            if dd & (2**y):
                v = self.__parents[i][v]
        if v == u: return v
        for i in range(self.__logn-1, -1, -1):
            pu = self.__parents[i][u]
            pv = self.__parents[i][v]
            if pu != pv: u, v = pu, pv
        return self.__parents[0][u]
  
n, q = map(int, input().split())
to = [list() for _ in range(n)]
for _ in range(n-1):
    a, b, c, d = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append((b, c, d))
    to[b].append((a, c, d))

G = LCA(to)

Query = [list() for _ in range(n)]
for i in range(q):
    #idx, color, mag, coef
    x, y, u, v = map(int, input().split())
    u -= 1
    v -= 1
    c = G.get(u, v)
    Query[u].append((i, x, y, 1))
    Query[v].append((i, x, y, 1))
    Query[c].append((i, x, y, -2))

ans = [0]*q
S = [[0, 0] for _ in range(n)]

def dfs(v, p=-1):
    for idx, color, mag, coef in Query[v]:
        x = G.dist[v]
        x -= S[color][1]
        x += mag*S[color][0]
        ans[idx] += x*coef
    for nv, color, d in to[v]:
        if nv == p: continue
        S[color][0] += 1
        S[color][1] += d
        dfs(nv, v)
        S[color][0] -= 1
        S[color][1] -= d
    return ans

print(*dfs(0), sep="\n")

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    INF = float('inf')

    N, Q = map(int, input().split())
    adjL = [[] for _ in range(N)]
    for _ in range(N-1):
        A, B, C, D = map(int, input().split())
        A, B, C = A-1, B-1, C-1
        adjL[A].append((B, C, D))
        adjL[B].append((A, C, D))
    querys = [tuple(map(int, input().split())) for _ in range(Q)]

    def dfs(vNow, vPar, depth):
        iVFirsts[vNow] = len(vs)
        vs.append(vNow)
        depths.append(depth)
        for v2, clr, dist in adjL[vNow]:
            if v2 == vPar: continue
            iVColorss[clr].append(len(numEs))
            numEs.append(1)
            sumDs.append(dist)

            dfs(v2, vNow, depth+1)

            vs.append(vNow)
            depths.append(depth)
            iVColorss[clr].append(len(numEs))
            numEs.append(-1)
            sumDs.append(-dist)

    vs = []
    iVFirsts = [-1] * N
    depths = []
    numEs = [0]
    sumDs = [0]
    iVColorss = [[0] for _ in range(N-1)]

    dfs(0, -1, 0)

    dists = [0] * N
    accD = 0
    for i, sumD in enumerate(sumDs):
        accD += sumD
        if iVFirsts[vs[i]] == i:
            dists[vs[i]] = accD

    for iVColors in iVColorss:
        for i in range(1, len(iVColors)):
            numEs[iVColors[i]] += numEs[iVColors[i-1]]
            sumDs[iVColors[i]] += sumDs[iVColors[i-1]]

    idEle = (INF, -1)
    def _binOpe(x, y):
        return x if x <= y else y  # min
    def makeSegTree(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [idEle] * (2*numPow2)
        return data, numPow2
    def setInit(As):
        for iST, A in enumerate(As, numPow2):
            data[iST] = A
        for iST in reversed(range(1, numPow2)):
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def getValue(iSt, iEn):
        L = iSt + numPow2
        R = iEn + numPow2
        ans = idEle
        while L < R:
            if L & 1:
                ans = _binOpe(ans, data[L])
                L += 1
            if R & 1:
                R -= 1
                ans = _binOpe(ans, data[R])
            L >>= 1
            R >>= 1
        return ans

    data, numPow2 = makeSegTree(len(depths))
    setInit([(depth, i) for i, depth in enumerate(depths)])

    def getLCA(x, y):
        L, R = iVFirsts[x], iVFirsts[y]
        minV, iMinV = getValue(L, R)
        return vs[iMinV]

    anss = []
    for clr, distNew, u, v in querys:
        u, v = u-1, v-1
        LCA = getLCA(u, v)

        clr -= 1
        ds = [dists[u], dists[v], dists[LCA]]
        for i, vv in enumerate([u, v, LCA]):
            iIV = bisect_right(iVColorss[clr], iVFirsts[vv]) - 1
            iV = iVColorss[clr][iIV]
            ds[i] += numEs[iV] * distNew - sumDs[iV]
        ans = ds[0] + ds[1] - 2*ds[2]
        anss.append(ans)

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


solve()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    INF = float('inf')

    N, Q = map(int, input().split())
    adjL = [[] for _ in range(N)]
    for _ in range(N-1):
        A, B, C, D = map(int, input().split())
        A, B, C = A-1, B-1, C-1
        adjL[A].append((B, C, D))
        adjL[B].append((A, C, D))
    querys = [tuple(map(int, input().split())) for _ in range(Q)]

    def dfs(vNow, vPar, depth):
        iVFirsts[vNow] = len(vs)
        vs.append(vNow)
        depths.append(depth)
        for v2, clr, dist in adjL[vNow]:
            if v2 == vPar: continue
            iVColorss[clr].append(len(numEs))
            numEs.append(1)
            sumDs.append(dist)

            dfs(v2, vNow, depth+1)

            vs.append(vNow)
            depths.append(depth)
            iVColorss[clr].append(len(numEs))
            numEs.append(-1)
            sumDs.append(-dist)

    vs = []
    iVFirsts = [-1] * N
    depths = []
    numEs = [0]
    sumDs = [0]
    iVColorss = [[0] for _ in range(N-1)]

    dfs(0, -1, 0)

    dists = [0] * N
    accD = 0
    for i, sumD in enumerate(sumDs):
        accD += sumD
        if iVFirsts[vs[i]] == i:
            dists[vs[i]] = accD

    for iVColors in iVColorss:
        for i in range(1, len(iVColors)):
            numEs[iVColors[i]] += numEs[iVColors[i-1]]
            sumDs[iVColors[i]] += sumDs[iVColors[i-1]]

    idEle = (INF, -1)
    def _binOpe(x, y):
        return x if x <= y else y  # min
    def makeSegTree(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [idEle] * (2*numPow2)
        return data, numPow2
    def setInit(As):
        for iST, A in enumerate(As, numPow2):
            data[iST] = A
        for iST in reversed(range(1, numPow2)):
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def getValue(iSt, iEn):
        L = iSt + numPow2
        R = iEn + numPow2
        ans = idEle
        while L < R:
            if L & 1:
                ans = _binOpe(ans, data[L])
                L += 1
            if R & 1:
                R -= 1
                ans = _binOpe(ans, data[R])
            L >>= 1
            R >>= 1
        return ans

    data, numPow2 = makeSegTree(len(depths))
    setInit([(depth, i) for i, depth in enumerate(depths)])

    def getLCA(x, y):
        L, R = iVFirsts[x], iVFirsts[y]
        minV, iMinV = getValue(L, R)
        return vs[iMinV]

    anss = []
    for clr, distNew, u, v in querys:
        u, v = u-1, v-1
        LCA = getLCA(u, v)

        clr -= 1
        ds = [dists[u], dists[v], dists[LCA]]
        for i, vv in enumerate([u, v, LCA]):
            iIV = bisect_right(iVColorss[clr], iVFirsts[vv]) - 1
            iV = iVColorss[clr][iIV]
            ds[i] += numEs[iV] * distNew - sumDs[iV]
        ans = ds[0] + ds[1] - ds[2]
        anss.append(ans)

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


solve()

Submission status: Wrong Answer

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)
        if p == stack[-1]:
            EulerTour.append((p, -1))    
            stack.pop()
            

#dfs(0)
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: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
readline = sys.stdin.readline
read = sys.stdin.read

N, Q = map(int, readline().split())
graph = [[] for _ in range(N + 1)]

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

xyuv = map(int, read().split())


def Euler_Tour(graph, start=1):
    v = len(graph)
    tour = []
    depth = [-1] * v
    first_appearance = [-1] * v
    color = [0] * (N + 1)  # 自身と親を結ぶ辺の色
    length = [0] * (N + 1)  # 自身と親を結ぶ辺の長さ

    def dfs(vertex, d):
        first_appearance[vertex] = len(tour)
        depth[vertex] = d
        tour.append(vertex)
        for (i, c, dist) in graph[vertex]:
            if first_appearance[i] == -1:
                color[i] = c
                length[i] = dist
                dfs(i, d + 1)
                tour.append(vertex)

    dfs(start, 0)

    return tour, depth, first_appearance, color, length


T, D, F, C, L = Euler_Tour(graph, 1)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 7)
read = sys.stdin.read

N, Q, *data = map(int, read().split())
graph = [[] for _ in range(N + 1)]
abcd = data[:4 * (N - 1)]

for a, b, c, d in zip(*[iter(abcd)] * 4):
    graph[a].append((b, c, d))
    graph[b].append((a, c, d))

xyuv = data[4 * (N - 1):]


def Euler_Tour(graph, start=1):
    v = len(graph)
    tour = []
    depth = [-1] * v
    first_appearance = [-1] * v
    color = [0] * (N + 1)  # 自身と親を結ぶ辺の色
    length = [0] * (N + 1)  # 自身と親を結ぶ辺の長さ

    def dfs(vertex, d):
        first_appearance[vertex] = len(tour)
        depth[vertex] = d
        tour.append(vertex)
        for (i, c, dist) in graph[vertex]:
            if first_appearance[i] == -1:
                color[i] = c
                length[i] = dist
                dfs(i, d + 1)
                tour.append(vertex)

    dfs(start, 0)

    return tour, depth, first_appearance, color, length


T, D, F, C, L = Euler_Tour(graph, 1)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 7)
readline = sys.stdin.readline
read = sys.stdin.read

N, Q = map(int, readline().split())
graph = [[] for _ in range(N + 1)]

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

xyuv = map(int, read().split())

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 7)
readline = sys.stdin.readline
read = sys.stdin.read

N, Q = map(int, readline().split())
graph = [[] for _ in range(N + 1)]

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

xyuv = map(int, read().split())


def Euler_Tour(graph, start=1):
    v = len(graph)
    tour = []
    depth = [-1] * v
    first_appearance = [-1] * v
    color = [0] * (N + 1)  # 自身と親を結ぶ辺の色
    length = [0] * (N + 1)  # 自身と親を結ぶ辺の長さ

    def dfs(vertex, d):
        first_appearance[vertex] = 1
        depth[vertex] = d
        tour.append(vertex)
        for (i, c, dist) in graph[vertex]:
            if first_appearance[i] == -1:
                color[i] = c
                length[i] = dist
                dfs(i, d + 1)
                tour.append(vertex)

    dfs(start, 0)

    return tour, depth, first_appearance, color, length


T, D, F, C, L = Euler_Tour(graph, 1)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 7)
readline = sys.stdin.readline
read = sys.stdin.read

N, Q = map(int, readline().split())
graph = [[] for _ in range(N + 1)]

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

xyuv = map(int, read().split())


def Euler_Tour(graph, start=1):
    v = len(graph)
    tour = []
    depth = [-1] * v
    first_appearance = [-1] * v
    color = [0] * (N + 1)  # 自身と親を結ぶ辺の色
    length = [0] * (N + 1)  # 自身と親を結ぶ辺の長さ

    def dfs(vertex, d):
        first_appearance[vertex] = len(tour)
        depth[vertex] = d
        tour.append(vertex)
        for (i, c, dist) in graph[vertex]:
            if first_appearance[i] == -1:
                color[i] = c
                length[i] = dist
                dfs(i, d + 1)
                tour.append(vertex)

    dfs(start, 0)

    return tour, depth, first_appearance, color, length


T, D, F, C, L = Euler_Tour(graph, 1)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
import numpy as np
 
N,Q = map(int,readline().split())
data = np.array(read().split(),np.int64)
 
ABCD = data[:4*N-4].reshape(-1,4).tolist()
 
graph = [[] for _ in range(N+1)]
for a,b,c,d in ABCD:
    graph[a].append((b,c,d))
    graph[b].append((a,c,d))
 
color = [0] * (N+1) # 自身と親を結ぶ辺の色
length = [0] * (N+1) # 自身と親を結ぶ辺の長さ
 
def EulerTour(graph,start=1):
    """
    1-indexed graph
    graphを破壊しているので場合によっては注意
    """
    V = len(graph)
    par = [0] * V
    depth = [0] * V; depth[start] = 0
    tour = [start]; st = [start]
    while st:
        x = st[-1]
        if not graph[x]:
            st.pop()
            tour.append(par[x])
            continue
        y,c,d = graph[x].pop()
        if y == par[x]:
            continue
        par[y] = x
        color[y] = c
        length[y] = d
        depth[y] = depth[x] + 1
        st.append(y)
        tour.append(y)
    return tour,depth
 
tour,depth = EulerTour(graph)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
readline = sys.stdin.readline
read = sys.stdin.read

N, Q = map(int, readline().split())
graph = [[] for _ in range(N + 1)]

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

xyuv = map(int, read().split())


def Euler_Tour(graph, start=1):
    v = len(graph)
    tour = []
    depth = [-1] * v
    first_appearance = [-1] * v

    def dfs(vertex, d):
        first_appearance[vertex] = len(tour)
        depth[vertex] = d
        tour.append(vertex)
        for (i, color, distance) in graph[vertex]:
            if first_appearance[i] == -1:
                dfs(i, d + 1)
                tour.append(vertex)

    dfs(start, 0)

    return tour, depth, first_appearance


T, D, F = Euler_Tour(graph, 1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
readline = sys.stdin.readline
read = sys.stdin.read

N, Q = map(int, readline().split())
graph = [[] for _ in range(N + 1)]

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

xyuv = map(int, read().split())


def Euler_Tour(graph, start=1):
    v = len(graph)
    tour = []
    depth = [-1] * v
    first_appearance = [-1] * v

    def dfs(vertex, d):
        first_appearance[vertex] = len(tour)
        depth[vertex] = d
        tour.append(vertex)
        for (i, color, distance) in graph[vertex]:
            if first_appearance[i] == -1:
                dfs(i, d + 1)
                tour.append(vertex)

    dfs(start, 0)

    return tour, depth, first_appearance


T, D, F = Euler_Tour(graph, 1)
INF = (N, None)
m = 2 * N
m0 = 2 ** (m - 1).bit_length()
data = [INF] * (2 * m0)
for i, v in enumerate(T):
    data[m0 - 1 + i] = (D[v], i)
for i in range(m0 - 2, -1, -1):
    data[i] = min(data[2 * i + 1], data[2 * i + 2])


def _query(a, b):
    yield INF
    a += m0
    b += m0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b - 1]
        if a & 1:
            yield data[a - 1]
            a += 1
        a >>= 1
        b >>= 1


def query(u, v):
    fu = F[u]
    fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return T[min(_query(fu, fv + 1))[1]]


for x, y, u, v in zip(*[xyuv] * 4):
    print(query(u, v))

Submission status: Wrong Answer

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


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

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

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

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

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


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

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

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

    def euler_tour_dfs(self, v, v_par, depth):
        self.first_idx[v] = len(self.euler_tour)
        self.euler_tour.append(v)
        self.euler_depth.append(depth)
        for v_next, c, d in self.graph[v]:
            if v_next == v_par:
                continue
            self.euler_tour_dfs(v_next, v, depth + d)
            self.euler_tour.append(v)
            self.euler_depth.append(depth)

    def depth(self, v):
        return self.euler_depth[self.first_idx[v]]

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

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


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

tree = Tree(n, graph, 0)

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

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

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


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

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


dfs(0, -1, 0)

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

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

Submission status: Wrong Answer

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

import numpy as np

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

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

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

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

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

tour,depth = EulerTour(graph)

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

def euler_tour(x, tour_v, tour_d, depth = 0, parent=None):
    tour_v.append(x)
    tour_d.append(depth)
    for y, c, d in graph[x]:
        if y == parent:
            continue
        euler_tour(y, tour_v, tour_d, depth + 1, parent = x)
        tour_v.append(x)
        tour_d.append(depth)

tour_v = []
tour_d = []
euler_tour(1, tour_v, tour_d)
tour_d_arr = np.array(tour_d)
v_to_i = {v:i for i,v in enumerate(tour_v)}
v_to_d = dict(zip(tour_v, tour_d))

# sparse table
# 各インデックスから、2^i 項目分見て、一番depthの小さいインデックス
L = len(tour_v)
U = L.bit_length()
sp = [np.arange(L)]
for i in range(1,U):
    prev = sp[-1]
    width = 1 << (i-1)
    n1 = prev[:-width]
    n2 = prev[width:]
    sp.append(np.where(tour_d_arr[n1] < tour_d_arr[n2], n1, n2))

def LCA(x,y):
    ix = v_to_i[x]
    iy = v_to_i[y]
    if ix > iy:
        ix,iy = iy,ix
    items = iy - ix + 1
    L = items.bit_length() - 1
    n1 = sp[L][ix]
    n2 = sp[L][iy - (1 << L) + 1]
    n = n1 if tour_d[n1] < tour_d[n2] else n2
    return tour_v[n]

tasks = [[] for _ in range(N+1)]
for i,(x,y,u,v) in enumerate(query):
    tasks[u].append((i,x,y,1))
    tasks[v].append((i,x,y,1))
    tasks[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 y,c,d in graph[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)))