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
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)]
    depth = [0] * N

    def dfs(v, p, d):
        parent[0][v] = p
        depth[v] = d
        for u in es[v]:
            if u[0] != p:
                dfs(u[0], v, d+1)

    dfs(1, -1, 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 depth[u] > depth[v]:
            t, u = u, v
            v = t
        for k in range(LOG_N)[::-1]:
            if (depth[v] - depth[u]) >> k & 1:
                v = parent[k][v]
            if depth[v] == depth[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, 1))
        qs[v].append((i, x, 1))
        qs[lca(u, v)].append((i, x, -2))
        query[i] = [y, 0, 0]
    ds = [0] * N
    cnt = [0] * N
    def EulerTour(v, p, alld):
        for id, col, f in qs[v]:
            query[id][1] += f * cnt[col]
            query[id][2] += f * (alld - ds[col])
        for u, c, d in es[v]:
            if u != p:
                ds[c] += d
                cnt[c] += 1
                EulerTour(u, v, alld+d)
                ds[c] -= d
                cnt[c] -= 1

    EulerTour(1, -1, 0)
    for y, c, d in query:
        print(y * c + d)

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)]
    depth = [0] * N

    def dfs(v, p, d):
        parent[0][v] = p
        depth[v] = d
        for u in es[v]:
            if u[0] != p:
                dfs(u[0], v, d+1)

    dfs(1, -1, 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 depth[u] > depth[v]:
            t, u = u, v
            v = t
        for k in range(LOG_N)[::-1]:
            if (depth[v] - depth[u]) >> k & 1:
                v = parent[k][v]
            if depth[v] == depth[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, 1])
        qs[v].append([i, x, 1])
        qs[lca(u, v)].append([i, x, -2])
        query[i] = [y, 0, 0]
    ds = [0] * N
    cnt = [0] * N
    def EulerTour(v, p, alld):
        for id, col, f in qs[v]:
            query[id][1] += f * cnt[col]
            query[id][2] += f * (alld - ds[col])
        for u, c, d in es[v]:
            if u != p:
                ds[c] += d
                cnt[c] += 1
                EulerTour(u, v, alld+d)
                ds[c] -= d
                cnt[c] -= 1

    EulerTour(1, -1, 0)
    for y, c, d in query:
        print(y * c + d)

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)]
    depth = [0] * N

    def dfs(v, p, d):
        parent[0][v] = p
        depth[v] = d
        for u in es[v]:
            if u[0] != p:
                dfs(u[0], v, d+1)

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

    def lca(u, v):
        if depth[u] > depth[v]:
            t, u = u, v
            v = t
        for k in range(LOG_N)[::-1]:
            if (depth[v] - depth[u]) >> k & 1:
                v = parent[k][v]
            if depth[v] == depth[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, 1])
        qs[v].append([i, x, 1])
        qs[lca(u, v)].append([i, x, -2])
        query[i] = [y, 0, 0]
    ds = [0] * N
    cnt = [0] * N
    def EulerTour(v, p, alld):
        for id, col, f in qs[v]:
            query[id][1] += f * cnt[col]
            query[id][2] += f * (alld - ds[col])
        for u, c, d in es[v]:
            if u != p:
                ds[c] += d
                cnt[c] += 1
                EulerTour(u, v, alld+d)
                ds[c] -= d
                cnt[c] -= 1

    EulerTour(1, -1, 0)
    for y, c, d in query:
        print(y * c + d)

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)]
    depth = [0] * N

    def dfs(v, p, d):
        parent[0][v] = p
        depth[v] = d
        for u in es[v]:
            if u[0] != p:
                dfs(u[0], v, d+1)

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

    def lca(u, v):
        if depth[u] > depth[v]:
            t, u = u, v
            v = t
        for k in range(LOG_N):
            if (depth[v] - depth[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)]
    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, 1])
        qs[v].append([i, x, 1])
        qs[lca(u, v)].append([i, x, -2])
        query[i] = [y, 0, 0]
    ds = [0] * N
    cnt = [0] * N
    def EulerTour(v, p, alld):
        for id, col, f in qs[v]:
            query[id][1] += f * cnt[col]
            query[id][2] += f * (alld - ds[col])
        for u, c, d in es[v]:
            if u != p:
                ds[c] += d
                cnt[c] += 1
                EulerTour(u, v, alld+d)
                ds[c] -= d
                cnt[c] -= 1

    EulerTour(1, -1, 0)
    for y, c, d in query:
        print(y * c + d)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

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)]
depth = [0] * N

def dfs(v, p, d):
    parent[0][v] = p
    depth[v] = d
    for u in es[v]:
        if u[0] != p:
            dfs(u[0], v, d+1)

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

def lca(u, v):
    if depth[u] > depth[v]:
        t, u = u, v
        v = t
    for k in range(LOG_N):
        if (depth[v] - depth[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)]
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, 1])
    qs[v].append([i, x, 1])
    qs[lca(u, v)].append([i, x, -2])
    query[i] = [y, 0, 0]
ds = [0] * N
cnt = [0] * N
def EulerTour(v, p, alld):
    for id, col, f in qs[v]:
        query[id][1] += f * cnt[col]
        query[id][2] += f * (alld - ds[col])
    for u, c, d in es[v]:
        if u != p:
            ds[c] += d
            cnt[c] += 1
            EulerTour(u, v, alld+d)
            ds[c] -= d
            cnt[c] -= 1

EulerTour(1, -1, 0)
for y, c, d in query:
    print(y * c + d)

Submission status: Time Limit Exceeded

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

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 = LOG_N = int(log(N, 2)) + 1
parent = [[-1 for i in range(N)] for i in range(LOG_N)]
depth = [0 for _ in range(N)]

def dfs(v, p, d):
    parent[0][v] = p
    depth[v] = d
    for u in es[v]:
        if u[0] != p:
            dfs(u[0], v, d+1)

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

def lca(u, v):
    if depth[u] > depth[v]:
        t, u = u, v
        v = t
    for k in range(LOG_N):
        if (depth[v] - depth[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())
    u -= 1
    v -= 1
    qs[u].append((i, x, 1))
    qs[v].append((i, x, 1))
    qs[lca(u, v)].append((i, x, -2))
    query[i] = [y, 0, 0]
ds = [0] * N
cnt = [0] * N
def EulerTour(v, p, alld):
    for id, col, f in qs[v]:
        query[id][1] += f * cnt[col]
        query[id][2] += f * (alld - ds[col])
    for u, c, d in es[v]:
        if u != p:
            ds[c] += d
            cnt[c] += 1
            EulerTour(u, v, alld+d)
            ds[c] -= d
            cnt[c] -= 1

EulerTour(1, -1, 0)
for y, c, d in query:
    print(y * c + d)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from math import log

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 = LOG_N = int(log(N, 2)) + 1
parent = [[-1 for i in range(N)] for i in range(LOG_N)]
depth = [0 for _ in range(N)]

def dfs(v, p, d):
    parent[0][v] = p
    depth[v] = d
    for u in es[v]:
        if u[0] != p:
            dfs(u[0], v, d+1)

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

def lca(u, v):
    if depth[u] > depth[v]:
        t, u = u, v
        v = t
    for k in range(LOG_N):
        if (depth[v] - depth[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())
    u -= 1
    v -= 1
    qs[u].append([i, x, 1])
    qs[v].append([i, x, 1])
    c = lca(u, v)
    qs[c].append([i, x, -2])
    query[i] = [y, 0, 0]
ds = [0] * N
cnt = [0] * N
def EulerTour(v, p = -1, alld=0):
    for q in qs[v]:
        id, col, f = q
        query[id][1] += f * cnt[col]
        query[id][2] += f * (alld - ds[col])
    for u, c, d in es[v]:
        if u != p:
            ds[c] += d
            cnt[c] += 1
            EulerTour(u, v, alld+d)
            ds[c] -= d
            cnt[c] -= 1

EulerTour(1)
for y, c, d in query:
    print(y * c + d)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from math import log

class LCA:
    def __init__(self, N, root, es):
        self.N = N
        self.root = root
        self.es = es
        self.LOG_N = LOG_N = int(log(N, 2)) + 1
        self.parent = [[-1 for _ in range(N)] for _ in range(LOG_N)]
        self.depth = [0 for _ in range(N)]
        self.dfs(root, -1, 0)
        parent = self.parent
        for k in range(LOG_N-1):
            for v in range(N):
                if parent[k][v] < 0:
                    parent[k+1][v] = -1
                else:
                    parent[k+1][v] = parent[k][parent[k][v]]
        self.parent = parent

    def dfs(self, v, p, d):
        self.parent[0][v] = p
        self.depth[v] = d
        for u in self.es[v]:
            if u[0] != p:
                self.dfs(u[0], v, d+1)

    def lca(self, u, v):
        LOG_N = self.LOG_N
        depth = self.depth
        parent = self.parent
        if depth[u] > depth[v]:
            t, u = u, v
            v = t
        for k in range(LOG_N):
            if (depth[v] - depth[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]

N, Q = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(N-1):
    a, b, c, d = map(int, input().split())
    es[a].append([b, c, d])
    es[b].append([a, c, d])
lca = LCA(N+1, 1, es)
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, 1])
    qs[v].append([i, x, 1])
    c = lca.lca(u, v)
    qs[c].append([i, x, -2])
    query[i] = [y, 0, 0]
ds = [0] * N
cnt = [0] * N
def EulerTour(v, p = -1, alld=0):
    for q in qs[v]:
        id, col, f = q
        query[id][1] += f * cnt[col]
        query[id][2] += f * (alld - ds[col])
    for u, c, d in es[v]:
        if u != p:
            ds[c] += d
            cnt[c] += 1
            EulerTour(u, v, alld+d)
            ds[c] -= d
            cnt[c] -= 1

EulerTour(1)
for y, c, d in query:
    print(y * c + d)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from math import log

class LCA:

    def __init__(self, N, root, es):
        self.N = N
        self.root = root
        self.es = es
        self.LOG_N = LOG_N = int(log(N, 2)) + 1
        self.parent = [[-1 for _ in range(N)] for _ in range(LOG_N)]
        self.depth = [0 for _ in range(N)]
        self.dfs(root, -1, 0)
        parent = self.parent
        for k in range(LOG_N-1):
            for v in range(N):
                if parent[k][v] < 0:
                    parent[k+1][v] = -1
                else:
                    parent[k+1][v] = parent[k][parent[k][v]]
        self.parent = parent

    def dfs(self, v, p, d):
        self.parent[0][v] = p
        self.depth[v] = d
        for u in self.es[v]:
            if u != p:
                self.dfs(u, v, d+1)

    def lca(self, u, v):
        LOG_N = self.LOG_N
        depth = self.depth
        parent = self.parent
        if depth[u] > depth[v]:
            t, u = u, v
            v = t
        for k in range(LOG_N):
            if (depth[v] - depth[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]

N, Q = map(int, input().split())
es = [[] for i in range(N+1)]
_es = [[] for i in range(N+1)]
for i in range(N-1):
    a, b, c, d = map(int, input().split())
    es[a].append([b, c, d])
    es[b].append([a, c, d])
    _es[a].append(b)
    _es[b].append(a)
lca = LCA(N+1, 1, _es)
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, 1])
    qs[v].append([i, x, 1])
    c = lca.lca(u, v)
    qs[c].append([i, x, -2])
    query[i] = [y, 0, 0]

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

EulerTour(1)
for y, c, d in query:
    print(y * c + d)

Submission status: Time Limit Exceeded

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

def f(n,q):
    def dfs(i, oi=-1, dpt=0):
        depth[i] = dpt
        parent_2k[0][i] = oi
        for ki, c, d in to[i]:
            if ki == oi: continue
            dfs(ki, i, dpt + 1)
        return

    def make_parent(level):
        parent_2kk1 = parent_2k[0]
        for k in range(1, level):
            parent_2kk = parent_2k[k]
            for i in range(n):
                parent1 = parent_2kk1[i]
                if parent1 != -1:
                    parent_2kk[i] = parent_2kk1[parent1]
            parent_2kk1 = parent_2kk
        return

    def lca(u, v):
        dist_uv = depth[u] - depth[v]
        if dist_uv < 0:
            u, v = v, u
            dist_uv *= -1

        k = 0
        while dist_uv:
            if dist_uv & 1:
                u = parent_2k[k][u]
            dist_uv >>= 1
            k += 1

        if u == v:
            return u

        for k in range(int(log2(depth[u])) + 1, -1, -1):
            pu = parent_2k[k][u]
            pv = parent_2k[k][v]
            if pu != pv:
                u = pu
                v = pv
        return parent_2k[0][u]

    to = defaultdict(list)
    root = 0
    depth = [0] * n
    level = int(log2(n)) + 1
    parent_2k = [[-1] * n for _ in range(level)]

    for _ in range(n - 1):
        a, b, c, d = list(map(int, input().split()))
        to[a - 1] += [[b - 1, c - 1, d]]
        to[b - 1] += [[a - 1, c - 1, d]]

    dfs(root)
    make_parent(level)

    qs = [[] for _ in range(n)]
    for qi in range(q):
        x, y, u, v = map(int, input().split())
        qs[u - 1].append([qi, x - 1, y, 1])
        qs[v - 1].append([qi, x - 1, y, 1])
        qs[lca(u - 1, v - 1)].append([qi, x - 1, y, -2])

    cnt_c = [0] * n
    sum_c = [0] * n
    ans = [0] * q

    def dfs2(i, oi=-1, sum_d=0):
        for qi, qc, qd, qk in qs[i]:
            ans[qi] += (sum_d - sum_c[qc] + qd * cnt_c[qc]) * qk
        for ki, c, d in to[i]:
            if ki == oi: continue
            cnt_c[c] += 1
            sum_c[c] += d
            dfs2(ki, i, sum_d + d)
            cnt_c[c] -= 1
            sum_c[c] -= d
        return

    dfs2(root)
    for x in ans:
        print(x)

n, q = map(int, input().split())
f(n,q)

Submission status: Time Limit Exceeded

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

def dfs(i, oi=-1, dpt=0):
    depth[i] = dpt
    parent_2k[0][i] = oi
    for ki, c, d in to[i]:
        if ki == oi: continue
        dfs(ki, i, dpt + 1)
    return

def make_parent(level):
    parent_2kk1 = parent_2k[0]
    for k in range(1, level):
        parent_2kk = parent_2k[k]
        for i in range(n):
            parent1 = parent_2kk1[i]
            if parent1 != -1:
                parent_2kk[i] = parent_2kk1[parent1]
        parent_2kk1 = parent_2kk
    return

def lca(u, v):
    dist_uv = depth[u] - depth[v]
    if dist_uv < 0:
        u, v = v, u
        dist_uv *= -1

    k = 0
    while dist_uv:
        if dist_uv & 1:
            u = parent_2k[k][u]
        dist_uv >>= 1
        k += 1

    if u == v:
        return u

    for k in range(int(log2(depth[u])) + 1, -1, -1):
        pu = parent_2k[k][u]
        pv = parent_2k[k][v]
        if pu != pv:
            u = pu
            v = pv
    return parent_2k[0][u]

root = 0
n, q = map(int, input().split())
to = defaultdict(list)
depth = [0] * n
level = int(log2(n)) + 1
parent_2k = [[-1] * n for _ in range(level)]

for _ in range(n - 1):
    a, b, c, d = list(map(int, input().split()))
    to[a - 1] += [[b - 1, c - 1, d]]
    to[b - 1] += [[a - 1, c - 1, d]]

dfs(root)
make_parent(level)

qs = [[] for _ in range(n)]
for qi in range(q):
    x, y, u, v = map(int, input().split())
    qs[u - 1].append([qi, x - 1, y, 1])
    qs[v - 1].append([qi, x - 1, y, 1])
    qs[lca(u - 1, v - 1)].append([qi, x - 1, y, -2])

cnt_c = [0] * n
sum_c = [0] * n
ans = [0] * q

def dfs2(i, oi=-1, sum_d=0):
    for qi, qc, qd, qk in qs[i]:
        ans[qi] += (sum_d - sum_c[qc] + qd * cnt_c[qc]) * qk
    for ki, c, d in to[i]:
        if ki == oi: continue
        cnt_c[c] += 1
        sum_c[c] += d
        dfs2(ki, i, sum_d + d)
        cnt_c[c] -= 1
        sum_c[c] -= d
    return

dfs2(root)
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


class Graph:

  def __init__(self):
    self.V = set()
    self.E = {}

  def add_edge(self, u, v, e):
    self.V.add(u)
    self.V.add(v)

    if u not in self.E: self.E[u] = {}
    self.E[u][v] = e
    if v not in self.E: self.E[v] = {}
    self.E[v][u] = e


class Edge:
  def __init__(self, weight, color):
    self.weight = weight
    self.color = color

  def __repr__(self):
    return str(self.weight)


class PrioritizedItem:
  def __init__(self, task, priority=1):
    self.task = task
    self.priority = priority

  def __eq__(self, other):
    return self.priority == other.priority

  def __lt__(self, other):
    return self.priority < other.priority


def bfs(graph: Graph):
  pred = {}

  starts = deque()
  starts.append((graph.V.__iter__().__next__(), {}))

  while len(starts) > 0:
    start, tmp = starts.popleft()
    tmp = tmp.copy()
    if start in tmp: del tmp[start]
    for v in graph.E[start]:
      if v not in pred:
        starts.append((v, tmp))

    pred[start] = tmp

    queue = deque()
    queue.append(start)
    while len(queue) > 0:
      u = queue.popleft()
      for v, edge in graph.E[u].items():
        if v != start and v not in tmp:
          tmp[v] = (u, edge)
          queue.append(v)

    # print(start, tmp)

  return pred


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

graph = Graph()
for _ in range(N - 1):
  a, b, c, d = map(int, input().strip().split())
  graph.add_edge(a, b, Edge(d, c))

pred = bfs(graph)

# questions = [map(int, input().strip().split()) for _ in range(Q)]
# for q in questions:
for _ in range(Q):
  # x, y, u, v = q
  x, y, u, v = map(int, input().strip().split())
  tmp = pred[u]

  total = 0
  current = v
  while current != u:
    current, edge = tmp[current]
    if edge.color == x:
      total += y
    else:
      total += edge.weight

  print(total)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


class Graph:

  def __init__(self):
    self.V = set()
    self.E = {}

  def add_edge(self, u, v, e):
    self.V.add(u)
    self.V.add(v)

    if u not in self.E: self.E[u] = {}
    self.E[u][v] = e
    if v not in self.E: self.E[v] = {}
    self.E[v][u] = e


class Edge:
  def __init__(self, weight, color):
    self.weight = weight
    self.color = color


class PrioritizedItem:
  def __init__(self, task, priority=1):
    self.task = task
    self.priority = priority

  def __eq__(self, other):
    return self.priority == other.priority

  def __lt__(self, other):
    return self.priority < other.priority


def bfs(graph: Graph, start, stop):
  pred = {}
  queue = deque()
  queue.append(start)
  while len(queue) > 0:
    u = queue.popleft()
    if u == stop:
      return pred

    for v, edge in graph.E[u].items():
      if v not in pred:
        pred[v] = (u, edge)
        queue.append(v)

  return pred


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

graph = Graph()
for _ in range(N - 1):
  a, b, c, d = map(int, input().strip().split())
  graph.add_edge(a, b, Edge(d, c))

questions = [map(int, input().strip().split()) for _ in range(Q)]
for q in questions:
  x, y, u, v = q
  pred = bfs(graph, u, v)

  total = 0
  current = v
  while current != u:
    current, edge = pred[current]
    if edge.color == x:
      total += y
    else:
      total += edge.weight

  print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
from bisect import bisect_right as br
N, K = map(int, input().split())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y, c, d = map(int, input().split())
    X[x-1].append((y-1, c-1, d))
    X[y-1].append((x-1, c-1, d))

P = [(-1, 0, 0)] * N
Q = [(0, 0, 0)]
R = []
ET = []
ct = 0
CT = [0] * (N-1) * 2
CTA = [-1]* N
BT = [[[-1], [0], [0]] for _ in range(N)]
while Q:
    i, c, d = Q.pop()
    if i < 0:
        BT[c][0].append(ct)
        BT[c][1].append(BT[c][1][-1]-1)
        BT[c][2].append(BT[c][2][-1]-d)
        ct += 1
        continue
    R.append(i)
    if i > 0:
        if CTA[i] < 0: CTA[i] = ct
        BT[c][0].append(ct)
        BT[c][1].append(BT[c][1][-1]+1)
        BT[c][2].append(BT[c][2][-1]+d)
        ct += 1
    
    for a, c, d in X[i][::-1]:
        if a != P[i][0]:
            ET.append((i, a))
            P[a] = (i, c, d)
            for k in range(len(X[a])):
                if X[a][k][0] == i:
                    del X[a][k]
                    break
            Q.append((~a, c, d))
            Q.append((a, c, d))

L = [[0, 0] for _ in range(N)]
for i in R[1:]:
    p, c, d = P[i]
    L[i][0] = L[p][0] + 1
    L[i][1] = L[p][1] + d

D = [[P[i][0] for i in range(N)]] + [[-1]*N for _ in range(16)]
for k in range(1, 17):
    for i in range(N):
        a = D[k-1][i]
        if a > 0:
            D[k][i] = D[k-1][a]

def lca(u0, v0):
    u, v = u0, v0
    if L[u][0] < L[v][0]:
        u, v = v, u
    
    while L[u][0] > L[v][0]:
        d = L[u][0] - L[v][0]
        dd = d.bit_length() - 1
        u = D[dd][u]
    if u == v:
        return u
    
    for i in range(17)[::-1]:
        if D[i][u] != D[i][v]:
            u = D[i][u]
            v = D[i][v]
    
    return D[0][u]
    

def calc(x, y, w):
    aa = br(BT[x][0], CTA[w]) - 1
    c = BT[x][1][aa]
    d = BT[x][2][aa]
    return L[w][1] + c*y - d

for _ in range(K):
    x, y, u, v = map(int, input().split())
    x, u, v = x-1, u-1, v-1
    ll = lca(u, v)
    print(calc(x, y, u) + calc(x, y, v) - 2*calc(x, y, ll))