Problem:


Score : 600 points

Problem Statement

There is a tree with N vertices numbered 1 to N.
The i-th edge in this tree connects Vertex a_i and Vertex b_i, and the color and length of that edge are c_i and d_i, respectively.
Here the color of each edge is represented by an integer between 1 and N-1 (inclusive). The same integer corresponds to the same color, and different integers correspond to different colors.

Answer the following Q queries:

Query j (1 \leq j \leq Q): assuming that the length of every edge whose color is x_j is changed to y_j, find the distance between Vertex u_j and Vertex v_j. (The changes of the lengths of edges do not affect the subsequent queries.)

Constraints

2 \leq N \leq 10^5

1 \leq Q \leq 10^5

1 \leq a_i, b_i \leq N

1 \leq c_i \leq N-1

1 \leq d_i \leq 10^4

1 \leq x_j \leq N-1

1 \leq y_j \leq 10^4

1 \leq u_j < v_j \leq N

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1 c_1 d_1
:
a_{N-1} b_{N-1} c_{N-1} d_{N-1}
x_1 y_1 u_1 v_1
:
x_Q y_Q u_Q v_Q

Output

Print Q lines. The j-th line (1 \leq j \leq Q) should contain the answer to Query j.

Sample Input 1

5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4

Sample Output 1

130
200
60

The graph in this input is as follows:

Here the edges of Color 1 are shown as solid red lines, the edge of Color 2 is shown as a bold green line, and the edge of Color 4 is shown as a blue dashed line.

Query 1: Assuming that the length of every edge whose color is 1 is changed to 100, the distance between Vertex 1 and Vertex 4 is 100 + 30 = 130.

Query 2: Assuming that the length of every edge whose color is 1 is changed to 100, the distance between Vertex 1 and Vertex 5 is 100 + 100 = 200.

Query 3: Assuming that the length of every edge whose color is 3 is changed to 1000 (there is no such edge), the distance between Vertex 3 and Vertex 4 is 20 + 10 + 30 = 60. Note that the edges of Color 1 now have their original lengths.



Sample input:
5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4


Sample output:
130
200
60

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 5 + 5)


def solve(n, links, queries, v_queries):
    def _query(a, b, data, m0, INF):
        yield INF
        a += m0
        b += m0
        while a < b:
            if b & 1:
                b -= 1
                yield data[b - 1]
            if a & 1:
                yield data[a - 1]
                a += 1
            a >>= 1
            b >>= 1

    def query(u, v):
        fu = first_appear[u]
        fv = first_appear[v]
        if fu > fv:
            fu, fv = fv, fu
        return euler_tour[min(_query(fu, fv + 1, data, m0, INF))[1]]

    def dfs(v, p, dep, tmp_dist, total_dist):
        first_appear[v] = len(euler_tour)
        depth[v] = dep
        euler_tour.append(v)
        parents[v] = p
        for x, arr in v_queries[v].items():
            arr[0] = total_dist - tmp_dist[x][0]
            arr[1] = tmp_dist[x][1]
        for u, (uc, ud) in links[v].items():
            if u == p:
                continue
            tmp_dist[uc][0] += ud
            tmp_dist[uc][1] += 1
            dfs(u, v, dep + 1, tmp_dist, total_dist + ud)
            tmp_dist[uc][0] -= ud
            tmp_dist[uc][1] -= 1
            euler_tour.append(v)

    def dfs2(v, x, y, dist, cnt):
        if v == 0:
            return dist, cnt
        p = parents[v]
        c, d = links[v][p]
        if x == c:
            cnt += 1
        else:
            dist += d
        return dfs2(p, x, y, dist, cnt)

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

    # Euler Tour の構築
    euler_tour = []
    first_appear = [0] * n
    depth = [0] * n
    parents = [0] * n

    tmp_dist = defaultdict(lambda: [0, 0])
    dfs(0, -1, 0, tmp_dist, 0)
    # print(euler_tour)
    # print(first_appear)
    # print(depth)
    # print(v_queries)
    # print(parents)

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

    # print(data)

    ans = []
    for x, y, u, v in queries:
        w = query(u, v)
        # print(u, v, w)
        qu = v_queries[u][x]
        qv = v_queries[v][x]
        du = qu[0] + qu[1] * y
        dv = qv[0] + qv[1] * y
        if w == 0:
            ans.append(du + dv)
            continue
        qw = v_queries[w]
        if x in qw:
            qw = qw[x]
            dw = qw[0] + qw[1] * y
        else:
            dist, cnt = dfs2(w, x, y, 0, 0)
            qw[x] = [dist, cnt]
            dw = dist + cnt * y
        ans.append(du + dv - 2 * dw)

    return ans


n, q = list(map(int, input().split()))
links = [{} for _ in range(n)]
lines = sys.stdin.readlines()
for line in lines[:n - 1]:
    a, b, c, d = list(map(int, line.split()))
    a -= 1
    b -= 1
    links[a][b] = (c, d)
    links[b][a] = (c, d)
queries = []
v_queries = [{} for _ in range(n)]
for line in lines[n - 1:]:
    x, y, u, v = map(int, line.split())
    u -= 1
    v -= 1
    queries.append((x, y, u, v))
    v_queries[u][x] = [0, 0]
    v_queries[v][x] = [0, 0]

ans = solve(n, links, queries, v_queries)

print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write
sys.setrecursionlimit(10**6)
N, Q = map(int, readline().split())
G = [[] for i in range(N)]
G0 = [[] for i in range(N)]
for i in range(N-1):
    a, b, c, d = map(int, readline().split())
    G[a-1].append((b-1, c, d))
    G[b-1].append((a-1, c, d))

D0 = defaultdict(list)
D1 = defaultdict(list)
ans = [0]*Q
X = [0]*Q
Y = [0]*Q
ES = []
for i in range(Q):
    x, y, u, v = map(int, readline().split())
    D0[u-1].append(i)
    D0[v-1].append(i)
    X[i] = x
    Y[i] = y
    ES.append((i, u-1, v-1))

U = [0]*N
P = [0]*N
depth = [0]*N
P[0] = -1
U[0] = 1
que = deque([0])
while que:
    v = que.popleft()
    d0 = depth[v] + 1
    for w, c, d in G[v]:
        if U[w]:
            continue
        U[w] = 1
        G0[v].append((w, c, d))
        P[w] = v
        que.append(w)
        depth[w] = d0

H = [0]*N
prv = [None]*N
def dfs(v):
    s = 1; heavy = None; m = 0
    for w, _, _ in G0[v]:
        prv[w] = v
        c = dfs(w)
        if m < c:
            heavy = w
            m = c
        s += c
    H[v] = heavy
    return s
dfs(0)

SS = []
D = []
L = [0]*N
I = [0]*N
que = deque([(0, 0)])
while que:
    v, d = que.popleft()
    S = []
    k = len(SS)
    while v is not None:
        I[v] = len(S)
        S.append(v)
        L[v] = k
        h = H[v]
        for w, _, _ in G0[v]:
            if h == w:
                continue
            que.append((w, d+1))
        v = h
    SS.append(S)
    D.append(d)

def query(u, v):
    lu = L[u]; lv = L[v]
    dd = D[lv] - D[lu]
    if dd < 0:
        lu, lv = lv, lu
        v, u = u, v
        dd = -dd

    assert D[lu] <= D[lv], (D[lu], D[lv], dd)


    for _ in range(dd):
        v = prv[SS[lv][0]]
        lv = L[v]

    assert D[lu] == D[lv]
    while lu != lv:
        u = prv[SS[lu][0]]
        lu = L[u]

        v = prv[SS[lv][0]]
        lv = L[v]
    return u if I[u] < I[v] else v


for i, u, v in ES:
    w = query(u, v)
    D1[w].append(i)

C = [0]*(N+1)
E = [0]*(N+1)
DD = [0]*Q
def dfs(v, d0):
    for i in D0[v]:
        x = X[i]; y = Y[i]
        DD[i] += d0 - E[x] + C[x]*y
    for i in D1[v]:
        x = X[i]; y = Y[i]
        DD[i] -= 2*(d0 - E[x] + C[x]*y)
    for w, c, d in G0[v]:
        C[c] += 1; E[c] += d
        dfs(w, d0 + d)
        C[c] -= 1; E[c] -= d
dfs(0, 0)
for i in range(Q):
    write("%d\n" % DD[i])

Submission status: Time Limit Exceeded

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

# LCAの計算 (generatorで最小値を求める)
from collections import defaultdict


def _query(a, b):
    yield INF
    a += m0
    b += m0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b - 1]
        if a & 1:
            yield data[a - 1]
            a += 1
        a >>= 1
        b >>= 1


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


import sys

sys.setrecursionlimit(10 ** 5 + 5)

n, q = list(map(int, input().split()))
links = [{} for _ in range(n)]
lines = sys.stdin.readlines()
for line in lines[:n - 1]:
    a, b, c, d = list(map(int, line.split()))
    a -= 1
    b -= 1
    links[a][b] = (c, d)
    links[b][a] = (c, d)
queries = []
v_queries = [{} for _ in range(n)]
for line in lines[n - 1:]:
    x, y, u, v = map(int, line.split())
    u -= 1
    v -= 1
    queries.append((x, y, u, v))
    v_queries[u][x] = [0, 0]
    v_queries[v][x] = [0, 0]

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

# Euler Tour の構築
euler_tour = []
first_appear = [0] * n
depth = [0] * n
parents = [0] * n


def dfs(v, p, dep, tmp_dist, total_dist):
    first_appear[v] = len(euler_tour)
    depth[v] = dep
    euler_tour.append(v)
    parents[v] = p
    for x, arr in v_queries[v].items():
        arr[0] = total_dist - tmp_dist[x][0]
        arr[1] = tmp_dist[x][1]
    for u, (uc, ud) in links[v].items():
        if u == p:
            continue
        tmp_dist[uc][0] += ud
        tmp_dist[uc][1] += 1
        dfs(u, v, dep + 1, tmp_dist, total_dist + ud)
        tmp_dist[uc][0] -= ud
        tmp_dist[uc][1] -= 1
        euler_tour.append(v)


def dfs2(v, x, y, dist, cnt):
    if v == 0:
        return dist, cnt
    p = parents[v]
    c, d = links[v][p]
    if x == c:
        cnt += 1
    else:
        dist += d
    return dfs2(p, x, y, dist, cnt)


tmp_dist = defaultdict(lambda: [0, 0])
dfs(0, -1, 0, tmp_dist, 0)
# print(euler_tour)
# print(first_appear)
# print(depth)
# print(v_queries)
# print(parents)

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

# print(data)

ans = []
for x, y, u, v in queries:
    w = query(u, v)
    # print(u, v, w)
    qu = v_queries[u][x]
    qv = v_queries[v][x]
    du = qu[0] + qu[1] * y
    dv = qv[0] + qv[1] * y
    if w == 0:
        ans.append(du + dv)
        continue
    qw = v_queries[w]
    if x in qw:
        qw = qw[x]
        dw = qw[0] + qw[1] * y
    else:
        dist, cnt = dfs2(w, x, y, 0, 0)
        qw[x] = [dist, cnt]
        dw = dist + cnt * y
    ans.append(du + dv - 2 * dw)

print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

queue = deque()
queue.append(1)
height = [0] * (N+1)
height[1] = 1
cdp = [0] * (N+1)
cdp[1] = [0, 0, 0]
while queue:
    v = queue.popleft()
    for child in adj[v]:
        if height[child[0]] == 0:
            idx = child[0]
            queue.append(idx)
            height[idx] = height[v] + 1
            cdp[idx] = [child[1], child[2], v]

for q in range(Q):
    x, y, u, v = map(int, input().split())
    ans = 0
    h_u = height[u]
    h_v = height[v]
    while h_u != h_v:
        if h_u < h_v:
            cdp_v = cdp[v]
            if cdp_v[0] == x:
                ans += y
            else:
                ans += cdp_v[1]
            v = cdp_v[2]
            h_v -= 1
        else:
            cdp_u = cdp[u]
            if cdp_u[0] == x:
                ans += y
            else:
                ans += cdp_u[1]
            u = cdp_u[2]
            h_u -= 1
    while u != v:
        cdp_v = cdp[v]
        if cdp_v[0] == x:
            ans += y
        else:
            ans += cdp_v[1]
        v = cdp_v[2]
        cdp_u = cdp[u]
        if cdp_u[0] == x:
            ans += y
        else:
            ans += cdp_u[1]
        u = cdp_u[2]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

queue = deque()
queue.append(1)
height = [0] * (N+1)
height[1] = 1
cdp = [0] * (N+1)
cdp[1] = [0, 0, 0]
while queue:
    v = queue.popleft()
    for child in adj[v]:
        if height[child[0]] == 0:
            idx = child[0]
            queue.append(idx)
            height[idx] = height[v] + 1
            cdp[idx] = [child[1], child[2], v]

for q in range(Q):
    x, y, u, v = map(int, input().split())
    ans = 0
    h_u = height[u]
    h_v = height[v]
    while h_u != h_v:
        if h_u < h_v:
            if cdp[v][0] == x:
                ans += y
            else:
                ans += cdp[v][1]
            v = cdp[v][2]
            h_v -= 1
        else:
            if cdp[u][0] == x:
                ans += y
            else:
                ans += cdp[u][1]
            u = cdp[u][2]
            h_u -= 1
    while u != v:
        if cdp[v][0] == x:
            ans += y
        else:
            ans += cdp[v][1]
        v = cdp[v][2]
        if cdp[u][0] == x:
            ans += y
        else:
            ans += cdp[u][1]
        u = cdp[u][2]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, defaultdict

def default_dist(N, c, d):
    res = [(0, 0) for _ in range(N-1)]
    res[c] = (1, d)
    return res

def dist_add(A, B):
    res = [(a[0]+b[0], a[1]+b[1]) for a, b in zip(A, B)]
    return res


def solve(N: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]", x: "List[int]", y: "List[int]", u: "List[int]", v: "List[int]"):
    adj = defaultdict(list)
    dist = dict()
    for aa, bb, cc, dd in zip(a, b, c, d):
        adj[aa].append((bb, cc, dd))
        adj[bb].append((aa, cc, dd))
        dist[frozenset([aa, bb])] = default_dist(N, cc, dd)

    for xx, yy, uu, vv in zip(x, y, u, v):
        if frozenset([uu, vv]) not in dist:
            deq = deque([uu])
            visited = [False for _ in range(N)]
            visited[uu] = True
            while len(deq) > 0:
                node = deq.popleft()
                for next_node, next_color, next_dist in adj[node]:
                    if visited[next_node]:
                        continue
                    if frozenset([uu, next_node]) not in dist:
                        dist[frozenset([uu, next_node])] = dist_add(dist[frozenset([uu, node])], default_dist(N, next_color, next_dist))
                    deq.append(next_node)
                    visited[next_node] = True

        res = 0
        for color, pair in enumerate(dist[frozenset([uu, vv])]):
            num, dd = pair
            if color == xx:
                res += num * yy
            else:
                res += dd
        print(res)




# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    c = [int()] * (N-1)  # type: "List[int]" 
    d = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))-1
        b[i] = int(next(tokens))-1
        c[i] = int(next(tokens))-1
        d[i] = int(next(tokens))
    x = [int()] * (Q)  # type: "List[int]" 
    y = [int()] * (Q)  # type: "List[int]" 
    u = [int()] * (Q)  # type: "List[int]" 
    v = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        x[i] = int(next(tokens))-1
        y[i] = int(next(tokens))
        u[i] = int(next(tokens))-1
        v[i] = int(next(tokens))-1
    solve(N, Q, a, b, c, d, x, y, u, v)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
from collections import defaultdict
edge=defaultdict(set)
for i in range(n-1):
    a,b,c,d=map(int,input().split())
    a-=1
    b-=1
    c-=1
    edge[a]|={(b,c,d)}
    edge[b]|={(a,c,d)}
infl=10**17
dist=[infl]*n
color=[[0]*(n-1) for i in range(n)]
ccnt=[[0]*(n-1) for i in range(n)]
bef=[-1]*n
check={0}
dist[0]=0
while len(check)>0:
    now=check.pop()
    for p in edge[now]:
        nex=p[0]
        if dist[nex]!=infl:continue
        ce=p[1]
        cd=p[2]
        if now==0:bef[nex]=nex
        else:bef[nex]=bef[now]
        color[nex]=color[now].copy()
        ccnt[nex]=ccnt[now].copy()
        color[nex][ce]+=cd
        ccnt[nex][ce]+=1
        dist[nex]=dist[now]+cd
        check|={nex}
for i in range(q):
    x,y,u,v=map(int,input().split())
    x-=1
    u-=1
    v-=1
    if u==0:
        print(dist[v]-color[v][x]+y*ccnt[v][x])
    elif bef[u]==bef[v]:
        print(abs(dist[u]-dist[v])-abs(color[u][x]-color[v][x])+y*abs(ccnt[u][x]-ccnt[v][x]))
    else:
        print(dist[u]+dist[v]-color[u][x]-color[v][x]+y*(ccnt[u][x]+ccnt[v][x]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write
sys.setrecursionlimit(10**6)
N, Q = map(int, readline().split())
G = [[] for i in range(N)]
G0 = [[] for i in range(N)]
for i in range(N-1):
    a, b, c, d = map(int, readline().split())
    G[a-1].append((b-1, c, d))
    G[b-1].append((a-1, c, d))

D0 = defaultdict(list)
D1 = defaultdict(list)
ans = [0]*Q
X = [0]*Q
Y = [0]*Q
ES = []
for i in range(Q):
    x, y, u, v = map(int, readline().split())
    D0[u-1].append(i)
    D0[v-1].append(i)
    X[i] = x
    Y[i] = y
    ES.append((i, u-1, v-1))

U = [0]*N
P = [0]*N
depth = [0]*N
P[0] = -1
U[0] = 1
que = deque([0])
while que:
    v = que.popleft()
    d0 = depth[v] + 1
    for w, c, d in G[v]:
        if U[w]:
            continue
        U[w] = 1
        G0[v].append((w, c, d))
        P[w] = v
        que.append(w)
        depth[w] = d0

LV = (N-1).bit_length()
def construct(prv):
    kprv = [prv]
    S = prv
    for k in range(LV):
        T = [0]*N
        for i in range(N):
            if S[i] is None:
                continue
            T[i] = S[S[i]]
        kprv.append(T)
        S = T
    return kprv

kprv = construct(P)

def lca(u, v, kprv=kprv, depth=depth):
    dd = depth[v] - depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd

    # assert depth[u] <= depth[v]
    for k in range(LV+1):
        if dd & 1:
            v = kprv[k][v]
        dd >>= 1

    # assert depth[u] == depth[v]
    if u == v:
        return u

    for k in range(LV-1, -1, -1):
        pu = kprv[k][u]; pv = kprv[k][v]
        if pu != pv:
            u = pu; v = pv

    # assert kprv[0][u] == kprv[0][v]
    return kprv[0][u]

for i, u, v in ES:
    w = lca(u, v)
    D1[w].append(i)

C = [0]*(N+1)
E = [0]*(N+1)
DD = [0]*Q
def dfs(v, d0):
    for i in D0[v]:
        x = X[i]; y = Y[i]
        t = d0 - E[x] + C[x]*y
        DD[i] += t
    for i in D1[v]:
        x = X[i]; y = Y[i]
        t = d0 - E[x] + C[x]*y
        DD[i] -= 2*t
    for w, c, d in G0[v]:
        C[c] += 1
        E[c] += d
        dfs(w, d0 + d)
        C[c] -= 1
        E[c] -= d
dfs(0, 0)
for i in range(Q):
    write("%d\n" % DD[i])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())

from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]




c=[[] for i in range(n)]
for i in range(n-1):
    tmp=[int(j) for j in input().split()]
    c[tmp[2]].append((tmp[0],tmp[1],tmp[3]))

for i in range(q):
    tmp=[int(j) for j in input().split()]
    x,y,u,v=tmp[0],tmp[1],tmp[2],tmp[3]
    g = Graph()
    for i in range(n):
        if i==x:
            for src, dst, weight in c[i]:
                g.add_edge(src, dst, y)
                g.add_edge(dst, src, y)
        else:
            for src, dst, weight in c[i]:
                g.add_edge(src, dst, weight)
                g.add_edge(dst, src, weight)
    d = Dijkstra(g, u)   
    print(d.shortest_distance(v))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100005)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, q = na()
g = [[] for _ in range(n)]
es = []
for i in range(n-1):
    a, b, c, d = na()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    es.append((c, d, a, b))
es.sort()

qs = []
for i in range(q):
    x, y, u, v = na()
    qs.append((x, y, u-1, v-1, i))
qs.sort()

def addfenwick(ft, i, v):
    if v == 0 or i < 0: return
    i += 1
    while i < len(ft):
        ft[i] += v
        i += i&-i

def sumfenwick(ft, i):
    s = 0
    i += 1
    while i > 0:
        s += ft[i]
        i -= i&-i
    return s

ord = []
right = [0] * n
par = [-1] * n
dep = [0] * n

def dfs(cur, pre, g):
    global ord, right, par, dep
    ord.append(cur)
    for e in g[cur]:
        if e == pre: continue
        dep[e] = dep[cur] + 1
        dfs(e, cur, g)
        par[e] = cur
    right[cur] = len(ord)

dfs(0, -1, g)


def ntz(m):
    assert m != 0
    ret = 0
    while m&1^1:
        ret += 1
        m >>= 1
    return ret

def lca(a, b, spar, dep):
    if dep[a] < dep[b]:
        b = anc(b, dep[b] - dep[a], spar)
    else:
        a = anc(a, dep[a] - dep[b], spar)

    if a == b:
        return a

    for d in range(len(spar)-1, -1, -1):
        if spar[d][a] == -1: continue
        if spar[d][a] != spar[d][b]:
            a = spar[d][a]
            b = spar[d][b]
    return spar[0][a]

def anc(a, m, spar):
    for x in range(17):
        if m>>x&1:
            a = spar[x][a]
    return a

def lsp(par):
    o = len(par)
    m = 17
    pars = [[0]*o for _ in range(m)]
    pars[0] = par
    for j in range(1, m):
        for i in range(n):
            pars[j][i] = -1 if pars[j-1][i] == -1 else pars[j-1][pars[j-1][i]]
    return pars

ft = [0] * (n+5)
ftc = [0] * (n+5)

pw = [0] * n
for e in es:
    if par[e[2]] == e[3]:
        pw[e[2]] = e[1]
    else:
        pw[e[3]] = e[1]

iord = [0] * n
for i in range(n):
    iord[ord[i]] = i

for i in range(1, n):
    addfenwick(ft, iord[i], pw[i])
    addfenwick(ft, right[i], -pw[i])

anss = [0] * q

spar = lsp(par)
i = 0
p = 0
while i < q:
    j = i
    while j < q and qs[j][0] == qs[i][0]:
        j += 1

    while p < n-1 and es[p][0] < qs[i][0]:
        p += 1
    r = p
    while r < n-1 and es[r][0] <= qs[i][0]:
        x = es[r][2]
        y = es[r][3]
        z = x if par[x] == y else y
        addfenwick(ft, iord[z], -pw[z])
        addfenwick(ft, right[z], pw[z])
        addfenwick(ftc, iord[z], 1)
        addfenwick(ftc, right[z], -1)
        r += 1

    for u in range(i, j):
        lc = lca(qs[u][2], qs[u][3], spar, dep)
        c0 = sumfenwick(ft, iord[qs[u][2]]) + sumfenwick(ft, iord[qs[u][3]]) - 2*sumfenwick(ft, iord[lc])
        c1 = sumfenwick(ftc, iord[qs[u][2]]) + sumfenwick(ftc, iord[qs[u][3]]) - 2*sumfenwick(ftc, iord[lc])
        anss[qs[u][4]] = c0 + c1 * qs[u][1]

    r = p
    while r < n-1 and es[r][0] <= qs[i][0]:
        x = es[r][2]
        y = es[r][3]
        z = x if par[x] == y else y
        addfenwick(ft, iord[z], pw[z])
        addfenwick(ft, right[z], -pw[z])
        addfenwick(ftc, iord[z], -1)
        addfenwick(ftc, right[z], 1)
        r += 1

    i = j

for v in anss:
    print(v)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100005)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, q = na()
g = [[] for _ in range(n)]
es = []
for i in range(n-1):
    a, b, c, d = na()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    es.append((c, d, a, b))
es.sort()

qs = []
for i in range(q):
    x, y, u, v = na()
    qs.append((x, y, u-1, v-1, i))
qs.sort()

def addfenwick(ft, i, v):
    if v == 0 or i < 0: return
    i += 1
    while i < len(ft):
        ft[i] += v
        i += i&-i

def sumfenwick(ft, i):
    s = 0
    i += 1
    while i > 0:
        s += ft[i]
        i -= i&-i
    return s

ord = []
right = [0] * n
par = [-1] * n
dep = [0] * n

def dfs(cur, pre, g):
    global ord, right, par, dep
    ord.append(cur)
    for e in g[cur]:
        if e == pre: continue
        dep[e] = dep[cur] + 1
        dfs(e, cur, g)
        par[e] = cur
    right[cur] = len(ord)

dfs(0, -1, g)


def ntz(m):
    ret = 0
    while m&1^1:
        ret += 1
        m >>= 1
    return ret

def lca(a, b, spar, dep):
    if dep[a] < dep[b]:
        b = anc(b, dep[b] - dep[a], spar)
    else:
        a = anc(a, dep[a] - dep[b], spar)

    if a == b:
        return a

    for d in range(len(spar)-1, -1, -1):
        if spar[d][a] == -1: continue
        if spar[d][a] != spar[d][b]:
            a = spar[d][a]
            b = spar[d][b]
    return spar[0][a]

def anc(a, m, spar):
    while m > 0 and a != -1:
        a = spar[ntz(m)][a]
        m &= m-1
    return a

def lsp(par):
    n = len(par)
    m = 17
    pars = [[0]*n for _ in range(m)]
    pars[0] = par
    for j in range(1, m):
        for i in range(n):
            pars[j][i] = -1 if pars[j-1][i] == -1 else pars[j-1][pars[j-1][i]]
    return pars

ft = [0] * (n+5)
ftc = [0] * (n+5)

pw = [0] * n
for e in es:
    if par[e[2]] == e[3]:
        pw[e[2]] = e[1]
    else:
        pw[e[3]] = e[1]

iord = [0] * n
for i in range(n):
    iord[ord[i]] = i

for i in range(1, n):
    addfenwick(ft, iord[i], pw[i])
    addfenwick(ft, right[i], -pw[i])

anss = [0] * q

spar = lsp(par)
i = 0
p = 0
while i < q:
    j = i
    while j < q and qs[j][0] == qs[i][0]:
        j += 1

    while p < n-1 and es[p][0] < qs[i][0]:
        p += 1
    r = p
    while r < n-1 and es[r][0] <= qs[i][0]:
        x = es[r][2]
        y = es[r][3]
        z = x if par[x] == y else y
        addfenwick(ft, iord[z], -pw[z])
        addfenwick(ft, right[z], pw[z])
        addfenwick(ftc, iord[z], 1)
        addfenwick(ftc, right[z], -1)
        r += 1

    for u in range(i, j):
        lc = lca(qs[u][2], qs[u][3], spar, dep)
        c0 = sumfenwick(ft, iord[qs[u][2]]) + sumfenwick(ft, iord[qs[u][3]]) - 2*sumfenwick(ft, iord[lc])
        c1 = sumfenwick(ftc, iord[qs[u][2]]) + sumfenwick(ftc, iord[qs[u][3]]) - 2*sumfenwick(ftc, iord[lc])
        anss[qs[u][4]] = c0 + c1 * qs[u][1]

    r = p
    while r < n-1 and es[r][0] <= qs[i][0]:
        x = es[r][2]
        y = es[r][3]
        z = x if par[x] == y else y
        addfenwick(ft, iord[z], pw[z])
        addfenwick(ft, right[z], -pw[z])
        addfenwick(ftc, iord[z], -1)
        addfenwick(ftc, right[z], 1)
        r += 1

    i = j

for v in anss:
    print(v)

Submission status: Memory Limit Exceeded

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

def bfs():
    q = deque([1])
    while q:
        now = q.popleft()
        for nex,c,w in e[now]:
            if depth[nex]>= 0:
                continue
            depth[nex] = depth[now]+1
            dis[nex] = dis[now]+w
            lca[0][nex] = now
            q.append(nex)

def dfs1(now,p,count1,count2):
    for cou in dcount[now]:
        dcount[now][cou] = count1[cou]
    for wei in dweight[now]:
        dweight[now][wei] = count2[wei]

    for nex,c,w in e[now]:
        if nex == p:
            continue
        count1[c] += 1
        count2[c] += w
        dfs1(nex,now,count1,count2)
        count1[c] -= 1
        count2[c] -= w
n,q = map(int,input().split())
e = [[] for i in range(n+1)]

for i in range(n-1):
    a,b,c,d = map(int,input().split())
    e[a].append((b,c,d))
    e[b].append((a,c,d))
size = n+1
bitlen = 19
lca = [[0]*size for i in range(bitlen)]
depth = [-1]*size
dis = [-1]*size
depth[1] = 0
dis[1] = 0

bfs()
for i in range(1,bitlen):
    for j in range(1,size):
        if lca[i-1][j] > 0:
            lca[i][j] = lca[i-1][lca[i-1][j]]
    
def search(x,y):
    dx = depth[x]
    dy = depth[y]
    if dx < dy:
        x,y = y,x
        dx,dy = dy,dx
    dif = dx-dy
    while dif:
        s = dif & (-dif)
        x = lca[s.bit_length()-1][x]
        dif -= s
    if x == y:
        return x
    for i in range(bitlen-1,-1,-1):
        if lca[i][x] != lca[i][y]:
            x = lca[i][x]
            y = lca[i][y]
    return lca[0][x]


Q = [[] for i in range(n+1)]
ans = []
for i in range(q):
    x,y,u,v = map(int,input().split())
    a = search(u,v)
    ans.append(dis[u]+dis[v]-2*dis[a])
    Q[u].append((x,y,i,1))
    Q[v].append((x,y,i,1))
    Q[a].append((x,y,i,-2))


count = [0]*n
weight = [0]*n

def dfs1(now,p):
    for x,y,ind,z in Q[now]:
        ans[ind] += z*(y*count[x]-weight[x])
    for nex,c,w in e[now]:
        if nex == p:
            continue
        count[c] += 1
        weight[c] += w
        dfs1(nex,now)
        count[c] -= 1
        weight[c] -= w
    
dfs1(1,0)

for i in ans:
    print(i)