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: Runtime Error

Solution code:
INF = 10**9

class RMQ:
    def __init__(self, a):
        self.n = len(a)
        self.size = 2**(self.n - 1).bit_length()
        self.data = [(INF, INF) for _ in range(2*self.size-1)]
        self.initialize(a)

    # Initialize data
    def initialize(self, a):
        for i in range(self.n):
            self.data[self.size + i - 1] = a[i][:]
        for i in range(self.size-2, -1, -1):
            self.data[i] = min(self.data[i*2 + 1], self.data[i*2 + 2])[:]
    
    # Update ak as x
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])[:]
    
    # Min value in [l, r)
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = (INF, INF)
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])[:]
            if L & 1:
                s = min(s, self.data[L-1])[:]
                L += 1
            L >>= 1; R >>= 1
        return s

class LCA:
    def __init__(self, edge, root):
        self.edge = edge[:]
        self.path = []
        self.depth = []
        self.color = []
        self.weight = []
        self.index = [0] * n
        self.euler_tour(-1, root, 0, 0, 0, 0)
        dat = list(zip(self.depth, self.path))
        self.rmq = RMQ(dat)
    
    # Lowest ancestor of u, v
    def get_lca(self, u, v):
        l, r = self.index[u], self.index[v]
        if l > r:
            l, r = r, l
        return self.rmq.query(l, r+1)[1]
    
    def get_depth(self, v):
        return self.depth[self.index[v]]

    def euler_tour(self, prev, v, d, k, c, w):
        self.index[v] = k
        self.path.append(v)
        self.depth.append(d)
        self.color.append(c)
        self.weight.append(w)
        k += 1
        for dest, c, w in self.edge[v]:
            if prev == dest:
                continue
            k = self.euler_tour(v, dest, d + 1, k, c, w)
            self.path.append(v)
            self.depth.append(d)
            self.color.append(-c)
            self.weight.append(-w)
            k += 1
        return k
        
n, q = [int(item) for item in input().split()] 
edge = [[] for _ in range(n)]

for i in range(n-1):
    u, v, c, w = [int(item) for item in input().split()]
    u -= 1; v -= 1
    edge[u].append([v, c, w])
    edge[v].append([u, c, w])

lca = LCA(edge, 0)
memo = [dict() for _ in range(n)]

query = []
for i in range(q):
    x, y, u, v = [int(item) for item in input().split()]
    u -= 1; v -= 1
    ca = lca.get_lca(u, v)
    memo[u][x] = None
    memo[v][x] = None
    memo[ca][x] = None
    query.append([x, y, u, v])

colors = [0] * n
c_depth = [0] * n
depth = 0
for i, (p, c, w) in enumerate(zip(lca.path, lca.color, lca.weight)):
    if i == 0:
        continue
    else:
        if c < 0:
            colors[abs(c)] -= 1
        else:
            colors[abs(c)] += 1
        c_depth[abs(c)] += w
        depth += w

        for key in memo[p].keys():
            memo[p][key] = [colors[key], c_depth[key]]
        memo[p][0] = depth 

for x, y, u, v in query:
    ca = lca.get_lca(u, v)
    # Calc basic distance
    ans = memo[u][0] + memo[v][0] - memo[ca][0] * 2
    # Append color diff
    ans += (memo[v][x][0] - memo[ca][x][0]) * y - (memo[v][x][1] - memo[ca][x][1])
    ans += (memo[u][x][0] - memo[ca][x][0]) * y - (memo[u][x][1] - memo[ca][x][1])
    print(ans)

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())

cn=[[] for i in range(N)]

def dst(x,y,o,p,g):
  for i in range(len(cn[p])):
    if cn[p][i][0] == o:
      continue
    d = y if cn[p][i][1] == x else cn[p][i][2]
    if cn[p][i][0] == g:
      return d
    r = dst(x,y,p,cn[p][i][0],g)
    if r != -1:
      return d + r
  return -1

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

for i in range(Q):
  x,y,u,v=map(int,input().split())
  print(dst(x,y,-1,u-1,v-1))

Submission status: Runtime Error

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:

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from math import log2

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

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

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

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

    if u == v:
        return u

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

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

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

dfs(root)
make_parent(level)

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

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

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

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

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc133/submissions/6316420
# 参考にさせていただきました。

import sys
input = sys.stdin.readline

n, q = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(n-1):
    a,b,c,d = map(int, input().split())
    a -= 1
    b -= 1
    c -= 1
    edges[a].append((b,c,d))
    edges[b].append((a,c,d))

# ここで前処理
# LCAができるようにしておく
dep=[0]*n
par=[[-1]*n for i in range(18)]
# ついでに距離も持っておく
dis=[0]*n

# parent, now_point, depth, dist

def dfs(p,v,d,dd):
    dep[v]=d
    par[0][v]=p
    dis[v]=dd
    for w, _, dist in edges[v]:
        if w!=p:
            dfs(v,w,d+1, dd+dist)

def lca(a,b):
    if dep[a]>dep[b]:
        a,b=b,a
    for i in range(18):
        if (dep[b]-dep[a]) & 1<<i:
            b=par[i][b]
    if a==b:
        return a
    for i in range(18)[::-1]:
        if par[i][a]!=par[i][b]:
            a=par[i][a]
            b=par[i][b]
    return par[0][a]

dfs(-1,0,0,0)

for i in range(17):
    for j in range(n):
        par[i+1][j]=par[i][par[i][j]]

# LCAの準備が完了

ans = [0]*q
v_need = [[] for i in range(n)]
for i in range(q):
    x,y,u,v = map(int, input().split())
    x -= 1
    u -= 1
    v -= 1
    l = lca(u, v)
    # 色の情報がほしいのは u, v, lの3点
    # どのクエリに属するか, どの色を変えるか、距離はいくつにするか, 係数
    v_need[u].append((i, x, y, 1))
    v_need[v].append((i, x, y, 1))
    v_need[l].append((i, x, y, -2))

# 色が何回出たか
color = [0]*n
# その点までの各色の距離の総和
cdist = [0]*n

def dfs2(cur, par):
    for i, x, y, k in v_need[cur]:
        ans[i] += k*(dis[cur] - cdist[x] + y*color[x])
    for to, x, y, in edges[cur]:
        if to == par:
            continue
        color[x] += 1
        cdist[x] += y
        dfs2(to, cur)
        # オイラーツアーのように、戻ってきたら引く
        # これによって、a→b→c→b→dと移動した時a→b→dとみなせる
        color[x] -= 1
        cdist[x] -= y
dfs2(0, -1)

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
from sys import exit
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)
    print(1)
	exit()
    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: Runtime Error

Solution code:
from collections import deque

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 i 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
D = [0] * N

def dfs(cur, pre) :
    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)

Submission status: Runtime Error

Solution code:
from collections import deque

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 i 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) :
    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)

Submission status: Runtime Error

Solution code:
from collections import deque

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

for K in range(18) :
    if 2 ** K >= N :
        break

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))

# Queryを先読みして必要な色を求める
xyuv = []
colors = [-1] * (N-1)
for _ in range(Q) : 
    x, y, u, v = map(int, input().split())
    xyuv.append([x-1, y, u-1, v-1])
    colors[x-1] = 1
  
count = 0
for i in range(N-1) :
    if colors[i] >= 0 :
        colors[i] = count
        count += 1

# dfs
parent = [[-1] * N for i in range(K)]
rank = [-1 for _ in range(N)]
dist = [0 for _ in range(N)]
C = [None for _ in range(N)]
D = [None for _ in range(N)]

rank[0] = 0
C[0] = [0] * count
D[0] = [0] * count
queue = deque([0])

while queue :
    cur = queue.popleft()
    
    for nex, c, d in path[cur] :
        if rank[nex] < 0 :
            parent[0][nex] = cur
            queue.append(nex)
            
            rank[nex] = rank[cur] + 1
            dist[nex] = dist[cur] + d
            
            if colors[c] >= 0 :
                C[nex] = C[cur][:]
                D[nex] = D[cur][:]
                C[nex][colors[c]] += 1
                D[nex][colors[c]] += d
            else :
                C[nex] = C[cur]
                D[nex] = D[cur]

# 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]]

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]
    
for x, y, u, v in xyuv :
    lca_ = lca(u, v)
    color = colors[x]
    
    dist_ = dist[u] + dist[v] - 2 * dist[lca_]
    C_ = C[u][color] + C[v][color] - 2 * C[lca_][color]
    D_ = D[u][color] + D[v][color] - 2 * D[lca_][color]
    
    print(dist_ - D_ + C_ * y)

Submission status: Runtime Error

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

N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
Q = int(input())
query = [[int(x) for x in input().split()] for _ in range(Q)]

def dfs(x, tour_v, tour_d, depth = 0, parent=None):
    tour_v.append(x)
    tour_d.append(depth)
    for y in graph[x]:
        if y == parent:
            continue
        dfs(y, tour_v, tour_d, depth + 1, parent = x)
        tour_v.append(x)
        tour_d.append(depth)

tour_v = []
tour_d = []
dfs(1, tour_v, tour_d)

v_to_i = {v:i for i,v in enumerate(tour_v)}
v_to_d = dict(zip(tour_v, tour_d))
tour_v = np.array(tour_v)
tour_d = np.array(tour_d)

# 各インデックスから、2^i 項目分見て、一番depthの小さいインデックス
L = len(tour_v)
U = L.bit_length()
sparse_table = [np.arange(L)]
for i in range(1,U):
    prev = sparse_table[-1]
    width = 1 << (i-1)
    n1 = prev[:-width]
    n2 = prev[width:]
    sparse_table.append(np.where(tour_d[n1] < tour_d[n2], n1, n2))

def LCA(x,y):
    ix = v_to_i[x]
    iy = v_to_i[y]
    if ix > iy:
        ix,iy = iy,ix
    items = iy - ix + 1
    L = items.bit_length() - 1
    n1 = sparse_table[L][ix]
    n2 = sparse_table[L][iy - (1 << L) + 1]
    n = n1 if tour_d[n1] < tour_d[n2] else n2
    return tour_v[n]

answer = [v_to_d[x] + v_to_d[y] - 2 * v_to_d[LCA(x,y)] + 1 for x,y in query]
print('\n'.join(map(str,answer)))

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict

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

for K in range(18) :
    if 2 ** K >= N :
        break

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))

parent = [[-1] * N for i in range(K)]
rank = [(-1, [0] * N, 0) for _ in range(N)]
rank[0] = [0, [0] * N, [0] * N]

queue = deque([0])

while queue :
    cur = queue.popleft()
    r, cl, dl = rank[cur]
    
    for nex, c, d in path[cur] :
        if rank[nex][0] < 0 :
            parent[0][nex] = cur
            queue.append(nex)
            cl_ = cl[:]
            dl_ = dl[:]
            cl_[c] += 1
            dl_[c] += d
            rank[nex] = [r + 1, cl_, dl_]

# 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]]

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

    diff = rank[b][0] - rank[a][0]
    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]

for _ in range(Q) : 
    x, y, u, v = map(int, input().split())
    x, u, v = x-1, u-1, v-1
    cl = [0] * N
    dl = [0] * N
    for i in range(N) :        
        dl[i] += rank[u][2][i]
        dl[i] += rank[v][2][i]
        dl[i] -= rank[lca(u, v)][2][i]
    dl[x] = y * (rank[u][1][x] + rank[v][1][x] - 2 * rank[lca(u, v)][1][x])
    print(sum(dl))

Submission status: Runtime Error

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

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

def set_ancestor(x=1, d=0, parent=0):
    depth[x] = d
    ax = ancestor[x]
    ax.append(parent)
    for i in range(d.bit_length() - 1):
        ax.append(ancestor[ax[i]][i])
    for y, _, _ in graph[x]:
        if y == parent:
            continue
        set_ancestor(y, d+1, x)

depth = [0] * (N+1)
ancestor = [[] for _ in range(N+1)] # 2**i だけ遡った頂点の番号、行き過ぎは0
set_ancestor()

def LCA(x,y):
    dx = depth[x]
    dy = depth[y]
    if dx > dy:
        x,y = y,x
        dx,dy = dy,dx
    diff = dy - dx
    while diff:
        step = diff & (-diff)
        y = ancestor[y][step.bit_length() - 1]
        diff -= step
    while x != y:
        j = 0
        while ancestor[x][j] != ancestor[y][j]:
            j += 1
        if j == 0:
            return ancestor[x][0]
        x = ancestor[x][j-1]
        y = ancestor[y][j-1]
    return x

tasks = [[] for _ in range(N+1)]
for i,(x,y,u,v) in enumerate(query):
    tasks[u].append((i,x,y,1))
    tasks[v].append((i,x,y,1))
    tasks[LCA(u,v)].append((i,x,y,-2))

answer = [0] * Q# 頂点、色に対して、距離、自色距離、自色個数)を入れる

def dfs(x, sums = defaultdict(int), nums = defaultdict(int), total = 0, parent = 0):
    for i,c,d,coef in tasks[x]:
        answer[i] += coef * (total - sums[c] + nums[c] * d)
    for y,c,d in graph[x]:
        if y == parent:
            continue
        sums[c] += d
        nums[c] += 1
        total += d
        dfs(y, sums, nums, total, x)
        sums[c] -= d
        nums[c] -= 1
        total -= d
    return

dfs(1)

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

Submission status: Runtime Error

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

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

def set_ancestor(x=1, d=0, parent=0):
    depth[x] = d
    ax = ancestor[x]
    ax.append(parent)
    for i in range(d.bit_length() - 1):
        ax.append(ancestor[ax[i]][i])
    for y, _, _ in graph[x]:
        if y == parent:
            continue
        set_ancestor(y, d+1, x)

depth = [0] * (N+1)
ancestor = [[] for _ in range(N+1)] # 2**i だけ遡った頂点の番号、行き過ぎは0
set_ancestor()

@lru_cache(None)
def LCA(x,y):
    dx = depth[x]
    dy = depth[y]
    if dx > dy:
        x,y = y,x
        dx,dy = dy,dx
    diff = dy - dx
    while diff:
        step = diff & (-diff)
        y = ancestor[y][step.bit_length() - 1]
        diff -= step
    while x != y:
        j = 0
        while ancestor[x][j] != ancestor[y][j]:
            j += 1
        if j == 0:
            return ancestor[x][0]
        x = ancestor[x][j-1]
        y = ancestor[y][j-1]
    return x

tasks = [[] for _ in range(N+1)]
for i,(x,y,u,v) in enumerate(query):
    tasks[u].append((i,x,y,1))
    tasks[v].append((i,x,y,1))
    tasks[LCA(u,v)].append((i,x,y,-1))

answer = [0] * Q# 頂点、色に対して、距離、自色距離、自色個数)を入れる

def dfs(x, sums = defaultdict(int), nums = defaultdict(int), total = 0, parent = 0):
    for i,c,d,coef in tasks[x]:
        answer[i] += coef * (total - sums[c] + nums[c] * d)
    for y,c,d in graph[x]:
        if y == parent:
            continue
        sums[c] += d
        nums[c] += 1
        total += d
        dfs(y, sums, nums, total, x)
        sums[c] -= d
        nums[c] -= 1
        total -= d
    return

dfs(1)

print('\n'.join(str(x) for x in answer))

Submission status: Runtime Error

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

N, Q = map(int, readline().split())
INF = (N, None)
M = 2*N
M0 = 2**(M-1).bit_length()
ii = -1

def dfs(bb, v, d, dd, cc, dpd, G, dp,
        S, F, w2i, depth, depthh, mmn, msn, iin):
    global ii
    ii += 1
    F[v] = ii
    depth[v] = d
    depthh[v] = dd
    S[ii] = v
    mmn[cc].append(mmn[cc][-1]+1)
    msn[cc].append(msn[cc][-1]+dpd)
    iin[cc].append(v)
    w2i[v] = ii
    for w in G[v]:
        if w == bb:
            continue
        cc, dpd = dp[(min(v,w), max(v,w))]
        dfs(v, w, d+1, dd+dpd, cc, dpd, G, dp,
        S, F, w2i, depth, depthh, mmn, msn, iin)
#        bb, v, d, dd = v, w, d+1, dd+dpd
        ii += 1
        S[ii] = v
        mmn[cc].append(mmn[cc][-1]-1)
        msn[cc].append(msn[cc][-1]-dpd)
        iin[cc].append(-w)
        w2i[-w] = ii

def _query(a, b, data):
    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, S, F, data):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1, data))[1]]

def b_s(ll, mm, ms, ind, lw, hw, target_i, lncc, w2i):
    if target_i < w2i[ll[0]] or target_i >= w2i[ll[lncc]]:
        return 0, 0
    while True:
        if w2i[ll[ind]] <= target_i:
            if target_i < w2i[ll[ind+1]]:
                return (mm[ind+1], ms[ind+1])
            ind, lw = (ind+1 + hw)//2, ind+1
            continue
        ind, hw = (ind-1 + lw)//2, ind-1

def iro(u, v, cc, x, y,
        mmn, msn, iin, lnc, w2i):
    u_n, u_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[u], lnc[x]-1, w2i)
    v_n, v_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[v], lnc[x]-1, w2i)
    c_n, c_d = b_s(iin[x], mmn[x], msn[x], (lnc[x]-1)//2, 0, lnc[x]-1, w2i[cc], lnc[x]-1, w2i)
    return (u_n + v_n - 2 * (c_n)) * y - (u_d + v_d - 2 * (c_d))


def main():
    G = [[] for _ in range(N)]
    dp = {}

    for v in range(N-1):
        a, b, c, d = map(int, readline().split())
        a, b = a-1, b-1
        G[a].append(b)
        G[b].append(a)
        dp[(min(a,b), max(a,b))] = c, d
     
    S, F, w2i = [0]*(2*N), [0]*N, [0]*(2*N)
    depth = depthh = [0]*N
    mmn, msn, iin = [[0] for _ in range(N)], [[0] for _ in range(N)], [[] for _ in range(N)]

    dfs(None, 0, 0, 0, 0,0,
            G, dp,
            S, F, w2i, depth, depthh, mmn, msn, iin)
    lnc = [len(x)-1 for x in mmn]
     
    data = [INF]*(2*M0)
    for i, v in enumerate(S):
        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])
     

    for q in range(Q):
        x, y, u, v = map(int, readline().split())
        u, v = u-1, v-1
        cc = query(u, v, S, F, data)
        if lnc[x] == 0:
            diff = 0
        else:
            diff = iro(u, v, cc, x, y, mmn, msn, iin, lnc, w2i)
        print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

if __name__ == '__main__':
    main()