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: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

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

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))

class Graph(DGraph):
    def __init__(self, n, edges):
        nd_edges = edges + [(d, s, c) for s, d, c in edges]
        super().__init__(n, nd_edges)

    def transpose(self):
        return self

def dfs(g, src):
    visited = [False] * len(g)
    stack = [(src, (0, -1, {}))]
    while stack:
        n, (c, p, acc) = stack.pop()
        if visited[n]:
            continue
        visited[n] = True

        for _, d, (dd, cc) in g.edges(n):
            _acc = dict(acc)
            if cc not in _acc:
                _acc[cc] = (0, 0)
            _acc[cc] = (_acc[cc][0] + 1, _acc[cc][1] + dd)
            stack.append((d, (c + 1, n, _acc)))
        yield n, c, p, acc


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]"):
    es = []
    for _a, _b, _c, _d in zip(a, b, c, d):
        es.append((_a - 1, _b - 1, (_d, _c)))

    h = int(ceil(log2(N)))
    g = Graph(N, es)
    ds = [-1] * N
    ps = [[-1] * h for _ in range(N)]
    accs = [{}] * N
    for i, d, p, acc in dfs(g, 0):
        ds[i] = d
        ps[i][0] = p
        accs[i] = acc

    for i in range(N):
        for j in range(h - 1):
            ps[i][j + 1] = ps[ps[i][j]][j]


    ret = []
    for _x, _y, _u, _v in zip(x, y, u, v):
        uu = _u - 1
        vv = _v - 1
        while ds[uu] < ds[vv]:
            vv = ps[vv][0]
        while ds[uu] < ds[vv]:
            uu = ps[uu][0]
        if uu == vv:
            lca = uu
        else:
            for i in range(h-1, 0, -1):
                if ps[uu][i] != ps[vv][i]:
                    uu = ps[uu][i]
                    vv = ps[vv][i]
            lca = ps[uu][0]

        du = sum([ddd for _, ddd in accs[_u - 1].values()])
        if _x in accs[_u - 1]:
            du += _y * accs[_u - 1][_x][0] - accs[_u - 1][_x][1]
        dv = sum([ddd for _, ddd in accs[_v - 1].values()])
        if _x in accs[_v - 1]:
            dv += _y * accs[_v - 1][_x][0] - accs[_v - 1][_x][1]
        dlca = sum([ddd for _, ddd in accs[lca].values()])
        if _x in accs[lca]:
            dlca += _y * accs[lca][_x][0] - accs[lca][_x][1]
        dist = du + dv - 2 * dlca
        ret.append(dist)
    return ret


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))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        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))
        y[i] = int(next(tokens))
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    result = solve(N, Q, a, b, c, d, x, y, u, v)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

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

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))

class Graph(DGraph):
    def __init__(self, n, edges):
        nd_edges = edges + [(d, s, c) for s, d, c in edges]
        super().__init__(n, nd_edges)

    def transpose(self):
        return self

def dfs(g, src):
    visited = [False] * len(g)
    stack = [(src, (0, -1, {}))]
    while stack:
        n, (c, p, acc) = stack.pop()
        if visited[n]:
            continue
        visited[n] = True

        for _, d, (dd, cc) in g.edges(n):
            _acc = dict(acc)
            if cc not in _acc:
                _acc[cc] = (0, 0)
            _acc[cc] = (_acc[cc][0] + 1, _acc[cc][1] + dd)
            stack.append((d, (c + 1, n, _acc)))
        yield n, c, p, acc


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]"):
    es = []
    for _a, _b, _c, _d in zip(a, b, c, d):
        es.append((_a - 1, _b - 1, (_d, _c)))

    h = int(ceil(log2(N)))
    g = Graph(N, es)
    ds = [-1] * N
    ps = [[-1] * h for _ in range(N)]
    accs = [{}] * N
    for i, d, p, acc in dfs(g, 0):
        ds[i] = d
        ps[i][0] = p
        accs[i] = acc

    for i in range(N):
        for j in range(h - 1):
            ps[i][j + 1] = ps[ps[i][j]][j]


    ret = []
    for _x, _y, _u, _v in zip(x, y, u, v):
        uu = _u - 1
        vv = _v - 1
        while ds[uu] < ds[vv]:
            vv = ps[vv][0]
        while ds[uu] < ds[vv]:
            uu = ps[uu][0]
        if uu == vv:
            lca = uu
        else:
            for i in range(h-1, 0, -1):
                if ps[uu][i] != ps[vv][i]:
                    uu = ps[uu][i]
                    vv = ps[vv][i]
            uu = ps[uu][0]
            vv = ps[vv][0]
            lca = uu

        du = sum([ddd for _, ddd in accs[_u - 1].values()])
        if _x in accs[_u - 1]:
            du += _y * accs[_u - 1][_x][0] - accs[_u - 1][_x][1]
        dv = sum([ddd for _, ddd in accs[_v - 1].values()])
        if _x in accs[_v - 1]:
            dv += _y * accs[_v - 1][_x][0] - accs[_v - 1][_x][1]
        dlca = sum([ddd for _, ddd in accs[lca].values()])
        if _x in accs[lca]:
            dv += _y * accs[lca][_x][0] - accs[lca][_x][1]
        dist = du + dv - 2 * dlca
        ret.append(dist)
    return ret


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))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        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))
        y[i] = int(next(tokens))
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    result = solve(N, Q, a, b, c, d, x, y, u, v)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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

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

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

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

Submission status: Wrong Answer

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


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

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

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

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

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

Submission status: Wrong Answer

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


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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

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

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

class LCA:

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque
N,Q=map(int,input().split())
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
c=[0 for i in range(N-1)]
d=[0 for i in range(N-1)]
x=[0 for i in range(Q)]
y=[0 for i in range(Q)]
u=[0 for i in range(Q)]
v=[0 for i in range(Q)]
G=[dict() for i in range(N)]
H=[dict() for i in range(N)]
for i in range(N-1):
    a[i],b[i],c[i],d[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
    G[a[i]][b[i]]=d[i]
    G[b[i]][a[i]]=d[i]
    H[a[i]][b[i]]=c[i]
    H[b[i]][a[i]]=c[i]
for i in range(Q):
    x[i],y[i],u[i],v[i]=map(int,input().split())
    u[i]-=1;v[i]-=1
parents=[-1 for i in range(N)]
reached=[0 for i in range(N)]
dist=[0 for i in range(N)]
rnk=[0 for i in range(N)]
q=deque([0])
while(len(q)>0):
    r=q.popleft()
    reached[r]=1
    for p in G[r]:
        if reached[p]==1:
            continue
        parents[p]=r
        rnk[p]=rnk[r]+1
        dist[p]=dist[r]+G[r][p]
        q.appendleft(p)
#print(parents)
M=len(bin(N))-2
parents2i=[[-1 for j in range(N)] for i in range(M)]
for i in range(N):
    parents2i[0][i]=parents[i]
for i in range(1,M):
    for j in range(N):
        if parents2i[i-1][j]==-1:
            parents2i[i][j]=-1
        else:
            parents2i[i][j]=parents2i[i-1][parents2i[i-1][j]]
def kyotusosen(a1,a2):
    b1=a1;b2=a2
    if rnk[b1]>rnk[b2]:
        b1,b2=b2,b1
    #rnk[b1]<rnk[b2]
    tmp=rnk[b2]-rnk[b1]
    tmp2=0
    while(tmp>0):
        if tmp%2==1:
            b2=parents2i[tmp2][b2]
        tmp=tmp//2
        tmp2+=1
    while(b1!=b2):
        #print(a1,a2,b1,b2)
        index=0
        for i in range(M):
            if parents2i[i][b1]!=parents2i[i][b2]:
                index=i
            else:
                break
        b1=parents2i[index][b1]
        b2=parents2i[index][b2]
    return b1

#print(kyotusosen(0,3))
for j in range(Q):
    k=kyotusosen(u[j],v[j])
    print(dist[u[j]]+dist[v[j]]-dist[k])

Submission status: Wrong Answer

Solution code:
def par(pmap, parent):
    from math import log2
    m = int(log2(len(pmap)))
    nextp = parent
    ans = [parent]
    for i in range(m):
        if nextp == 0:
            ans.append(0)
            continue
        nextp = pmap[nextp][i]
        ans.append(nextp)
    return ans

def make_dmap(tree):
    from queue import LifoQueue
    from copy import deepcopy
    lifo = LifoQueue()
    lifo.put((0,0,0,[0 for i in range(len(tree))],[0 for i in range(len(tree))],0))
    ans = [0 for i in range(len(tree))]
    while not lifo.empty():
        parent,e,depth,c,d,odis = lifo.get()
        ans[e] = [depth,c,d,odis]
        for i in tree[e]:
            if i[0] is parent:
                continue
            ctmp = deepcopy(c)
            dtmp = deepcopy(d)
            ctmp[i[1]] += 1
            dtmp[i[1]] += i[2]
            
            lifo.put((e,i[0],depth+1,ctmp,dtmp,odis+i[2]))
    return ans


def dfs(tree):
    from queue import LifoQueue
    lifo = LifoQueue()
    lifo.put((0,0))
    ans = [0 for i in range(len(tree))]
    while not lifo.empty():
        parent,e = lifo.get()
        ans[e] = par(ans,parent)
        for i in tree[e]:
            if i[0] is parent:
                continue
            lifo.put((e,i[0]))
    return ans

def find_LCA(pmap,dmap,a,b):
    from math import log2

    ddif = abs(dmap[a][0] - dmap[b][0])
    two = []
    while ddif is not 0:
        two.append(ddif%2)
        ddif //= 2
    lentwo = len(two)
    if dmap[a][0] > dmap[b][0]:
        for i in range(lentwo):
            lentwo -= 1
            if two[lentwo]:
                a = pmap[a][lentwo]
    else:
        for i in range(lentwo):
            lentwo -= 1
            if two[lentwo]:
                b = pmap[b][lentwo]
    if a == b:
        return a

    m = int(log2(len(pmap)))
    for i in range(m+1):
        if pmap[a][m-i] != pmap[b][m-i]:
            a = pmap[a][m-i]
            b = pmap[b][m-i]
    return pmap[a][0]



def main():
    bign = 10**9+7
    n,q = map(int,input().split())

    cdtree = []
    tree = [[] for i in range(n)]
    for i in range(n-1):
        u,v,c,d = map(int,input().split())
        u -= 1
        v -= 1
        tree[u].append([v,c,d])
        tree[v].append([u,c,d])

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


    pmap = dfs(tree)
    dmap = make_dmap(tree)
    for q in qs:
    	print(1)

    dismap = []
"""
    for q in qs:
        x,y,u,v = q
        lca = find_LCA(pmap,dmap,u,v)
        odis = dmap[u][3] + dmap[v][3] - 2 * dmap[lca][3]
        odis += (dmap[u][1][x] + dmap[v][1][x] - 2 * dmap[lca][1][x]) * y - (dmap[u][2][x] + dmap[v][2][x] - 2 * dmap[lca][2][x])
        print(odis)
"""

main()

Submission status: Wrong Answer

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

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

path = [[] for _ in range(N)]

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

# doublingに必要なKを求める
for K in range(18) :
    if 2 ** K >= N :
        break

# dfs
parent = [[-1] * N for _ in range(K)]
rank = [-1 for _ in range(N)]

rank[0] = 0
queue = [0]

while queue :
    cur = queue.pop()
    for nex, _, _ in path[cur] :
        if rank[nex] < 0 :
            queue.append(nex)
            parent[0][nex] = cur
            rank[nex] = rank[cur] + 1

# doubling        
for i in range(1, K) :
    for j in range(N) :
        if parent[i-1][j] > 0 :
            parent[i][j] = parent[i-1][parent[i-1][j]]

# lca
def lca(a, b) :
    if rank[a] > rank[b] :
        a, b = b, a

    diff = rank[b] - rank[a]
    i = 0
    while diff > 0 :
        if diff & 1 :
            b = parent[i][b]
        diff >>= 1
        i += 1
        
    if a == b :
        return a

    for i in range(K-1, -1, -1) :
        if parent[i][a] != parent[i][b] :
            a = parent[i][a]
            b = parent[i][b]

    return parent[0][a]

# Queryの先読み
schedule = [[] for _ in range(N)]
for i in range(Q) : 
    x, y, u, v = map(int, input().split())
    x, u, v = x-1, u-1, v-1
    l = lca(u, v)
    schedule[u].append((i, 1, x, y))
    schedule[v].append((i, 1, x, y))
    schedule[l].append((i, -1, x, y))

ret = [0] * Q
C = [0] * (N-1)
D = [0] * (N-1)

def dfs(cur, pre, tot) :
    for i, t, c, d in schedule[cur] :
        ret[i] += t * (tot - D[c] + C[c] * d)
    
    for nex, c, d in path[cur] :
        if nex == pre :
            continue
        C[c] += 1
        D[c] += d
        dfs(nex, cur, tot + d)
        C[c] -= 1
        D[c] -= d

dfs(0, -1, 0)
   
for i in range(Q) :
    print(ret[i])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**5)

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

path = [[] for _ in range(N)]

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

# doublingに必要なKを求める
for K in range(18) :
    if 2 ** K >= N :
        break

# bfs
parent = [[-1] * N for _ in range(K)]
rank = [-1 for _ in range(N)]
dist = [0 for _ in range(N)]

rank[0] = 0
queue = deque([0])

while queue :
    cur = queue.popleft()
    for nex, _, d in path[cur] :
        if rank[nex] < 0 :
            queue.append(nex)
            parent[0][nex] = cur
            rank[nex] = rank[cur] + 1
            dist[nex] = dist[cur] + d

# doubling        
for i in range(1, K) :
    for j in range(N) :
        if parent[i-1][j] > 0 :
            parent[i][j] = parent[i-1][parent[i-1][j]]

# lca
def lca(a, b) :
    if rank[a] > rank[b] :
        a, b = b, a

    diff = rank[b] - rank[a]
    i = 0
    while diff > 0 :
        if diff & 1 :
            b = parent[i][b]
        diff >>= 1
        i += 1
        
    if a == b :
        return a

    for i in range(K-1, -1, -1) :
        if parent[i][a] != parent[i][b] :
            a = parent[i][a]
            b = parent[i][b]

    return parent[0][a]

# Queryの先読み
xyuv = []
colors = [[] for _ in range(N)]
for _ in range(Q) : 
    x, y, u, v = map(int, input().split())
    x, u, v = x-1, u-1, v-1
    xyuv.append([x, y, u, v])
    colors[u].append(x)
    colors[v].append(x)
    colors[lca(u, v)].append(x)

for i in range(N) :
    colors[i] = list(set(colors[i]))

mem = dict()
C = [0] * (N-1)
D = [0] * (N-1)

def dfs(cur, pre) :
    print(cur, C, D)
    for color in colors[cur] :
        mem[(cur, color)] = [C[color], D[color]]
    
    for nex, c, d in path[cur] :
        if nex == pre :
            continue
        C[c] += 1
        D[c] += d
        dfs(nex, cur)
        C[c] -= 1
        D[c] -= d

dfs(0, -1)
   
for x, y, u, v in xyuv :
    lca_ = lca(u, v)
    dist_ = dist[u] + dist[v] - 2*dist[lca_]
    C_ = mem[(u, x)][0] + mem[(v, x)][0] - 2*mem[(lca_, x)][0]
    D_ = mem[(u, x)][1] + mem[(v, x)][1] - 2*mem[(lca_, x)][1]
    print(dist_ - D_ + C_ * y)