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

Solution code:
import sys
from bisect import bisect
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.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_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: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect
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 = 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_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: Time Limit Exceeded

Solution code:
def main():

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

    inf = float('inf')

    # 一点更新　区間取得　1-indexed
    class SegmentTree:
        def __init__(self, n):
            tmp = 1
            while tmp < n:
                tmp <<= 1
            # self.N : 完全二分木の葉の数(N以上の最小の2べき)
            self.N = tmp
            # 2*self.N - 1 : 完全二分木のノード数
            # 1-indexedで管理するので１つ余分に設ける
            self.Data = [(inf, -1) for _ in range(2*self.N)]

        # k (0-indexed)
        def update(self, k, x):
            #　インデックスを補正
            k += self.N
            # 指定ノードを更新
            self.Data[k] = x
            # kを含む区間ノードを更新していく
            while k > 1:
                k >>= 1
                self.Data[k] = min([self.Data[2*k], self.Data[2*k+1]])

        # [l, r) (0-indexed)
        def query(self, l, r):
            #　インデックスを補正
            l += self.N
            r += self.N
            # 返り値を初期化
            res = (inf, -1)
            while l < r:
                # 右側なら右側を更新 右上に行く
                # 左側なら更新しない　上に行く
                if l & 1:
                    res = min([res, self. Data[l]])
                    l += 1
                # 右側なら左側を更新　上に行く
                # 左側なら更新しない 上に行く
                if r & 1:
                    r -= 1
                    res = min([res, self.Data[r]])
                l >>= 1; r >>= 1
            return res

    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))

    Weight = [[0] * (N - 1) for _ in range(N)]
    Number = [[0] * (N - 1) for _ in range(N)]
    Dist = [0] * N
    ID = [-1] * N
    vs = []
    Depth = []
    weight = [0] * (N - 1)
    number = [0] * (N - 1)
    vsappend = vs.append
    Depthappend = Depth.append

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

    dfs()
    ST = SegmentTree(len(Depth))
    for i, depth in enumerate(Depth):
        ST.update(i, (depth, i))

    def LCA(u, v):
        l = ID[u]; r = ID[v]
        if not (l < r):
            l, r = r, l
        _, index = ST.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: Time Limit Exceeded

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

inf = float('inf')

# 一点更新　区間取得　1-indexed
class SegmentTree:
    def __init__(self, n):
        tmp = 1
        while tmp < n:
            tmp <<= 1
        # self.N : 完全二分木の葉の数(N以上の最小の2べき)
        self.N = tmp
        # 2*self.N - 1 : 完全二分木のノード数
        # 1-indexedで管理するので１つ余分に設ける
        self.Data = [(inf, -1) for _ in range(2*self.N)]

    # k (0-indexed)
    def update(self, k, x):
        #　インデックスを補正
        k += self.N
        # 指定ノードを更新
        self.Data[k] = x
        # kを含む区間ノードを更新していく
        while k > 1:
            k >>= 1
            self.Data[k] = min([self.Data[2*k], self.Data[2*k+1]])

    # [l, r) (0-indexed)
    def query(self, l, r):
        #　インデックスを補正
        l += self.N
        r += self.N
        # 返り値を初期化
        res = (inf, -1)
        while l < r:
            # 右側なら右側を更新 右上に行く
            # 左側なら更新しない　上に行く
            if l & 1:
                res = min([res, self. Data[l]])
                l += 1
            # 右側なら左側を更新　上に行く
            # 左側なら更新しない 上に行く
            if r & 1:
                r -= 1
                res = min([res, self.Data[r]])
            l >>= 1; r >>= 1
        return res

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))

Weight = [[0] * (N - 1) for _ in range(N)]
Number = [[0] * (N - 1) for _ in range(N)]
Dist = [0] * N
ID = [-1] * N
vs = []
Depth = []
weight = [0] * (N - 1)
number = [0] * (N - 1)
def dfs(v=0, pv=-1, dist=0, depth=0):
    Weight[v] = weight[:]
    Number[v] = number[:]
    Dist[v] = dist
    ID[v] = len(vs)
    vs.append(v)
    Depth.append(depth)
    for nv, c, w in to[v]:
        if nv == pv:
            continue
        weight[c] += w
        number[c] += 1
        dfs(nv, v, dist + w, depth + 1)
        weight[c] -= w
        number[c] -= 1
        vs.append(v)
        Depth.append(depth)

dfs()
ST = SegmentTree(len(Depth))
for i, depth in enumerate(Depth):
    ST.update(i, (depth, i))

def LCA(u, v):
    l = min(ID[u], ID[v])
    r = max(ID[u], ID[v]) + 1
    _, index = ST.query(l, r)
    w = vs[index]
    return w

ans_list = []

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
    ans_list.append(ans)

print(*ans_list, sep="\n")

Submission status: Time Limit Exceeded

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


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

        self.logn = (self.n - 1).bit_length()
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.depth = [0] * self.n
        self.dist = [0] * self.n

        self.init()

    def init(self):
        self.dfs(self.v_root, -1, 0, 0)
        # doubling
        for k in range(self.logn - 1):
            for v in range(self.n):
                if self.parent[k][v] != -1:
                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]

    def dfs(self, v, v_par, depth, dist):
        self.parent[0][v] = v_par
        self.depth[v] = depth
        self.dist[v] = dist
        for v_next, c, d in self.graph[v]:
            if v_next == v_par:
                continue
            self.dfs(v_next, v, depth + 1, dist + d)

    def lca(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u

        # go to parents of v until same depth as u
        diff = self.depth[v] - self.depth[u]
        for k in range(diff.bit_length()):
            if diff & (1 << k):
                v = self.parent[k][v]
        if u == v:
            return u
        # binary search
        # for k in reversed(range(self.logn)):
        for k in range(self.depth[u].bit_length() - 1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]


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))

v_root = n // 2
tree = Tree(n, graph, v_root)

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(v_root, -1, 0)

for x, y, u, v, lca in query:
    depth_u = tree.dist[u]
    depth_u += -d_color_memo[(u, x)] + y * n_color_memo[(u, x)]
    depth_v = tree.dist[v]
    depth_v += -d_color_memo[(v, x)] + y * n_color_memo[(v, x)]
    depth_lca = tree.dist[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: Time Limit Exceeded

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


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

        self.logn = (self.n - 1).bit_length()
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.depth = [0] * self.n
        self.dist = [0] * self.n

        self.init()

    def init(self):
        self.dfs(self.v_root, -1, 0, 0)
        # doubling
        for k in range(self.logn - 1):
            for v in range(self.n):
                if self.parent[k][v] != -1:
                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]

    def dfs(self, v, v_par, depth, dist):
        self.parent[0][v] = v_par
        self.depth[v] = depth
        self.dist[v] = dist
        for v_next, c, d in self.graph[v]:
            if v_next == v_par:
                continue
            self.dfs(v_next, v, depth + 1, dist + d)

    def lca(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u

        # go to parents of v until same depth as u
        diff = self.depth[v] - self.depth[u]
        for k in range(diff.bit_length()):
            if diff & (1 << k):
                v = self.parent[k][v]
        if u == v:
            return u
        # binary search
        # for k in reversed(range(self.logn)):
        for k in range(self.depth[u].bit_length() - 1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]


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))

v_root = 0
tree = Tree(n, graph, v_root)

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(v_root, -1, 0)

for x, y, u, v, lca in query:
    depth_u = tree.dist[u]
    depth_u += -d_color_memo[(u, x)] + y * n_color_memo[(u, x)]
    depth_v = tree.dist[v]
    depth_v += -d_color_memo[(v, x)] + y * n_color_memo[(v, x)]
    depth_lca = tree.dist[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: Time Limit Exceeded

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


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

        self.logn = (self.n - 1).bit_length()
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.depth = [0] * self.n
        self.dist = [0] * self.n

        self.init()

    def init(self):
        self.dfs(self.v_root, -1, 0, 0)
        # doubling
        for k in range(self.logn - 1):
            for v in range(self.n):
                if self.parent[k][v] != -1:
                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]

    def dfs(self, v, v_par, depth, dist):
        self.parent[0][v] = v_par
        self.depth[v] = depth
        self.dist[v] = dist
        for v_next, c, d in self.graph[v]:
            if v_next == v_par:
                continue
            self.dfs(v_next, v, depth + 1, dist + d)

    def lca(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u

        # go to parents of v until same depth as u
        diff = self.depth[v] - self.depth[u]
        for k in range(self.logn):
            if diff == 0:
                break
            if diff & (1 << k):
                v = self.parent[k][v]
                diff -= (1 << k)
        if u == v:
            return u
        # binary search
        # for k in reversed(range(self.logn)):
        for k in range((self.depth[u] - 1).bit_length() - 1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]


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))

v_root = 0
tree = Tree(n, graph, v_root)

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(v_root, -1, 0)

for x, y, u, v, lca in query:
    depth_u = tree.dist[u]
    depth_u += -d_color_memo[(u, x)] + y * n_color_memo[(u, x)]
    depth_v = tree.dist[v]
    depth_v += -d_color_memo[(v, x)] + y * n_color_memo[(v, x)]
    depth_lca = tree.dist[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: Time Limit Exceeded

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


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

        self.logn = (self.n - 1).bit_length()
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.depth = [0] * self.n
        self.dist = [0] * self.n

        self.init()

    def init(self):
        self.dfs(self.v_root, -1, 0, 0)
        # doubling
        for k in range(self.logn - 1):
            for v in range(self.n):
                if self.parent[k][v] != -1:
                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]

    def dfs(self, v, v_par, depth, dist):
        self.parent[0][v] = v_par
        self.depth[v] = depth
        self.dist[v] = dist
        for v_next, c, d in self.graph[v]:
            if v_next == v_par:
                continue
            self.dfs(v_next, v, depth + 1, dist + d)

    def lca(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u

        # go to parents of v until same depth as u
        diff = self.depth[v] - self.depth[u]
        for k in range(self.logn):
            if diff == 0:
                break
            if diff & (1 << k):
                v = self.parent[k][v]
                diff -= (1 << k)
        if u == v:
            return u
        # binary search
        # for k in reversed(range(self.logn)):
        for k in range(self.logn - 1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]


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))

v_root = 0
tree = Tree(n, graph, v_root)

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(v_root, -1, 0)

for x, y, u, v, lca in query:
    depth_u = tree.dist[u]
    depth_u += -d_color_memo[(u, x)] + y * n_color_memo[(u, x)]
    depth_v = tree.dist[v]
    depth_v += -d_color_memo[(v, x)] + y * n_color_memo[(v, x)]
    depth_lca = tree.dist[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: Time Limit Exceeded

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


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

        self.logn = (self.n - 1).bit_length()
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.depth = [0] * self.n
        self.dist = [0] * self.n

        self.init()

    def init(self):
        self.dfs(self.v_root, -1, 0, 0)
        # doubling
        for k in range(self.logn - 1):
            for v in range(self.n):
                if self.parent[k][v] != -1:
                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]

    def dfs(self, v, v_par, depth, dist):
        self.parent[0][v] = v_par
        self.depth[v] = depth
        self.dist[v] = dist
        for v_next, c, d in self.graph[v]:
            if v_next == v_par:
                continue
            self.dfs(v_next, v, depth + 1, dist + d)

    def lca(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u

        # go to parents of v until same depth as u
        diff = self.depth[v] - self.depth[u]
        for k in range(self.logn):
            if diff & (1 << k):
                v = self.parent[k][v]
        if u == v:
            return u
        # binary search
        # for k in reversed(range(self.logn)):
        for k in range(self.logn - 1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]


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))

v_root = n // 2 - 1
tree = Tree(n, graph, v_root)

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(v_root, -1, 0)

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

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