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:
import sys
sys.setrecursionlimit(10**6)
from collections import defaultdict
class LCA:

    def __init__(self,n):
        self.size = n+1
        self.bitlen = n.bit_length()
        self.lca = [[0]*self.bitlen for i in range(self.size)]
        self.depth = [-1]*self.size
    def dfs(self,now,par,dep):
        if self.depth[now] >= 0:
            return self.depth[now]
        self.depth[now] = dep
        for nex in e[now]:
            if nex[0] == par or self.depth[nex[0]] >= 0:
                continue
            self.dfs(nex[0],now,dep+1)
        return self.depth[now]
    def make(self,root):
        self.dfs(root,0,0)
        self.lca[0] = self.depth
        for i in range(1,self.bitlen):
            for j in range(self.size):
                if self.lca[j][i-1] > 0:
                    self.lca[j][i] = self.lca[self.lca[j][i-1]][i-1]
    
    def search(self,x,y):
        dx = self.depth[x]
        dy = self.depth[y]
        if dx < dy:
            x,y = y,x
            dx,dy = dy,dx
        dif = dx-dy
        while dif:
            s = dif & (-dif)
            x = self.lca[x][s.bit_length()-1]
            dif -= s
        if x == y:
            return x
        for i in range(self.bitlen-1,-1,-1):
            if self.lca[x][i] != self.lca[y][i]:
                x = self.lca[x][i]
                y = self.lca[y][i]
            else:
                break
        return self.lca[x][0]

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))
    
lca = LCA(n)
lca.make(1)

Q = []
dcount = defaultdict(lambda : defaultdict(int))
dweight = defaultdict(lambda : defaultdict(int))
for i in range(q):
    x,y,u,v = map(int,input().split())
    a = lca.search(u,v)
    dcount[u][x] = 0
    dcount[v][x] = 0
    dcount[a][x] = 0
    dweight[u][x] = 0
    dweight[v][x] = 0
    dweight[a][x] = 0
    Q.append((x,y,u,v,a))

dis = [0]*(n+1)


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
        dis[nex] =dis[now]+w
        dfs1(nex,now,count1,count2)
        count1[c] -= 1
        count2[c] -= w
    
dfs1(1,0,defaultdict(int),defaultdict(int))

for x,y,u,v,a in Q:
    cal = dis[u]+dis[v]-2*dis[a]
    cal += y*(dcount[u][x]+dcount[v][x]-2*dcount[a][x]) - dweight[u][x]-dweight[v][x]+2*dweight[a][x]
    print(cal)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import defaultdict
class LCA:

    def __init__(self,n):
        self.size = n+1
        x = 1
        while 1<<x < n:
            x += 1
        self.bitlen = x
        self.lca = [[0]*self.bitlen for i in range(self.size)]
        self.depth = [-1]*self.size
    def dfs(self,now,par,dep):
        if self.depth[now] >= 0:
            return self.lca[now][0]
        self.lca[now][0] = par
        self.depth[now] = dep
        for nex in e[now]:
            if nex[0] == par or self.depth[nex[0]] >= 0:
                continue
            self.dfs(nex[0],now,dep+1)
        return self.lca[now][0]
    def make(self,root):
        self.dfs(root,0,0)
        for i in range(1,self.bitlen):
            for j in range(self.size):
                self.lca[j][i] = self.lca[self.lca[j][i-1]][i-1]
    
    def search(self,x,y):
        dx = self.depth[x]
        dy = self.depth[y]
        if dx < dy:
            x,y = y,x
            dx,dy = dy,dx
        dif = dx-dy
        while dif:
            s = dif & (-dif)
            x = self.lca[x][s.bit_length()-1]
            dif -= s
        if x == y:
            return x
        for i in range(self.bitlen-1,-1,-1):
            if self.lca[x][i] != self.lca[y][i]:
                x = self.lca[x][i]
                y = self.lca[y][i]
        return self.lca[x][0]

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))
    
lca = LCA(n)
lca.make(1)

Q = []
dcount = defaultdict(lambda : defaultdict(int))
dweight = defaultdict(lambda : defaultdict(int))
for i in range(q):
    x,y,u,v = map(int,input().split())
    a = lca.search(u,v)
    dcount[u][x] = -1
    dcount[v][x] = -1
    dcount[a][x] = -1
    dweight[u][x] = -1
    dweight[v][x] = -1
    dweight[a][x] = -1
    Q.append((x,y,u,v,a))

dis = [-1]*(n+1)
dis[0] = 0
count1 = [0]*(n+1)
count2 = [0]*(n+1)
def dfs1(now,p,c,d):
    if dis[now] >= 0:
        return dis[now]
    dis[now] = dis[p]+d
    count1[c] += 1
    count2[c] += d
    for cou in dcount[now]:
        dcount[now][cou] = count1[cou]
    for wei in dweight[now]:
        dweight[now][wei] = count2[wei]

    for nex in e[now]:
        if nex[0] == p or dis[nex[0]] >= 0:
            continue
        dfs1(nex[0],now,nex[1],nex[2])
    return dis[now]
dfs1(1,0,0,0)

for x,y,u,v,a in Q:
    cal = dis[u]+dis[v]-2*dis[a]
    cal += y*(dcount[u][x]+dcount[v][x]-2*dcount[a][x]) - dweight[u][x]-dweight[v][x]+2*dweight[a][x]
    print(cal)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
class LCA:

    def __init__(self,n):
        self.size = n+1
        x = 1
        while 1<<x < n:
            x += 1
        self.bitlen = x
        self.lca = [[0]*self.bitlen for i in range(self.size)]
        self.depth = [-1]*self.size
    def dfs(self,now,par,dep):
        if self.depth[now] >= 0:
            return self.lca[now][0]
        self.lca[now][0] = par
        self.depth[now] = dep
        for nex in e[now]:
            if nex[0] == par or self.depth[nex[0]] >= 0:
                continue
            self.dfs(nex[0],now,dep+1)
        return self.lca[now][0]
    def make(self,root):
        self.dfs(root,0,0)
        for i in range(1,self.bitlen):
            for j in range(self.size):
                self.lca[j][i] = self.lca[self.lca[j][i-1]][i-1]
    
    def search(self,x,y):
        dx = self.depth[x]
        dy = self.depth[y]
        if dx < dy:
            x,y = y,x
            dx,dy = dy,dx
        dif = dx-dy
        while dif:
            s = dif & (-dif)
            x = self.lca[x][s.bit_length()-1]
            dif -= s
        if x == y:
            return x
        for i in range(self.bitlen-1,-1,-1):
            if self.lca[x][i] != self.lca[y][i]:
                x = self.lca[x][i]
                y = self.lca[y][i]
        return self.lca[x][0]

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))
    
lca = LCA(n)
lca.make(1)

Q = [[] for i in range(n)]

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



dis = [-1]*(n+1)

def dfs1(now,p,d):
    if dis[now] >= 0:
        return dis[now]
    dis[now] = d
    for nex in e[now]:
        if nex[0] == p or dis[nex[0]] >= 0:
            continue
        dfs1(nex[0],now,d+nex[2])
    return dis[now]

def dfs2(now,p,d,d2):
    if count1[now] >= 0:
        return count1[now]
    count1[now] = d
    count2[now] = d2
    for nex in e[now]:
        if nex[0] == p or count1[nex[0]] >= 0:
            continue
        if nex[1] == c:
            dfs2(nex[0],now,d+1,d2+nex[2])
        else:
            dfs2(nex[0],now,d,d2)
    return count1[now]
dfs1(1,0,0)
ans = [0]*q
for i in range(n):
    if Q[i] == []:
        continue
    c = i
    count1 = [-1]*(n+1)
    count2 = [-1]*(n+1)
    dfs2(1,0,0,0)
    for y,u,v,j in Q[i]:
        a = lca.search(u,v)
        cal = dis[u]+dis[v]-2*dis[a]
        cal += (count1[u]+count1[v]-2*count1[a])*y-count2[u]-count2[v]+count2[a]
        ans[j] = cal

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
e = [[] for i in range(n+1)]
color = [0]*(n)
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))
    color[c] = d

Q = [[] for i in range(n)]

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

import sys
sys.setrecursionlimit(10**6)
class LCA:

    def __init__(self,n):
        self.size = n+1
        x = 1
        while 1<<x < n:
            x += 1
        self.bitlen = x
        self.lca = [[0]*self.bitlen for i in range(self.size)]
        self.depth = [-1]*self.size
    def dfs(self,now,par,dep):
        if self.depth[now] >= 0:
            return self.lca[now][0]
        self.lca[now][0] = par
        self.depth[now] = dep
        for nex in e[now]:
            if nex[0] == par or self.depth[nex[0]] >= 0:
                continue
            self.dfs(nex[0],now,dep+1)
        return self.lca[now][0]
    def make(self,root):
        self.dfs(root,0,0)
        for i in range(1,self.bitlen):
            for j in range(self.size):
                self.lca[j][i] = self.lca[self.lca[j][i-1]][i-1]
    
    def search(self,x,y):
        dx = self.depth[x]
        dy = self.depth[y]
        if dx < dy:
            x,y = y,x
            dx,dy = dy,dx
        dif = dx-dy
        while dif:
            s = dif & (-dif)
            x = self.lca[x][s.bit_length()-1]
            dif -= s
        while x != y:
            j = 0
            while self.lca[x][j] != self.lca[y][j]:
                j += 1
            if j == 0:
                return self.lca[x][0]
            x = self.lca[x][j-1]
            y = self.lca[y][j-1]
        return x
lca = LCA(n)
lca.make(1)
dis = [-1]*(n+1)

def dfs1(now,p,d):
    if dis[now] >= 0:
        return dis[now]
    dis[now] = d
    for nex in e[now]:
        if nex[0] == p or dis[nex[0]] >= 0:
            continue
        dfs1(nex[0],now,d+nex[2])
    return dis[now]

def dfs2(now,p,d,d2):
    if count1[now] >= 0:
        return count1[now]
    count1[now] = d
    count2[now] = d2
    for nex in e[now]:
        if nex[0] == p or count1[nex[0]] >= 0:
            continue
        if nex[1] == c:
            dfs2(nex[0],now,d+1,d2+nex[2])
        else:
            dfs2(nex[0],now,d,d2)
    return count1[now]
dfs1(1,0,0)
ans = [0]*q
for i in range(n):
    if Q[i] == []:
        continue
    c = i
    count1 = [-1]*(n+1)
    count2 = [-1]*(n+1)
    dfs2(1,0,0,0)
    for y,u,v,j in Q[i]:
        a = lca.search(u,v)
        cal = dis[u]+dis[v]-2*dis[a]
        cal += (count1[u]+count1[v]-2*count1[a])*y-count2[u]-count2[v]+count2[a]
        ans[j] = cal

for i in ans:
    print(i)

Submission status: Wrong Answer

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

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

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

par = [[-1] * N for _ in range(D)]
dep = [0] * N
dist = [0] * N
node = [0]
while node:
    s = node.pop()
    for t, _, d in edge[s]:
        if par[0][s] == t:
            continue
        par[0][t] = s
        dep[t] = dep[s] + 1
        dist[t] = dist[s] + d
        node.append(t)

for d in range(D - 1):
    for i in range(N):
        par[d + 1][i] = par[d][par[d][i]]


def LCA(x, y):
    if dep[x] < dep[y]:
        x, y = y, x
    h = dep[x] - dep[y]
    for d in reversed(range(D)):
        if h >= 1 << d:
            x = par[d][x]
            h -= 1 << d
    if x == y:
        return x
    for d in reversed(range(D)):
        if par[d][x] != par[d][y]:
            x = par[d][x]
            y = par[d][y]
    return par[0][x]


memo = [[] for _ in range(N)]
ans = [0] * Q

for i, (x, y, u, v) in enumerate(query):
    u -= 1
    v -= 1
    c = LCA(u, v)
    ans[i] = dist[u] + dist[v] - 2 * dist[c]
    memo[u].append((x, y, i))
    memo[v].append((x, y, i))
    memo[c].append((x, y, ~i))


c_len = [0] * (N + 1)
c_cnt = [0] * (N + 1)


def dfs(s, p=-1):
    for c, val, i in memo[s]:
        if i >= 0:
            ans[i] -= c_len[c]
            ans[i] += c_cnt[c] * val
        else:
            ans[~i] += c_len[c]
            ans[~i] -= c_cnt[c] * val
    for t, c, d in edge[s]:
        if t == p:
            continue
        c_len[c] += d
        c_cnt[c] += 1
        dfs(t, s)
        c_len[c] -= d
        c_cnt[c] -= 1


dfs(0)
print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


n,q = map(int,readline().split())
data = list(map(int,read().split()))
abcd = data[:4*(n-1)]
xyuv = data[4*(n-1):]

root = 1
dbl_max = 20
dbl = [[0] * dbl_max for _ in range(n+1)]
depth = [0] * (n+1)
links = [[] for _ in range(n+1)]
it = iter(abcd)
for a,b,c,d in zip(it,it,it,it):
    links[a].append((b,c,d))
    links[b].append((a,c,d))

stack = [root]
while(stack):
    i = stack.pop()
    for j,c,d in links[i]:
        if(j==dbl[i][0]):
            continue
        dbl[j][0] = i
        depth[j] = depth[i]+1
        stack.append(j)

for i in range(1,dbl_max):
    for j in range(1,n+1):
        dbl[j][i] = dbl[dbl[j][i-1]][i-1]

def get_lca(x,y):
    if(depth[x] > depth[y]):
        x,y = y,x

    dif = depth[y]-depth[x]
    for i in range(dbl_max):
        if(dif==0):
            break
        if(dif>>i)&1:
            y = dbl[y][i]
            dif -= (1<<i)

    for i in range(dbl_max-1,0,-1):
        if(dbl[x][i] != dbl[y][i]):
            x = dbl[x][i]
            y = dbl[y][i]

    if(x!=y):
        return dbl[x][0]
    else:
        return x

ans = [0] * q
query = [[] for _ in range(n+1)]
for i in range(q):
    x,y,u,v = xyuv[i*4:i*4+4]

    lca = get_lca(u,v)
    query[u].append((i,x,y,1))
    query[v].append((i,x,y,1))
    query[lca].append((i,x,y,-2))

tot = 0
c_cost = [[0,0] for _ in range(n)]
stack = []
for j,c,d in links[root]:
    stack.append((root,j,c,d,1))

while(stack):
    a,b,c,d,num = stack.pop()
    tot += d*num
    c_cost[c][0] += d*num
    c_cost[c][1] += num

    if(num==1):
        for qi,x,y,num_q in query[b]:
            ans[qi] += num_q * (tot - c_cost[x][0] + c_cost[x][1]*y)

        next = []
        for j,c,d in links[b]:
            if(j==dbl[b][0]):
                stack.append((b,j,c,d,-1))
            else:
                next.append((b,j,c,d,1))
        stack += next

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

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


n,q = map(int,readline().split())
data = list(map(int,read().split()))
abcd = data[:4*(n-1)]
xyuv = data[4*(n-1):]

root = 1
dbl_max = 20
dbl = [[0] * dbl_max for _ in range(n+1)]
depth = [0] * (n+1)
links = [[] for _ in range(n+1)]
it = iter(abcd)
for a,b,c,d in zip(it,it,it,it):
    links[a].append((b,c,d))
    links[b].append((a,c,d))

stack = [root]
while(stack):
    i = stack.pop()
    for j,c,d in links[i]:
        if(j==dbl[i][0]):
            continue
        dbl[j][0] = i
        depth[j] = depth[i]+1
        stack.append(j)

for i in range(1,dbl_max):
    for j in range(1,n+1):
        dbl[j][i] = dbl[dbl[j][i-1]][i-1]

def get_lca(x,y):
    if(depth[x] > depth[y]):
        x,y = y,x

    dif = depth[y]-depth[x]
    for i in range(dbl_max):
        if(dif==0):
            break
        if(dif>>i)&1:
            y = dbl[y][i]
            dif -= (1<<i)

    for i in range(dbl_max-1,-1,-1):
        if(dbl[x][i] != dbl[y][i]):
            x = dbl[x][i]
            y = dbl[y][i]

    return x

ans = [0] * q
query = [[] for _ in range(n+1)]
for i in range(q):
    x,y,u,v = xyuv[i*4:i*4+4]

    lca = get_lca(u,v)
    query[u].append((i,x,y,1))
    query[v].append((i,x,y,1))
    query[lca].append((i,x,y,-2))

tot = 0
c_cost = [[0,0] for _ in range(n)]
stack = []
for j,c,d in links[root]:
    stack.append((root,j,c,d,1))

while(stack):
    a,b,c,d,num = stack.pop()
    tot += d*num
    c_cost[c][0] += d*num
    c_cost[c][1] += num

    if(num==1):
        for qi,x,y,num_q in query[b]:
            ans[qi] += num_q * (tot - c_cost[x][0] + c_cost[x][1]*y)

        next = []
        for j,c,d in links[b]:
            if(j==dbl[b][0]):
                stack.append((b,j,c,d,-1))
            else:
                next.append((b,j,c,d,1))
        stack += next

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
edge=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c,d=map(int1,input().split())
    d+=1
    edge[a].append((b,c,d))
    edge[b].append((a,c,d))
U=defaultdict(list)
V=defaultdict(list)
Query=[]
for i in range(Q):
    x,y,u,v=map(int1,input().split())
    y+=1
    Query.append((x,y,u,v))
    U[u].append((x,y,i))
    V[v].append((x,y,i))

S=[0]*(2*N-1)

def EulerTour(start,n,edges):
    used=[False]*n
    et=[]
    left=[-1]*n
    right=[-1]*n
    depth=[]
    stack=[(start,-1,-1)]
    cur_depth=-1
    while stack:
        v,c,d=stack.pop()
        if et:
            S[len(et)]=S[len(et)-1]+d
        if v>=0:
            used[v]=True
            cur_depth+=1
            left[v]=right[v]=len(et)
            et.append(v)
            depth.append(cur_depth)
            for nv,c,d in edges[v]:
                if not used[nv]:
                    stack.append((~v,c,-d))
                    stack.append((nv,c,d))
        else:
            cur_depth-=1
            right[~v]=len(et)
            et.append(~v)
            depth.append(cur_depth)
    return et,left,depth

et,left,depth=EulerTour(0,N,edge)

class SegmentTree:
    def __init__(self,n,segfunc,ide_ele):
        self.segfunc=segfunc
        self.ide_ele=ide_ele
        self.num=2**(n-1).bit_length()
        self.dat=[ide_ele]*2*self.num
    
    def init(self,iter):
        for i in range(len(iter)):
            self.dat[i+self.num]=iter[i]
        for i in range(self.num-1,0,-1):
            self.dat[i]=self.segfunc(self.dat[i*2],self.dat[i*2+1])
    
    def update(self,k,x):
        k+=self.num
        self.dat[k]=x
        while k:
            k//=2
            self.dat[k]=self.segfunc(self.dat[k*2],self.dat[k*2+1])
    
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num
        q+=self.num-1
        res=self.ide_ele
        while q-p>1:
            if p&1==1:
                res=self.segfunc(res,self.dat[p])
            if q&1==0:
                res=self.segfunc(res,self.dat[q])
                q-=1
            p=(p+1)//2
            q=q//2
        if p==q:
            res=self.segfunc(res,self.dat[p])
        else:
            res=self.segfunc(self.segfunc(res,self.dat[p]),self.dat[q])
        return res

s=SegmentTree(2*N-1,lambda a,b:min(a,b,key=lambda t:t[0]),(INF,INF))
for i in range(2*N-1):
    s.update(i,(depth[i],i))

LCA=defaultdict(list)
LLCA=[-1]*Q
for i,(x,y,u,v) in enumerate(Query):
    p,q=min(left[u],left[v]),max(left[u],left[v])+1
    res=s.query(p,q)
    LCA[et[res[1]]].append((x,y,i))
    LLCA[i]=res[1]

diff=[0]*Q

def EulerTour2(start,n,edges):
    used=[False]*n
    et=[]
    left=[-1]*n
    right=[-1]*n
    depth=[]
    stack=[(start,-1,-1)]
    cur_depth=-1
    col=[[0,0] for _ in range(N)]
    while stack:
        v,c,d=stack.pop()
        if v>=0:
            col[c][0]+=d
            col[c][1]+=1
            used[v]=True
            cur_depth+=1
            left[v]=right[v]=len(et)
            et.append(v)
            depth.append(cur_depth)
            for nv,c,d in edges[v]:
                if not used[nv]:
                    stack.append((~v,c,-d))
                    stack.append((nv,c,d))
        else:
            col[c][0]+=d
            col[c][1]-=1
            cur_depth-=1
            right[~v]=len(et)
            et.append(~v)
            depth.append(cur_depth)
        while LCA[v]:
            qc,qd,qi=LCA[v].pop()
            diff[qi]-=(col[qc][0]-col[qc][1]*qd)*2
        while U[v]:
            qc,qd,qi=U[v].pop()
            diff[qi]+=-col[qc][0]+col[qc][1]*qd
        while V[v]:
            qc,qd,qi=V[v].pop()
            diff[qi]+=-col[qc][0]+col[qc][1]*qd
    return

EulerTour2(0,N,edge)

for i,(x,y,u,v) in enumerate(Query):
    print(S[left[v]]+S[left[u]]-S[LLCA[i]]*2+diff[i])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
edge=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c,d=map(int1,input().split())
    d+=1
    edge[a].append((b,c,d))
    edge[b].append((a,c,d))
U=defaultdict(list)
V=defaultdict(list)
Query=[]
for i in range(Q):
    x,y,u,v=map(int1,input().split())
    Query.append((x,y,u,v))
    y+=1
    U[u].append((x,y,i))
    V[v].append((x,y,i))

S=[0]*(2*N-1)

def EulerTour(start,n,edges):
    used=[False]*n
    et=[]
    left=[-1]*n
    right=[-1]*n
    depth=[]
    stack=[(start,-1,-1)]
    cur_depth=-1
    while stack:
        v,c,d=stack.pop()
        if et:
            S[len(et)]=S[len(et)-1]+d
        if v>=0:
            used[v]=True
            cur_depth+=1
            left[v]=right[v]=len(et)
            et.append(v)
            depth.append(cur_depth)
            for nv,c,d in edges[v]:
                if not used[nv]:
                    stack.append((~v,c,-d))
                    stack.append((nv,c,d))
        else:
            cur_depth-=1
            right[~v]=len(et)
            et.append(~v)
            depth.append(cur_depth)
    return et,left,depth

et,left,depth=EulerTour(0,N,edge)

class SegmentTree:
    def __init__(self,n,segfunc,ide_ele):
        self.segfunc=segfunc
        self.ide_ele=ide_ele
        self.num=2**(n-1).bit_length()
        self.dat=[ide_ele]*2*self.num
    
    def init(self,iter):
        for i in range(len(iter)):
            self.dat[i+self.num]=iter[i]
        for i in range(self.num-1,0,-1):
            self.dat[i]=self.segfunc(self.dat[i*2],self.dat[i*2+1])
    
    def update(self,k,x):
        k+=self.num
        self.dat[k]=x
        while k:
            k//=2
            self.dat[k]=self.segfunc(self.dat[k*2],self.dat[k*2+1])
    
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num
        q+=self.num-1
        res=self.ide_ele
        while q-p>1:
            if p&1==1:
                res=self.segfunc(res,self.dat[p])
            if q&1==0:
                res=self.segfunc(res,self.dat[q])
                q-=1
            p=(p+1)//2
            q=q//2
        if p==q:
            res=self.segfunc(res,self.dat[p])
        else:
            res=self.segfunc(self.segfunc(res,self.dat[p]),self.dat[q])
        return res

s=SegmentTree(2*N-1,lambda a,b:min(a,b,key=lambda t:t[0]),(INF,INF))
for i in range(2*N-1):
    s.update(i,(depth[i],i))

LCA=defaultdict(list)
LLCA=[-1]*Q
for i,(x,y,u,v) in enumerate(Query):
    p,q=min(left[u],left[v]),max(left[u],left[v])+1
    res=s.query(p,q)
    LCA[et[res[1]]].append((x,y,i))
    LLCA[i]=res[1]

diff=[0]*Q

def EulerTour2(start,n,edges):
    used=[False]*n
    et=[]
    left=[-1]*n
    right=[-1]*n
    depth=[]
    stack=[(start,-1,-1)]
    cur_depth=-1
    col=[[0,0] for _ in range(N)]
    while stack:
        v,c,d=stack.pop()
        if v>=0:
            col[c][0]+=d
            col[c][1]+=1
            used[v]=True
            cur_depth+=1
            left[v]=right[v]=len(et)
            et.append(v)
            depth.append(cur_depth)
            for nv,c,d in edges[v]:
                if not used[nv]:
                    stack.append((~v,c,-d))
                    stack.append((nv,c,d))
        else:
            col[c][0]+=d
            col[c][1]-=1
            cur_depth-=1
            right[~v]=len(et)
            et.append(~v)
            depth.append(cur_depth)
        while LCA[v]:
            qc,qd,qi=LCA[v].pop()
            diff[qi]-=(col[qc][0]-col[qc][1]*qd)*2
        while U[v]:
            qc,qd,qi=U[v].pop()
            diff[qi]+=col[qc][0]-col[qc][1]*qd
        while V[v]:
            qc,qd,qi=V[v].pop()
            diff[qi]-=col[qc][0]-col[qc][1]*qd
    return

EulerTour2(0,N,edge)

for i,(x,y,u,v) in enumerate(Query):
    print(S[left[v]]+S[left[u]]-S[LLCA[i]]*2+diff[i])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
edge=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c,d=map(int1,input().split())
    d+=1
    edge[a].append((b,c,d))
    edge[b].append((a,c,d))
U=defaultdict(list)
V=defaultdict(list)
Query=[]
for i in range(Q):
    x,y,u,v=map(int1,input().split())
    Query.append((x,y,u,v))
    y+=1
    U[u].append((x,y,i))
    V[v].append((x,y,i))

S=[0]*(2*N-1)

def EulerTour(start,n,edges):
    used=[False]*n
    et=[]
    left=[-1]*n
    right=[-1]*n
    depth=[]
    stack=[(start,-1,-1)]
    cur_depth=-1
    while stack:
        v,c,d=stack.pop()
        if et:
            S[len(et)]=S[len(et)-1]+d
        if v>=0:
            used[v]=True
            cur_depth+=1
            left[v]=right[v]=len(et)
            et.append(v)
            depth.append(cur_depth)
            for nv,c,d in edges[v]:
                if not used[nv]:
                    stack.append((~v,c,-d))
                    stack.append((nv,c,d))
        else:
            cur_depth-=1
            right[~v]=len(et)
            et.append(~v)
            depth.append(cur_depth)
    return left,depth

left,depth=EulerTour(0,N,edge)

class SegmentTree:
    def __init__(self,n,segfunc,ide_ele):
        self.segfunc=segfunc
        self.ide_ele=ide_ele
        self.num=2**(n-1).bit_length()
        self.dat=[ide_ele]*2*self.num
    
    def init(self,iter):
        for i in range(len(iter)):
            self.dat[i+self.num]=iter[i]
        for i in range(self.num-1,0,-1):
            self.dat[i]=self.segfunc(self.dat[i*2],self.dat[i*2+1])
    
    def update(self,k,x):
        k+=self.num
        self.dat[k]=x
        while k:
            k//=2
            self.dat[k]=self.segfunc(self.dat[k*2],self.dat[k*2+1])
    
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num
        q+=self.num-1
        res=self.ide_ele
        while q-p>1:
            if p&1==1:
                res=self.segfunc(res,self.dat[p])
            if q&1==0:
                res=self.segfunc(res,self.dat[q])
                q-=1
            p=(p+1)//2
            q=q//2
        if p==q:
            res=self.segfunc(res,self.dat[p])
        else:
            res=self.segfunc(self.segfunc(res,self.dat[p]),self.dat[q])
        return res

s=SegmentTree(2*N-1,lambda a,b:min(a,b,key=lambda t:t[0]),(INF,INF))
for i in range(2*N-1):
    s.update(i,(depth[i],i))

LCA=defaultdict(list)
for i,(x,y,u,v) in enumerate(Query):
    p,q=min(left[u],left[v]),max(left[u],left[v])+1
    res=s.query(p,q)
    LCA[res[1]].append((x,y,i))

diff=[0]*Q

def EulerTour2(start,n,edges):
    used=[False]*n
    et=[]
    left=[-1]*n
    right=[-1]*n
    depth=[]
    stack=[(start,-1,-1)]
    cur_depth=-1
    col=[[0,0] for _ in range(N)]
    while stack:
        v,c,d=stack.pop()
        if v>=0:
            col[c][0]+=d
            col[c][1]+=1
            used[v]=True
            cur_depth+=1
            left[v]=right[v]=len(et)
            et.append(v)
            depth.append(cur_depth)
            for nv,c,d in edges[v]:
                if not used[nv]:
                    stack.append((~v,c,-d))
                    stack.append((nv,c,d))
        else:
            col[c][0]+=d
            col[c][1]-=1
            cur_depth-=1
            right[~v]=len(et)
            et.append(~v)
            depth.append(cur_depth)
        while LCA[v]:
            qc,qd,qi=LCA[v].pop()
            diff[qi]-=(col[qc][0]-col[qc][1]*qd)*2
        while U[v]:
            qc,qd,qi=U[v].pop()
            diff[qi]+=col[qc][0]-col[qc][1]*qd
        while V[v]:
            qc,qd,qi=V[v].pop()
            diff[qi]-=col[qc][0]-col[qc][1]*qd
    return

EulerTour2(0,N,edge)

for i,(x,y,u,v) in enumerate(Query):
    print(S[left[v]]+S[left[u]]-S[res[1]]*2+diff[i])