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: Runtime Error

Solution code:
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.__dist[u]
        if dd < 0:
            u, v = v, u
            dd *= -1
        for i in range(self.__logn):
            if dd & (2**i):
                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: Runtime Error

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 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(*[iter(xyuv)] * 4):
    print(query(u, v))

Submission status: Runtime Error

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 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(*[iter(xyuv)] * 2):
    print(query(u, v))

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect
from math import log2
sys.setrecursionlimit(10**6)

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 = maxlog = int(log2(n-1))+1
		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_key = [[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_key[co].append(self.cnt)
			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_key[co].append(self.cnt)
			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]:
			return self.get_lca(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: Runtime Error

Solution code:
# 参考　https://tjkendev.github.io/procon-library/python/graph/lca-segment-tree.html

# N: 頂点数
# G[v]: 頂点vの子頂点 (親頂点は含まない)

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

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

# Euler Tour の構築
S = []
F = [0] * N
depth = [0] * N
Dist = [0] * N
Weight = [[] for _ in range(N)]
weight = [0] * (N - 1)
Number = [[] for _ in range(N)]
number = [0] * (N - 1)

def dfs(v=0, pv=-1, d=0, dist=0):
    F[v] = len(S)
    depth[v] = d
    S.append(v)
    Dist[v] = dist
    Weight[v] = weight[:]
    Number[v] = number[:]
    for nv, c, w in G[v]:
        if nv == pv:
            continue
        weight[c] += w
        number[c] += 1
        dfs(nv, v, d + 1, dist + w)
        weight[c] -= w
        number[c] -= 1
        S.append(v)

dfs()

# 存在しない範囲は深さが他よりも大きくなるようにする
INF = (N, None)

# LCAを計算するクエリの前計算
M = 2*N
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])

# LCAの計算 (generatorで最小値を求める)
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

# LCAの計算 (外から呼び出す関数)
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv + 1))[1]]

for _ in range(Q):
    x, y, u, v = map(int, input().split())
    x -= 1; u -= 1; v -= 1
    w = query(u, v)
    du = Dist[u] - Weight[u][x] + y * Number[u][x]
    dv = Dist[v] - Weight[v][x] + y * Number[v][x]
    dw = Dist[w] - Weight[w][x] + y * Number[w][x]
    ans = du + dv - 2 * dw
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
inf = float('inf')

def main():

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

    ID = [-1] * N
    VS = []
    Depth = []
    Dist = [0] * N
    Weight = [[] for _ in range(N)]
    Number = [[] for _ in range(N)]

    weight = [0] * (N - 1)
    number = [0] * (N - 1)

    VSappend = VS.append
    Depthappend = Depth.append

    def dfs(v=0, pv=-1, depth=0, dist=0):
        ID[v] = len(VS)
        VSappend(v)
        Depthappend(depth)
        Dist[v] = dist
        Weight[v] = weight[:]
        Number[v] = number[:]
        for nv, c, w in to[v]:
            if nv == pv:
                continue
            weight[c] += w
            number[c] += 1
            dfs(nv, v, depth + 1, dist + w)
            weight[c] -= w
            number[c] -= 1
            VSappend(v)
            Depthappend(depth)

    dfs()

    M = 1
    while M < len(Depth):
        M <<= 1
    Data = [(inf, -1) for _ in range(2 * M)]

    def update(k, x):
        k += M
        Data[k] = x
        while k > 1:
            k >>= 1
            Data[k] = min(Data[2*k], Data[2*k+1])

    def query(l, r):
        l += M
        r += M
        res = (inf, -1)
        while l < r:
            if l & 1:
                res = min(res, Data[l])
                l += 1
            if r & 1:
                r -= 1
                res = min(res, Data[r])
            l >>= 1; r >>= 1
        return res

    for i, depth in enumerate(Depth):
        update(i, (depth, i))

    def LCA(u, v):
        l = ID[u]; r = ID[v]
        if not (l < r):
            l, r = r, l
        _, index = query(l, r + 1)
        w = VS[index]
        return w

    for _ in range(Q):
        x, y, u, v = map(int, input().split())
        x -= 1; u -= 1; v -= 1
        w = LCA(u, v)
        du = Dist[u] - Weight[u][x] + y * Number[u][x]
        dv = Dist[v] - Weight[v][x] + y * Number[v][x]
        dw = Dist[w] - Weight[w][x] + y * Number[w][x]
        ans = du + dv - 2 * dw
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

class Accumulate:
    def __init__(self,lst): #g: graph 
        from itertools import accumulate
        self.acc = list(accumulate(lst))

    def query(self,u,v): #[u,v]の和を返す（閉区間）
        return self.acc[v] - self.acc[u-1] if u else self.acc[v]

"""
オイラーツアー（辺属性）　http://beet-aizu.hatenablog.com/entry/2019/07/08/174727
部分木やパスに関するクエリを処理

dfs で踏む頂点を順番に並べる
ds[v] = v を行きがけに踏むのはds[v]   歩目
us[v] = v の帰りがけに踏むのはus[v]-1 歩目
辺st （ただしs が親）の情報は dist[t], color[t], idx[t] などに保存
（つまり辺の情報のツアーは info[tour[1]], info[tour[2]], ... と並ぶ ）
v の部分木に属する頂点は [ds[v],us[v]-1] までの頂点
v の部分木に属する辺は [ds[v],us[v]-2] までの辺（REに注意）
パス pc は[ds[p],ds[c]-1] までの辺に対応
"""

class Euler_tour_edge:
    """
    parent: ダブリングテーブル
    depth: 元の深さ
    """
    def __init__(self,g,root): #g: graph 

        def dfs(root):
            parent = self.parent[0]
            q = [root]
            cnt = 0
            col = [-1]*N; wt = [-1]*N #辺の情報
            while q:
                v = q.pop()
                if v >= 0: #行きがけ
                    q.append(-v-1)
                    self.ds[v] = cnt; self.tour[cnt] = v; cnt += 1; 
                    for c,c_col,c_wt in g[v]:
                        if c != parent[v]:
                            parent[c] = v
                            self.depth[c] = self.depth[v] + 1
                            q.append(c)
                            # c を子とする唯一の辺の情報を保存
                            col[c] = c_col; wt[c] = c_wt
                else: #帰りがけ
                    self.tour[cnt] = parent[-v-1]
                    self.us[-v-1] = cnt; cnt += 1
            self.tour.pop() #
            return col, wt
            
        def doubling_make_table(N,logN,Table):
            for i in range(1,logN):
                for j, Tiij in enumerate(Table[i-1]):
                    if Tiij != -1:
                        Table[i][j] = Table[i-1][Tiij]

        N = len(g)
        self.logN = len(bin(N))-2
        self.parent = [[-1]*N for _ in range(self.logN)]
        self.depth = [0]*(N) #ノードの深さ
        self.ds = [0]*(N)
        self.us = [0]*(N)
        self.tour = [-1]*(2*N) #踏む頂点の列
        self.col, self.wt = dfs(root) #問題に必要な情報をここで計算
        doubling_make_table(N, self.logN, self.parent) #ダブリングのテープル構築
        
        #辺情報を列の形で管理        
        self.data_col = [0]*(2*N-2)
        self.data_wt = [0]*(2*N-2)
        for i in range(N):
            if i != root:
                di, ui = self.ds[i], self.us[i]
                # 行きがけで i に向かう辺
                self.data_wt[di-1] = self.wt[i]
                self.data_col[di-1] = self.col[i]
                # 帰りがけで i から出る辺
                self.data_wt[ui-1] = -self.wt[i]
                self.data_col[ui-1] = self.col[i]
        #print(self.data_col)        
        #print(self.data_wt)        

        #print(self.tour, self.col, self.wt)
        #print(self.ds,self.us)

        
        #以下、data を用いてデータ構造を構成
        #print(data)
        self.wt_acc = Accumulate(self.data_wt)
        self.color_id = [[] for _ in range(n)]
        self.color_num = [[0] for _ in range(n)]
        self.color_acc = [[0] for _ in range(n)]
        for i,(c,w) in enumerate(zip(self.data_col,self.data_wt)):
            self.color_id[c].append(i)
            self.color_num[c].append(self.color_num[c][-1] + (1 if w>0 else -1))
            self.color_acc[c].append(self.color_acc[c][-1]+w)
        
        #print(self.wt_acc.acc)
        #print(self.ds,self.us)
        
            
    def get_path_wt(self,col,wt,u,v):
        p = self.getLCA(u,v)
        #print("p",p,self.ds[p],"u",u,self.ds[u],"v",v,self.ds[v])
        res = self.wt_acc.query(self.ds[p],self.ds[u]-1) + self.wt_acc.query(self.ds[p],self.ds[v]-1)
        # res = u-v 間のパスの重みが求まった
        cid  = self.color_id[col] 
        cnum = self.color_num[col]
        cacc = self.color_acc[col]
        if cid:
            i = bisect_left(cid,self.ds[u])
            res += (-cacc[i] + wt*cnum[i])
            i = bisect_left(cid,self.ds[v])
            res += (-cacc[i] + wt*cnum[i])
            i = bisect_left(cid,self.ds[p])
            res -= 2*(-cacc[i] + wt*cnum[i])
        return res
        

    def getLCA(self,u,v): #u,vのLCAを返す
        if self.depth[u] > self.depth[v]: u,v = v,u #vが深い
        dd = self.depth[v] - self.depth[u]
        for k in range(self.logN-1,-1,-1):
            if (dd >> k) & 1: v = self.parent[k][v]
        if u == v: return u;
        for k in range(self.logN-1,-1,-1):
            if self.parent[k][u] != self.parent[k][v]:
                u,v = self.parent[k][u], self.parent[k][v]
        return self.parent[0][u];

    def getdepth(self,u): #uの深さを返す
        return self.depth[u]



#####################################


import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines
 
#n = int(input())
#ab = [[int(i) for i in readline().split()] for _ in range(n)]
 
n,m = [int(i) for i in readline().split()]
abcd = map(int,read().split())
 
g = [[] for _ in range(n)]
 
for i in range(n-1):
    a,b,c,d = next(abcd),next(abcd),next(abcd),next(abcd)
    a -= 1; b -= 1
    #print(a,b,c,d)
    g[a].append([b,c,d])
    g[b].append([a,c,d])
 
 
#print(g)
E = Euler_tour_edge(g,0)
 
ans = [0]*m
 
from bisect import bisect_left
 
for i in range(m):
    c,w,u,v = next(abcd),next(abcd),next(abcd),next(abcd)
    u -= 1; v -= 1
    #print(E.get_path_wt(c,w,u,v))
    ans[i] = E.get_path_wt(c,w,u,v)
 
print("\n".join(map(str,ans)))

"""
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

#n = int(input())
#ab = [[int(i) for i in readline().split()] for _ in range(n)]

n,m = [int(i) for i in readline().split()]
abcd = map(int,read().split())

g = [[] for _ in range(n)]

for i in range(n-1):
    a,b,c,d = next(abcd),next(abcd),next(abcd),next(abcd)
    a -= 1; b -= 1
    #print(a,b,c,d)
    g[a].append((b,c,d))
    g[b].append((a,c,d))


#print(g)
E = Euler_tour_edge(g,0)

ans = [0]*m

acc = 0
acc_color = [0]*n

qlist = [[] for _ in range(n)] # qlist[i]: 頂点 i 上のクエリ (q_num, col, 倍率)
ans = [0]*m #

for i in range(m):
    c,w,u,v = next(abcd),next(abcd),next(abcd),next(abcd)
    u -= 1; v -= 1
    qlist[E.ds[u]].qppend((i,c,1))
    qlist[E.ds[v]].qppend((i,c,1))
    qlist[E.ds[p]].qppend((i,c,-2))

for i,y in E.tour[1:]:
    i    


ans[i] = E.get_path_wt(c,w,u,v)
"""


assert n != 5 or m != 3

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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

# query先読みで、頂点ごとに、どの色の長さを求めるのか。
n, q = LI()
edge_dict = [{} for _ in range(n)]
for u, v, c, d in LIR(n - 1):
    edge_dict[u - 1][v - 1] = (c, d)
    edge_dict[v - 1][u - 1] = (c, d)

lca = LCA(n, edge_dict)
query = [[] for _ in range(n)]
for q_idx, (x, y, u, v) in enumerate(LIR(q)):
    query[u - 1] += [(q_idx, x, y, 1)]
    query[v - 1] += [(q_idx, x, y, 1)]
    query[lca.lca(u - 1, v - 1)] += [(q_idx, x, y, 0)]

def euler_tour(G, root=0):
    n = len(G)
    euler = []
    depth = [-1] * n
    depth[root] = 0
    dq = deque([root])
    dq2 = deque()
    visited = [0] * n
    while dq:
        u = dq.pop()
        euler += [(depth[u], u)]
        if visited[u]:
            continue
        for v in G[u]:
            if visited[v]:
                dq += [v]
            # [親頂点、子頂点、子頂点、。。。]と入れていく.その後連結
            else:
                depth[v] = depth[u] + 1
                dq += [v]
        dq.extend(dq2)
        dq2 = deque()
        visited[u] = 1
    return euler

dist = 0
color_len = [0] * n
color_cnt = [0] * n
ans = [0] * q
euler = euler_tour(edge_dict)
for i in range(1, len(euler)):
    dep = euler[i][0]
    c, d = edge_dict[euler[i - 1][1]][euler[i][1]]
    if euler[i - 1][0] < euler[i][0]:
        dist += d
        color_len[c] += d
        color_cnt[c] += 1
        for q_idx, x, y, flag in query[euler[i][1]]:
            if flag:
                ans[q_idx] += dist - color_len[x] + color_cnt[x] * y
            else:
                ans[q_idx] -= (dist - color_len[x] + color_cnt[x] * y) * 2
    else:
        dist -= d
        color_len[c] -= d
        color_cnt[c] -= 1


print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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

# query先読みで、頂点ごとに、どの色の長さを求めるのか。
n, q = LI()
edge_dict = [{} for _ in range(n)]
for u, v, c, d in LIR(n - 1):
    edge_dict[u - 1][v - 1] = (c, d)
    edge_dict[v - 1][u - 1] = (c, d)

lca = LCA(n, edge_dict)
query = [[] for _ in range(n)]
for q_idx, (x, y, u, v) in enumerate(LIR(q)):
    query[u - 1] += [(q_idx, x, y, 1)]
    query[v - 1] += [(q_idx, x, y, 1)]
    query[lca.lca(u - 1, v - 1)] += [(q_idx, x, y, 0)]

def Eulertour(G, root=0):
    n = len(G)
    euler = []
    depth = [-1] * n
    depth[root] = 0
    dq = deque([root])
    dq2 = deque()
    visited = [0] * n
    while dq:
        u = dq.pop()
        euler += [(depth[u], u)]
        if visited[u]:
            continue
        for v in G[u]:
            if visited[v]:
                dq += [v]
            # [親頂点、子頂点、子頂点、。。。]と入れていく.その後連結
            else:
                depth[v] = depth[u] + 1
                dq += [v]
        dq.extend(dq2)
        dq2 = deque()
        visited[u] = 1
    return euler

dist = 0
color_len = [0] * n
color_cnt = [0] * n
ans = [0] * q
euler = Eulertour(edge_dict)
for i in range(1, len(euler)):
    dep = euler[i][0]
    c, d = edge_dict[euler[i - 1][1]][euler[i][1]]
    if euler[i - 1][0] < euler[i][0]:
        dist += d
        color_len[c] += d
        color_cnt[c] += 1
        for q_idx, x, y, flag in query[euler[i][1]]:
            if flag:
                ans[q_idx] += dist - color_len[x] + color_cnt[x] * y
            else:
                ans[q_idx] -= (dist - color_len[x] + color_cnt[x] * y) * 2
    else:
        dist -= d
        color_len[c] -= d
        color_cnt[c] -= 1


print(*ans, sep='\n')