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
import numpy as np
i4 = np.int32


def solve(p, b, c, d, xyuv, ans, nodes, prevs, distances):
    def solve_loop(x, y, u, v):
        n = 0
        prev = -1
        distance = 0
        cur = u
        while n >= 0:
            for edge in range(p[cur], p[cur + 1]):
                if b[edge] != prev:
                    nodes[n] = b[edge]
                    prevs[n] = cur
                    distances[n] = distance + (y if c[edge] == x else d[edge])
                    if nodes[n] == v:
                        return distances[n]
                    n += 1
            n += -1
            distance = distances[n]
            prev = prevs[n]
            cur = nodes[n]

    for i in range(xyuv.shape[0]):
        ans[i] = solve_loop(xyuv[i, 0], xyuv[i, 1], xyuv[i, 2] - 1, xyuv[i, 3] - 1)


def make_pointer(a, p):
    c = -1
    for i in range(a.shape[0]):
        if a[i] != c:
            c = a[i]
            p[c] = i


def main():
    pin = np.fromstring(sys.stdin.buffer.read(), dtype=i4, sep=' ')
    N = pin[0]
    Q = pin[1]
    abcd = pin[2:4*(N-1)+2].reshape(N-1, 4)
    xyuv = pin[4 * (N - 1) + 2:].reshape(Q, 4)
    abcd[:,:2] = abcd[:,:2] - 1
    abcd = np.vstack((abcd, abcd[:,[1, 0, 2, 3]])).T
    abcd = abcd[:, np.argsort(abcd[0])]
    p = np.empty(N + 1, dtype=i4)
    p[N] = 2*N - 2
    make_pointer(abcd[0], p)
    nodes = np.empty(N, dtype=i4)
    prevs = np.empty(N, dtype=i4)
    distances = np.empty(N, dtype=i4)
    ans = np.zeros(Q, dtype=i4)
    solve(p, abcd[1], abcd[2], abcd[3], xyuv, ans, nodes, prevs, distances)
    for c in ans:
        print(c)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict
import copy
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))

ki = [dict() for i in range(N)]
for node in ki:
    node["edge"] = []
    node["num"] = defaultdict(int)
    node["iro_kyori"] = defaultdict(int)
for i in range(N-1):
    a, b, c, d = list(map(int, input().split()))
    ki[a - 1]["edge"].append([b - 1, c, d])
    ki[b - 1]["edge"].append([a - 1, c, d])

ki[0]["kyori"] = 0
ki[0]["oya"] = [-1, -1]
hukasa = []
for edge in ki[0]["edge"]:
    hukasa.append(edge[0])
    ki[edge[0]]["oya"] = [0, edge[1]]
    ki[edge[0]]["kyori"] = ki[0]["kyori"] + edge[2]
    ki[edge[0]]["num"][edge[1]] += 1
    ki[edge[0]]["iro_kyori"][edge[1]] += edge[2]

while len(hukasa) > 0:
    node = hukasa.pop()
    for edge in ki[node]["edge"]:
        if edge[0] != ki[node]["oya"][0]:
            hukasa.append(edge[0])
            ki[edge[0]]["num"] = copy.deepcopy(ki[node]["num"])
            ki[edge[0]]["iro_kyori"] = copy.deepcopy(ki[node]["iro_kyori"])
            ki[edge[0]]["oya"] = [node, edge[1]]
            ki[edge[0]]["num"][edge[1]] += 1
            ki[edge[0]]["kyori"] = ki[node]["kyori"] + edge[2]
            ki[edge[0]]["iro_kyori"][edge[1]] += edge[2]


for q in range(Q):
    x, y, u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    u_start = u
    v_start = v
    diff = 0
    while u != v:
        if ki[u]["kyori"] < ki[v]["kyori"]:
            node = v
            v = ki[node]["oya"][0]
        else:
            node = u
            u = ki[node]["oya"][0]
    sum = ki[u_start]["kyori"] + ki[v_start]["kyori"] - 2 * ki[u]["kyori"]
    sum -= (ki[u_start]["iro_kyori"][x] + ki[v_start]["iro_kyori"][x] - 2*ki[u]["iro_kyori"][x])
    sum += y*(ki[u_start]["num"][x] + ki[v_start]["num"][x] - 2*ki[u]["num"][x])
    print(sum)

Submission status: Time Limit Exceeded

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


N, Q = list(map(int, input().split()))

ki = [dict() for i in range(N)]
for node in ki:
    node["edge"] = []
for i in range(N-1):
    a, b, c, d = list(map(int, input().split()))
    ki[a - 1]["edge"].append([b - 1, c, d])
    ki[b - 1]["edge"].append([a - 1, c, d])

ki[0]["kyori"] = 0
ki[0]["oya"] = [-1, -1]
hukasa = []
for edge in ki[0]["edge"]:
    hukasa.append(edge[0])
    ki[edge[0]]["oya"] = [0, edge[1]]
    ki[edge[0]]["kyori"] = ki[0]["kyori"] + edge[2]

while len(hukasa) > 0:
    node = hukasa.pop()
    for edge in ki[node]["edge"]:
        if edge[0] != ki[node]["oya"][0]:
            hukasa.append(edge[0])
            ki[edge[0]]["oya"] = [node, edge[1]]
            ki[edge[0]]["kyori"] = ki[node]["kyori"] + edge[2]

for q in range(Q):
    x, y, u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    u_start = u
    v_start = v
    diff = 0
    while u != v:
        if ki[u]["kyori"] < ki[v]["kyori"]:
            node = v
            v = ki[node]["oya"][0]
        else:
            node = u
            u = ki[node]["oya"][0]
        if ki[node]["oya"][1] == x:
            diff += y - (ki[node]["kyori"] - ki[ki[node]["oya"][0]]["kyori"])
    sum = ki[u_start]["kyori"] + ki[v_start]["kyori"] - 2 * ki[u]["kyori"] +diff
    print(sum)

Submission status: Time Limit Exceeded

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


N, Q = list(map(int, input().split()))

ki = [dict() for i in range(N)]
for node in ki:
    node["edge"] = []
for i in range(N-1):
    a, b, c, d = list(map(int, input().split()))
    ki[a - 1]["edge"].append([b - 1, c, d])
    ki[b - 1]["edge"].append([a - 1, c, d])

ki[0]["kyori"] = 0
ki[0]["oya"] = [-1, -1]
hukasa = []
for edge in ki[0]["edge"]:
    hukasa.append(edge[0])
    ki[edge[0]]["oya"] = [0, edge[1]]
    ki[edge[0]]["kyori"] = ki[0]["kyori"] + edge[2]

while len(hukasa) > 0:
    node = hukasa.pop()
    for edge in ki[node]["edge"]:
        if edge[0] != ki[node]["oya"][0]:
            hukasa.append(edge[0])
            ki[edge[0]]["oya"] = [node, edge[1]]
            ki[edge[0]]["kyori"] = ki[node]["kyori"] + edge[2]

for q in range(Q):
    x, y, u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    sum = 0
    while u != v:
        if ki[u]["kyori"] < ki[v]["kyori"]:
            node = v
        else:
            node = u
        if ki[node]["oya"][1] != x:
            sum += ki[node]["kyori"] - ki[ki[node]["oya"][0]]["kyori"]
        else:
            sum += y
        if node == v:
            v = ki[node]["oya"][0]
        else:
            u = ki[node]["oya"][0]

    print(sum)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
from math import log
from collections import deque

def solve():
    N, Q = map(int, input().split())
    es = [[] for i in range(N+1)]
    for i in range(N-1):
        u, v, c, d = map(int, input().split())
        es[u].append([v, c, d])
        es[v].append([u, c, d])
    LOG_N = int(log(N, 2)) + 1
    parent = [[-1] * (N+1) for i in range(LOG_N)]
    level = [None] * (N+1)
    level[1] = 0
    dq = deque()
    dq.append(1)
    while dq:
        v = dq.popleft()
        p = parent[0][v]
        lv = level[v]
        for u, c, d in es[v]:
            if u != p:
                parent[0][u] = v
                level[u] = lv + 1
                dq.append(u)
    for k in range(LOG_N-1):
        parentk = parent[k]
        for v in range(1, N+1):
            if parentk[v] < 0:
                parent[k+1][v] = -1
            else:
                parent[k+1][v] = parentk[parentk[v]]

    def lca(u, v):
        if level[u] > level[v]:
            u, v = v, u
        for k in range(LOG_N)[::-1]:
            if (level[v] - level[u]) >> k & 1:
                v = parent[k][v]
        if u == v:
            return u
        for k in range(LOG_N)[::-1]:
            if parent[k][u] != parent[k][v]:
                u, v = parent[k][u], parent[k][v]
        return parent[0][u]

    qs = [[] for i in range(N+1)]
    for i in range(Q):
        x, y, u, v = map(int, input().split())
        qs[u].append([i, x, y, 1])
        qs[v].append([i, x, y, 1])
        a = lca(u, v)
        qs[a].append([i, x, y, -2])
    ds = [0] * N
    cnt = [0] * N
    query = [0] * Q

    def EulerTour(v, p, d):
        for id, col, y, f in qs[v]:
            query[id] += f * (d + y * cnt[col] - ds[col])
        for u, c, _d in es[v]:
            if u != p:
                ds[c] += _d
                cnt[c] += 1
                EulerTour(u, v, d + _d)
                ds[c] -= _d
                cnt[c] -= 1

    EulerTour(1, -1, 0)
    for res in query:
        print(res)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)

n,q = map(int,input().split(" "))
data = [[] for _ in range(n+1)]
for _ in range(n-1):
    n1, n2, c, l = map(int,input().split(" "))
    data[n1].append([n2,c,l])
    data[n2].append([n1,c,l])

#print(data)
#node in data = [node,c,l]
'''
for _ in range(q):
    c, l , s ,e = map(int,input().split(" "))
    stack = [s]
    path = [s]
    ifReached = [0 for _ in range(n+1)]
    ifReached[1] = 1
    while True:
        if stack == []:
            break
            print("wtf")
        else:
            start = stack.pop()
            for node in data[start]:
                if ifReached[node] == 0:
'''
                    


def divein(s):
    global  ifReached, ifFound, stack, light
    for dat in data[s]:
        node = dat[0]
        if ifReached[node] == 0:
            ifReached[node] = 1
            if node == g:
                light.append([dat[1],dat[2]])
                ifFound = True
                return
            divein(node)
            if ifFound:
                light.append([dat[1],dat[2]])
                return
        
for _ in range(q):
    c, l , s ,g = map(int,input().split(" "))
    light = []
    ifReached = [0 for _ in range(n+1)]
    ifReached[s] = 1
    ifFound = False
    divein(s)

    #距離の計算
    ans2 = 0
    for ele in light:
        if ele[0] == c:
            ans2 += l
        else:
            ans2 += ele[1]
    print(ans2)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import operator
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class SegmentTree:
    # http://tsutaj.hatenablog.com/entry/2017/03/29/204841
    def __init__(self, size, fn=operator.add, default=None, initial_values=None):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        :param default:
        :param list initial_values:
        """
        default = default or 0

        # size 以上である最小の 2 冪を size とする
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._fn = fn

        self._tree = [default] * (self._size * 2 - 1)
        if initial_values:
            i = self._size - 1
            for v in initial_values:
                self._tree[i] = v
                i += 1
            i = self._size - 2
            while i >= 0:
                self._tree[i] = self._fn(self._tree[i * 2 + 1], self._tree[i * 2 + 2])
                i -= 1

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size


def eulerian_trail(tree, max_v, root=0):
    """
    木のオイラー路; オイラーツアー
    :param list of (list of (int, int, int)) tree:
    :param int max_v:
    :param int root:
    :return: (trails, depths)
    :rtype: (list of int, list of int, list of (int, int))
    """
    seen = [False] * (max_v + 1)
    # 頂点の履歴
    trails = []
    # 深さの履歴
    depths = []
    # list of (color, weight)
    edges = []
    # Overflow 回避のためループで
    stack = [(root, 0, (0, 0), True)]
    while stack:
        v, d, edge, forward = stack.pop()
        seen[v] = True
        trails.append(v)
        depths.append(d)
        edges.append(edge)
        if not forward:
            continue
        for u, c, w in tree[v]:
            if not seen[u]:
                stack.append((v, d, (c, -w), False))
                stack.append((u, d + 1, (c, w), True))
    return trails, depths, edges


N, Q = list(map(int, sys.stdin.readline().split()))
ABCD = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]
XYVU = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

#: :type: list of (list of (int, int, int))
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))

trails, depths, edges = eulerian_trail(graph, max_v=N, root=1)
ids = [-1] * (N + 1)
for i, t in enumerate(trails):
    ids[t] = i

distances = []
color_dist = defaultdict(lambda: [(-1, 0)])
color_cnt = defaultdict(lambda: [(-1, 0)])
s = 0
for i, (c, d) in enumerate(edges):
    s += d
    distances.append(s)

    color_dist[c].append((i, color_dist[c][-1][1] + d))
    _, cc = color_cnt[c][-1]
    color_cnt[c].append((i, cc + 1 if d > 0 else cc - 1))

st = SegmentTree(size=len(trails), fn=min, default=(IINF, -1), initial_values=list(zip(depths, trails)))


def get_lca(v, u):
    iv, iu = ids[v], ids[u]
    if iv > iu:
        iv, iu = iu, iv
    _, ret = st.get(iv, iu + 1)
    return ret


def distance(v):
    # v から root までの距離
    return distances[ids[v]]


def count_color(v, c):
    # v から root までの c の数
    iv = ids[v]
    i = bisect.bisect_left(color_cnt[c], (iv + 1, 0))
    return color_cnt[c][i - 1][1]


def distance_color(v, c):
    # v から root までの c の数
    iv = ids[v]
    i = bisect.bisect_left(color_dist[c], (iv + 1, 0))
    return color_dist[c][i - 1][1]


for x, y, u, v in XYVU:
    lca = get_lca(u, v)
    d = distance(u) + distance(v) - distance(lca) * 2
    c = count_color(u, x) + count_color(v, x) - count_color(lca, x) * 2
    s = distance_color(u, x) + distance_color(v, x) - distance_color(lca, x) * 2
    print(d - s + c * y)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
from math import log
from collections import deque

def solve():
    N, Q = map(int, input().split())
    es = [[] for i in range(N+1)]
    for i in range(N-1):
        u, v, c, d = map(int, input().split())
        es[u].append([v, c, d])
        es[v].append([u, c, d])
    LOG_N = int(log(N, 2)) + 1
    parent = [[-1] * (N+1) for i in range(LOG_N)]
    level = [None] * (N+1)
    level[1] = 0
    dist = [None] * (N+1)
    dist[1] = 0
    dq = deque()
    dq.append(1)
    while dq:
        v = dq.popleft()
        p = parent[0][v]
        lv = level[v]
        dv = dist[v]
        for u, c, d in es[v]:
            if u != p:
                parent[0][u] = v
                level[u] = lv + 1
                dist[u] = dv + d
                dq.append(u)
    for k in range(LOG_N-1):
        parentk = parent[k]
        for v in range(1, N+1):
            if parentk[v] < 0:
                parent[k+1][v] = -1
            else:
                parent[k+1][v] = parentk[parentk[v]]

    def lca(u, v):
        if level[u] > level[v]:
            u, v = v, u
        for k in range(LOG_N)[::-1]:
            if (level[v] - level[u]) >> k & 1:
                v = parent[k][v]
        if u == v:
            return u
        for k in range(LOG_N)[::-1]:
            if parent[k][u] != parent[k][v]:
                u, v = parent[k][u], parent[k][v]
        return parent[0][u]

    qs = [[] for i in range(N+1)]
    query = [None] * Q
    for i in range(Q):
        x, y, u, v = map(int, input().split())
        qs[u].append([i, x, y, 1])
        qs[v].append([i, x, y, 1])
        a = lca(u, v)
        qs[a].append([i, x, y, -2])
        query[i] = dist[v] + dist[u] - 2 * dist[a]

    def EulerTour(v, p, ds, cnt):
        for id, col, y, f in qs[v]:
            query[id] += f * (y * cnt[col] - ds[col])
        for u, c, d in es[v]:
            if u != p:
                ds[c] += d
                cnt[c] += 1
                EulerTour(u, v, ds, cnt)
                ds[c] -= d
                cnt[c] -= 1

    ds = [0] * N
    cnt = [0] * N
    EulerTour(1, -1, ds, cnt)
    for res in query:
        print(res)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
from math import log

def solve():
    N, Q = map(int, input().split())
    es = [[] for i in range(N+1)]
    for i in range(N-1):
        u, v, c, d = map(int, input().split())
        es[u].append([v, c, d])
        es[v].append([u, c, d])
    LOG_N = int(log(N, 2)) + 1
    parent = [[-1] * (N+1) for i in range(LOG_N)]
    level = [None] * (N+1)
    dist = [None] * (N+1)

    def dfs(v, p, lv, d):
        parent[0][v] = p
        level[v] = lv
        dist[v] = d
        for u, c, _d in es[v]:
            if u != p:
                dfs(u, v, lv+1, d+_d)

    dfs(1, -1, 0, 0)
    for k in range(LOG_N-1):
        parentk = parent[k]
        for v in range(1, N+1):
            if parentk[v] < 0:
                parent[k+1][v] = -1
            else:
                parent[k+1][v] = parentk[parentk[v]]

    def lca(u, v):
        if level[u] > level[v]:
            u, v = v, u
        for k in range(LOG_N)[::-1]:
            if (level[v] - level[u]) >> k & 1:
                v = parent[k][v]
        if u == v:
            return u
        for k in range(LOG_N)[::-1]:
            if parent[k][u] != parent[k][v]:
                u, v = parent[k][u], parent[k][v]
        return parent[0][u]

    qs = [[] for i in range(N+1)]
    query = [None] * Q
    for i in range(Q):
        x, y, u, v = map(int, input().split())
        qs[u].append([i, x, y, 1])
        qs[v].append([i, x, y, 1])
        a = lca(u, v)
        qs[a].append([i, x, y, -2])
        query[i] = dist[v] + dist[u] - 2 * dist[a]
    ds = [0] * N
    cnt = [0] * N

    def EulerTour(v, p):
        for id, col, y, f in qs[v]:
            query[id] += f * (y * cnt[col] - ds[col])
        for u, c, d in es[v]:
            if u != p:
                ds[c] += d
                cnt[c] += 1
                EulerTour(u, v)
                ds[c] -= d
                cnt[c] -= 1

    EulerTour(1, -1)
    for res in query:
        print(res)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
from math import log
from collections import deque

def solve():
    N, Q = map(int, input().split())
    es = [[] for i in range(N+1)]
    for i in range(N-1):
        u, v, c, d = map(int, input().split())
        es[u].append([v, c, d])
        es[v].append([u, c, d])
    LOG_N = int(log(N, 2)) + 1
    parent = [[-1] * (N+1) for i in range(LOG_N)]
    level = [None] * (N+1)
    level[1] = 0
    dist = [None] * (N+1)
    dist[1] = 0
    dq = deque()
    dq.append(1)
    while dq:
        v = dq.popleft()
        p = parent[0][v]
        lv = level[v]
        dv = dist[v]
        for u, c, d in es[v]:
            if u != p:
                parent[0][u] = v
                level[u] = lv + 1
                dist[u] = dv + d
                dq.append(u)
    for k in range(LOG_N-1):
        parentk = parent[k]
        for v in range(1, N+1):
            if parentk[v] < 0:
                parent[k+1][v] = -1
            else:
                parent[k+1][v] = parentk[parentk[v]]

    def lca(u, v):
        if level[u] > level[v]:
            u, v = v, u
        for k in range(LOG_N)[::-1]:
            if (level[v] - level[u]) >> k & 1:
                v = parent[k][v]
        if u == v:
            return u
        for k in range(LOG_N)[::-1]:
            if parent[k][u] != parent[k][v]:
                u, v = parent[k][u], parent[k][v]
        return parent[0][u]

    qs = [[] for i in range(N+1)]
    query = [None] * Q
    for i in range(Q):
        x, y, u, v = map(int, input().split())
        qs[u].append([i, x, y, 1])
        qs[v].append([i, x, y, 1])
        a = lca(u, v)
        qs[a].append([i, x, y, -2])
        query[i] = dist[v] + dist[u] - 2 * dist[a]
    ds = [0] * N
    cnt = [0] * N

    def EulerTour(v, p):
        for id, col, y, f in qs[v]:
            query[id] += f * (y * cnt[col] - ds[col])
        for u, c, d in es[v]:
            if u != p:
                ds[c] += d
                cnt[c] += 1
                EulerTour(u, v)
                ds[c] -= d
                cnt[c] -= 1

    EulerTour(1, -1)
    for res in query:
        print(res)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
from math import log
from collections import deque

def solve():
    N, Q = map(int, input().split())
    es = [[] for i in range(N)]
    for i in range(N-1):
        u, v, c, d = map(int, input().split())
        u -= 1
        v -= 1
        es[u].append([v, c, d])
        es[v].append([u, c, d])
    LOG_N = int(log(N, 2)) + 1
    parent = [[-1] * N for i in range(LOG_N)]
    level = [None] * N
    level[0] = 0
    dist = [None] * N
    dist[0] = 0
    dq = deque()
    dq.append(0)
    while dq:
        v = dq.popleft()
        p = parent[0][v]
        lv = level[v]
        dv = dist[v]
        for u, c, d in es[v]:
            if u != p:
                parent[0][u] = v
                level[u] = lv + 1
                dist[u] = dv + d
                dq.append(u)
    for k in range(LOG_N-1):
        parentk = parent[k]
        for v in range(N):
            if parentk[v] < 0:
                parent[k+1][v] = -1
            else:
                parent[k+1][v] = parentk[parentk[v]]

    def lca(u, v):
        if level[u] > level[v]:
            t, u = u, v
            v = t
        for k in range(LOG_N)[::-1]:
            if (level[v] - level[u]) >> k & 1:
                v = parent[k][v]
            if level[v] == level[u]:
                break
        if u == v:
            return u
        for k in range(LOG_N)[::-1]:
            if parent[k][u] != parent[k][v]:
                u, v = parent[k][u], parent[k][v]
        return parent[0][u]

    qs = [[] for i in range(N)]
    query = [None] * Q
    for i in range(Q):
        x, y, u, v = map(int, input().split())
        u -= 1
        v -= 1
        qs[u].append([i, x, y, 1])
        qs[v].append([i, x, y, 1])
        a = lca(u, v)
        qs[a].append([i, x, y, -2])
        query[i] = dist[v] + dist[u] - 2 * dist[a]
    ds = [0] * N
    cnt = [0] * N

    def EulerTour(v, p):
        for id, col, y, f in qs[v]:
            query[id] += f * (y * cnt[col] - ds[col])
        for u, c, d in es[v]:
            if u != p:
                ds[c] += d
                cnt[c] += 1
                EulerTour(u, v)
                ds[c] -= d
                cnt[c] -= 1

    EulerTour(0, -1)
    for res in query:
        print(res)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
from math import log

def solve():
    N, Q = map(int, input().split())
    es = [[] for i in range(N)]
    for i in range(N-1):
        a, b, c, d = map(int, input().split())
        a -= 1
        b -= 1
        es[a].append([b, c, d])
        es[b].append([a, c, d])
    LOG_N = int(log(N, 2)) + 1
    parent = [[-1] * N for i in range(LOG_N)]
    level = [0] * N
    dist = [None] * N

    def dfs(v, p, lv, d):
        parent[0][v] = p
        level[v] = lv
        dist[v] = d
        for u, c, _d in es[v]:
            if u != p:
                dfs(u, v, lv+1, d+_d)

    dfs(1, -1, 0, 0)
    for k in range(LOG_N-1):
        parentk = parent[k]
        for v in range(N):
            if parentk[v] < 0:
                parent[k+1][v] = -1
            else:
                parent[k+1][v] = parentk[parentk[v]]

    def lca(u, v):
        if level[u] > level[v]:
            t, u = u, v
            v = t
        for k in range(LOG_N)[::-1]:
            if (level[v] - level[u]) >> k & 1:
                v = parent[k][v]
            if level[v] == level[u]:
                break
        if u == v:
            return u
        for k in range(LOG_N)[::-1]:
            if parent[k][u] != parent[k][v]:
                u, v = parent[k][u], parent[k][v]
        return parent[0][u]

    qs = [[] for i in range(N)]
    for i in range(Q):
        x, y, u, v = map(int, input().split())
        u -= 1
        v -= 1
        qs[u].append([i, x, y, 1])
        qs[v].append([i, x, y, 1])
        qs[lca(u, v)].append([i, x, y, -2])
    query = [0] * Q
    ds = [0] * N
    cnt = [0] * N
    def EulerTour(v, p):
        for id, col, y, f in qs[v]:
            query[id] += f * (dist[v] + y * cnt[col] - ds[col])
        for u, c, d in es[v]:
            if u != p:
                ds[c] += d
                cnt[c] += 1
                EulerTour(u, v)
                ds[c] -= d
                cnt[c] -= 1

    EulerTour(1, -1)
    for res in query:
        print(res)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)

n,q = map(int,input().split(" "))
data = [[] for _ in range(n+1)]
for _ in range(n-1):
    n1, n2, c, l = map(int,input().split(" "))
    data[n1].append([n2,c,l])
    data[n2].append([n1,c,l])

#print(data)
#node in data = [node,c,l]
'''
for _ in range(q):
    c, l , s ,e = map(int,input().split(" "))
    stack = [s]
    path = [s]
    ifReached = [0 for _ in range(n+1)]
    ifReached[1] = 1
    while True:
        if stack == []:
            break
            print("wtf")
        else:
            start = stack.pop()
            for node in data[start]:
                if ifReached[node] == 0:
'''
                    


def divein(s):
    global path, ifReached, ifFound, stack
    for dat in data[s]:
        node = dat[0]
        if ifReached[node] == 0:
            ifReached[node] = 1
            if node == g:
                path.append(node)
                ifFound = True
                return
            divein(node)
            if ifFound:
                path.append(node)
                return
        
for _ in range(q):
    c, l , s ,g = map(int,input().split(" "))
    path = []
    ifReached = [0 for _ in range(n+1)]
    ifReached[s] = 1
    ifFound = False
    divein(s)
    path.append(s)

    #距離の計算
    
    ans = 0
    for i in range(len(path)-1):
        j = path[i]
        a = path[i+1]
        for oppai in data[j]:
            if oppai[0] == a:
                if oppai[1] == c:
                    ans += l
                else:
                    ans += oppai[2]
                break
    print(ans)