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 deque

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

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

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: Time Limit Exceeded

Solution code:
import sys
from collections import deque

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

# 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) :
    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: Time Limit Exceeded

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) :
    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: Time Limit Exceeded

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
            C[nex] = C[cur][:]
            D[nex] = D[cur][:]
            
            if colors[c] >= 0 :
                C[nex][colors[c]] += 1
                D[nex][colors[c]] += 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]]

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: Time Limit Exceeded

Solution code:
from collections import deque,defaultdict
import sys
sys.setrecursionlimit(10**7)
N,Q=map(int,input().split())
table=[[] for i in range(N)]
ddcost=defaultdict(tuple)
for i in range(N-1):
    a,b,c,d=map(int,input().split())
    a,b,c=a-1,b-1,c-1
    table[a].append(b)
    table[b].append(a)
    ddcost[(min(a,b),max(b,a))]=(c,d)
#print(table)
#print(ddcost)
H=deque()
H.append(0)
visit=[-1]*N
visit[0]=0
parent=[[-1]*N for i in range(17)]
while H:
    x=H.popleft()
    for y in table[x]:
        if visit[y]!=-1:
            continue
        parent[0][y]=x
        visit[y]=visit[x]+1
        H.append(y)
for k in range(16):
    for i in range(N):
        if parent[k][i]<0:
            parent[k+1][i]=-1
        else:
            parent[k + 1][i]=parent[k][parent[k][i]]
def lca(u,v):
    if visit[u]>visit[v]:
        u,v=v,u
    for k in range(17):
        if ((visit[v]-visit[u] )>>k)&1:
            v=parent[k][v]
    if u==v:
        return u
    for k in range(16,-1,-1):
        if parent[k][u]!=parent[k][v]:
            u=parent[k][u]
            v=parent[k][v]
    return parent[0][u]

query=[]
sakidori=[set() for i 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
    if u>=v:
        u,v=v,u
    pa=lca(u,v)
    sakidori[u].add(x)
    sakidori[v].add(x)
    sakidori[pa].add(x)
    query.append((x,y,u,v,pa))
ddcolorsum=defaultdict(int)
ddcolornum=defaultdict(int)
W=deque()
colorsum=[0]*(N)
colornum=[0]*(N)
dist=[0]*N
vi=[0]*N
W.append((0,0,1))

while W:
    #print(W)
    pa,ci,vector=W.pop()
    if vector==-1:
        color,dis=ddcost[(min(pa,ci),max(pa,ci))]
        colorsum[color]-=dis
        colornum[color]-=1
        #print(colorsum, colornum, pa, ci, vector)
        continue
    if pa==0 and ci==0:
        for y in table[ci]:
            W.append((ci, y, 1))
        for co in sakidori[0]:
            ddcolorsum[(0,co)]=0
            ddcolornum[(0,co)]=0
        continue
    color,dis=ddcost[(min(pa,ci),max(pa,ci))]
    dist[ci]=dist[pa]+dis
    colorsum[color]+=dis
    colornum[color]+=1
    for co in sakidori[ci]:
        ddcolorsum[(ci, co)] = colorsum[co]
        ddcolornum[(ci, co)] = colornum[co]
    #print(colorsum,colornum,pa,ci,vector)
    W.append((pa,ci,-1))
    for y in table[ci]:
        if y==pa:
            continue
        W.append((ci,y,1))
#print(ddcolorsum)
#print(ddcolornum)
#print(dist)
def dista(x,y,u):
    return dist[u]-ddcolorsum[(u,x)]+y*ddcolornum[(u,x)]
for x,y,u,v,pa in query:
    #print(x,y,u,v,pa)
    #print(dista(x,y,u),dista(x,y,v),dista(x,y,pa))
    print(dista(x,y,u)+dista(x,y,v)-2*dista(x,y,pa))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.readline
 
N, Q = map(int, readline().split())

def process():
    INF = (N, None)
    M = 2*N
    M0 = 2**(M-1).bit_length()
    data = [INF]*(2*M0)
    lnc = [0]*N

    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 = [0]*(2*N)
    F = [0]*(2*N)
    stack = [0] + G[0][::-1]
    visited = set([0])
    depth = [0]*N
    depthh = [0]*N
    mmn = [[0] for _ in range(N)]
    msn = [[0] for _ in range(N)]
    iin = [[] for _ in range(N)]
    ccs = [0]*N
    path = [0]
    ii = 0
    d = 0
    dd = 0

    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v in visited:
            continue
        ii += 1
        if v >=0:
            visited.add(v)
            cc, dpd = dp[(min(v,path[-1]), max(v,path[-1]))]
            F[v] = ii
            S[ii] = v
            d += 1
            dd += dpd
            depth[v] = d
            depthh[v] = dd
            ccs[v] = cc

            mmn[cc].append(mmn[cc][-1]+1)
            msn[cc].append(msn[cc][-1]+dpd)
            iin[cc].append(v)

            path.append(v)
            stack += [-v] + G[v][::-1]
        else:
            cc, dpd = dp[(min(path[-1], path[-2]), max(path[-1],path[-2]))]
            dd -= dpd
            mmn[cc].append(mmn[cc][-1]-1)
            iin[cc].append(-path[-1])
            msn[cc].append(msn[cc][-1]-dpd)
            F[-path[-1]] = ii
            path.pop()
            S[ii] = path[-1]
            d -= 1
    
    for i, z in enumerate(mmn):
        lnc[i] = len(z)-1

    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
        fu = F[u]; fv = F[v]
        if fu > fv:
            fu, fv = fv, fu

        minx = INF
        a, b = fu, fv+1
        a += M0; b += M0
        while a < b:
            if b & 1:
                b -= 1
                minx = min(minx, data[b-1])
            if a & 1:
                minx = min(minx, data[a-1])
                a += 1
            a >>= 1; b >>= 1
        cc = S[minx[1]]
        if lnc[x] == 0:
            diff = 0
        else:
            ll, mm, ms, lncc = iin[x], mmn[x], msn[x], lnc[x]-1
            uvcs = []
            for target_i in [F[u], F[v], F[cc]]:
                ind, lw, hw =  (lnc[x]-1)//2, 0, lnc[x]-1
                if target_i < F[ll[0]] or target_i >= F[ll[lncc]]:
                    uvcs.append((0,0))
                else:
                    while True:
                        if F[ll[ind]] <= target_i:
                            if target_i < F[ll[ind+1]]:
                                uvcs.append((mm[ind+1], ms[ind+1]))
                                break
                            ind, lw = (ind+1 + hw)//2, ind+1
                            continue
                        ind, hw = (ind-1 + lw)//2, ind-1
            diff = (uvcs[0][0] + uvcs[1][0] - 2 * uvcs[2][0]) * y - (uvcs[0][1] + uvcs[1][1] - 2 * uvcs[2][1])
        print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

if __name__ == '__main__':
    process()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
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)]

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

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

@lru_cache(None)
def LCA(x,y):
    if x == y:
        return x
    dx = depth[x]
    dy = depth[y]
    if dx > dy:
        x,y = y,x
        dx,dy = dy,dx
    diff = dy - dx
    if diff > 0:
        while diff:
            step = diff & (-diff)
            y = ancestor[y][step.bit_length() - 1]
            diff -= step
        return LCA(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 LCA(x,y)

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 = 1, sums = [0] * (N+1), nums = [0] * (N+1), 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()

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)
readline = sys.stdin.readline
 
N, Q = map(int, readline().split())
S = [0]*(2*N)
F = [0]*N
depth = [0]*N
depthh = [0]*N
mmn = [[0] for _ in range(N)]
msn = [[0] for _ in range(N)]
iin = [[] for _ in range(N)]
w2i = [0]*(2*N)
ii = -1



def process():
    def dfs(bb, v, d, dd, cc, dpd):
        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)
    #        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
    INF = (N, None)
    M = 2*N
    M0 = 2**(M-1).bit_length()
    data = [INF]*(2*M0)
    dp = {}
    lnc = [0]*N


    G = [[] for _ in range(N)]
    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
    dfs(None, 0, 0, 0, 0,0)
    for i, z in enumerate(mmn):
        lnc[i] = len(z)-1

    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
        fu = F[u]; fv = F[v]
        if fu > fv:
            fu, fv = fv, fu

        minx = INF
        a, b = fu, fv+1
        a += M0; b += M0
        while a < b:
            if b & 1:
                b -= 1
                minx = min(minx, data[b-1])
            if a & 1:
                minx = min(minx, data[a-1])
                a += 1
            a >>= 1; b >>= 1
        cc = S[minx[1]]
        if lnc[x] == 0:
            diff = 0
        else:
            ll, mm, ms, lncc = iin[x], mmn[x], msn[x], lnc[x]-1
            uvcs = []
            for target_i in [w2i[u], w2i[v], w2i[cc]]:
                ind, lw, hw =  (lnc[x]-1)//2, 0, lnc[x]-1
                if target_i < w2i[ll[0]] or target_i >= w2i[ll[lncc]]:
                    uvcs.append((0,0))
                else:
                    while True:
                        if w2i[ll[ind]] <= target_i:
                            if target_i < w2i[ll[ind+1]]:
                                uvcs.append((mm[ind+1], ms[ind+1]))
                                break
                            ind, lw = (ind+1 + hw)//2, ind+1
                            continue
                        ind, hw = (ind-1 + lw)//2, ind-1
            diff = (uvcs[0][0] + uvcs[1][0] - 2 * uvcs[2][0]) * y - (uvcs[0][1] + uvcs[1][1] - 2 * uvcs[2][1])
        print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

if __name__ == '__main__':
    process()

Submission status: Time Limit Exceeded

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()
data = [INF]*(2*M0)


G = [[] for _ in range(N)]
dp = {}
S = [0]*(2*N)
F = [0]*N
lnc = [0]*N
depth = [0]*N
depthh = [0]*N
mmn = [[0] for _ in range(N)]
msn = [[0] for _ in range(N)]
iin = [[] for _ in range(N)]
w2i = [0]*(2*N)
ii = -1

def dfs(bb, v, d, dd, cc, dpd):
    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)
#        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 process():
    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
    dfs(None, 0, 0, 0, 0,0)
    for i, z in enumerate(mmn):
        lnc[i] = len(z)-1

    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
        fu = F[u]; fv = F[v]
        if fu > fv:
            fu, fv = fv, fu

        minx = INF
        a, b = fu, fv+1
        a += M0; b += M0
        while a < b:
            if b & 1:
                b -= 1
                minx = min(minx, data[b-1])
            if a & 1:
                minx = min(minx, data[a-1])
                a += 1
            a >>= 1; b >>= 1
        cc = S[minx[1]]
        if lnc[x] == 0:
            diff = 0
        else:
            ll, mm, ms, lncc = iin[x], mmn[x], msn[x], lnc[x]-1
            uvcs = []
            for target_i in [w2i[u], w2i[v], w2i[cc]]:
                ind, lw, hw =  (lnc[x]-1)//2, 0, lnc[x]-1
                if target_i < w2i[ll[0]] or target_i >= w2i[ll[lncc]]:
                    uvcs.append((0,0))
                else:
                    while True:
                        if w2i[ll[ind]] <= target_i:
                            if target_i < w2i[ll[ind+1]]:
                                uvcs.append((mm[ind+1], ms[ind+1]))
                                break
                            ind, lw = (ind+1 + hw)//2, ind+1
                            continue
                        ind, hw = (ind-1 + lw)//2, ind-1
            diff = (uvcs[0][0] + uvcs[1][0] - 2 * uvcs[2][0]) * y - (uvcs[0][1] + uvcs[1][1] - 2 * uvcs[2][1])
        print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

if __name__ == '__main__':
    process()

Submission status: Time Limit Exceeded

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()
data = [INF]*(2*M0)


G = [[] for _ in range(N)]
dp = {}
S = [0]*(2*N)
F = [0]*N
lnc = [0]*N
depth = [0]*N
depthh = [0]*N
mmn = [[0] for _ in range(N)]
msn = [[0] for _ in range(N)]
iin = [[] for _ in range(N)]
w2i = [0]*(2*N)
ii = -1

def dfs(bb, v, d, dd, cc, dpd):
    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)
#        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 mk_data():
    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])

 
def b_s(ll, mm, ms, ind, lw, hw, target_i, lncc):
    if target_i < w2i[ll[0]]:
        return 0, 0
    if 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 process():
    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
    dfs(None, 0, 0, 0, 0,0)
    for i, z in enumerate(mmn):
        lnc[i] = len(z)-1
    mk_data()
    for q in range(Q):
        x, y, u, v = map(int, readline().split())
        u, v = u-1, v-1
        fu = F[u]; fv = F[v]
        if fu > fv:
            fu, fv = fv, fu

        minx = INF
        a, b = fu, fv+1
        a += M0; b += M0
        while a < b:
            if b & 1:
                b -= 1
                minx = min(minx, data[b-1])
            if a & 1:
                minx = min(minx, data[a-1])
                a += 1
            a >>= 1; b >>= 1
        cc = S[minx[1]]
        if lnc[x] == 0:
            diff = 0
        else:
            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)
            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)
            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)
            diff = (u_n + v_n - 2 * (c_n)) * y - (u_d + v_d - 2 * (c_d))
        print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

if __name__ == '__main__':
    process()

Submission status: Time Limit Exceeded

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()
data = [INF]*(2*M0)


G = [[] for _ in range(N)]
dp = {}
S = [0]*(2*N)
F = [0]*N
depth = [0]*N
depthh = [0]*N
mmn = [[0] for _ in range(N)]
msn = [[0] for _ in range(N)]
iin = [[] for _ in range(N)]
w2i = [0]*(2*N)
ii = -1

def init():
    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

def dfs(bb, v, d, dd, cc, dpd):
    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)
#        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 mk_data():
    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])
 
def b_s(ll, mm, ms, ind, lw, hw, target_i, lncc):
    if target_i < w2i[ll[0]]:
        return 0, 0
    if 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 process():
    for q in range(Q):
        x, y, u, v = map(int, readline().split())
        u, v = u-1, v-1
        fu = F[u]; fv = F[v]
        if fu > fv:
            fu, fv = fv, fu

        minx = INF
        a, b = fu, fv+1
        a += M0; b += M0
        while a < b:
            if b & 1:
                b -= 1
                minx = min(minx, data[b-1])
            if a & 1:
                minx = min(minx, data[a-1])
                a += 1
            a >>= 1; b >>= 1
        cc = S[minx[1]]
        if lnc[x] == 0:
            diff = 0
        else:
            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)
            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)
            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)
            diff = (u_n + v_n - 2 * (c_n)) * y - (u_d + v_d - 2 * (c_d))
        print(depthh[u] + depthh[v] - 2*depthh[cc] + diff)

if __name__ == '__main__':
    init()
    dfs(None, 0, 0, 0, 0,0)
    lnc = [len(x)-1 for x in mmn]
    mk_data()
    process()