Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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)


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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)


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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)


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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)

Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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)

Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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)


Fixed submission:
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()