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

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

Solution code:
import sys
input = sys.stdin.readline

N,Q=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]
Query=[list(map(int,input().split())) for i in range(Q)]
mod=10**9+7

EDGELIST=[dict() for i in range(N+1)]
for x,y,c,l in EDGE:
    EDGELIST[x][y]=(c,l)
    EDGELIST[y][x]=(c,l)
    
# LCA(オイラーツアー＋Segment tree)

DEPTH=[-1]*(N+1)
DEPTH[1]=0

from collections import deque
QUE = deque([1])
QUE2 = deque()
EULER=[]#(i,j)で,(1からツアーで辿った点の深さ,そのindex)

USED=[0]*(N+1)
while QUE:
    x=QUE.pop()
    EULER.append((DEPTH[x],x))
    if USED[x]==1:
        continue
    for to in EDGELIST[x]:
        
        if USED[to]==0:
            DEPTH[to]=DEPTH[x]+1
            QUE2.append(to)
        else:
            QUE.append(to)
    QUE.extend(QUE2)
    QUE2=deque()
 
    USED[x]=1

MINP=[1<<30]*(N+1)
MAXP=[-1]*(N+1)

for ind,(depth,p) in enumerate(EULER):
    MINP[p]=min(MINP[p],ind)
    MAXP[p]=max(MAXP[p],ind)

LEN=len(EULER)

seg_el=1<<(LEN.bit_length())#Segment treeの台の要素数
SEG=[(1<<30,0)]*(2*seg_el)#1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

for i in range(LEN):#Dを対応する箇所へupdate
    SEG[i+seg_el]=EULER[i]

for i in range(seg_el-1,0,-1):#親の部分もupdate
    SEG[i]=min(SEG[i*2],SEG[i*2+1])

def update(n,x,seg_el):#A[n]をxへ更新（反映）
    i=n+seg_el
    SEG[i]=x
    i>>=1#子ノードへ
    
    while i!=0:
        SEG[i]=min(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r):#区間[l,r)に関するminを調べる
    L=l+seg_el
    R=r+seg_el
    ANS=(1<<30,0)

    while L<R:
        if L & 1:
            ANS=min(ANS , SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS=min(ANS , SEG[R])
        L>>=1
        R>>=1

    return ANS

def LCA(l,r):
    return getvalues(min(MINP[l],MINP[r]),max(MAXP[l],MAXP[r])+1)

check=[set() for i in range(N+1)]
for c,l,x,y in Query:
    check[x].add(c)
    check[y].add(c)
    check[LCA(x,y)[1]].add(c)

LENGTH=[0]*(N+1)
LENG=0
C_LENGTH=[0]*N
C_SUM=[0]*N
C_LDICT=dict()
C_SDICT=dict()

for c in check[1]:
    C_LDICT[(1,c)]=0
    C_SDICT[(1,c)]=0
    

for i in range(1,len(EULER)):
    ind=EULER[i][1]
    c,l=EDGELIST[EULER[i-1][1]][ind]
    if EULER[i][0]>EULER[i-1][0]:
        LENG+=l
        C_LENGTH[c]+=l
        C_SUM[c]+=1

        LENGTH[ind]=LENG

        for c in check[ind]:
            C_LDICT[(ind,c)]=C_LENGTH[c]
            C_SDICT[(ind,c)]=C_SUM[c]
            

    else:
        LENG-=l
        C_LENGTH[c]-=l
        C_SUM[c]-=1
        
        
for c,pl,x,y in Query:
    ind=LCA(x,y)[1]
    print(LENGTH[x]+LENGTH[y]-LENGTH[ind]*2+(C_SDICT[x,c]+C_SDICT[y,c]-C_SDICT[ind,c]*2)*pl-(C_LDICT[x,c]+C_LDICT[y,c]-C_LDICT[ind,c]*2))

Submission status: Time Limit Exceeded

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

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

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

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

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

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

rank[0] = 0
queue = [0]

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

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

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

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

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

    return parent[0][a]

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

rank[0] = 0
queue = [0]

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

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

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

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

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

    return parent[0][a]

# Queryの先読み
xyuvl = []
colors = [set() 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
    l = lca(u, v)
    xyuvl.append([x, y, u, v, l])
    colors[u].add(x)
    colors[v].add(x)
    colors[l].add(x)

mem = dict()
dist = [0 for _ in range(N)]
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
        dist[nex] = dist[cur] + d
        C[c] += 1
        D[c] += d
        dfs(nex, cur)
        C[c] -= 1
        D[c] -= d

dfs(0, -1)
   
for x, y, u, v, l in xyuvl :
    dist_ = dist[u] + dist[v] - 2*dist[l]
    C_ = mem[(u, x)][0] + mem[(v, x)][0] - 2*mem[(l, x)][0]
    D_ = mem[(u, x)][1] + mem[(v, x)][1] - 2*mem[(l, 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())
for K in range(18) :
    if 2 ** K >= N :
        break

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

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

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

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

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

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

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

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

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

    return parent[0][a]

# Queryの先読み
xyuvl = []
colors = [set() 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
    l = lca(u, v)
    xyuvl.append([x, y, u, v, l])
    colors[u].add(x)
    colors[v].add(x)
    colors[l].add(x)

# dfs
mem = dict()
dist = [0] * N
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 in path[cur] :
        if nex == pre :
            continue
        c, d = cd[(min(cur, nex), max(cur, nex))]
        dist[nex] = dist[cur] + d
        C[c] += 1
        D[c] += d
        dfs(nex, cur)
        C[c] -= 1
        D[c] -= d

dfs(0, -1)
   
for x, y, u, v, l in xyuvl :
    dist_ = dist[u] + dist[v] - 2*dist[l]
    C_ = mem[(u, x)][0] + mem[(v, x)][0] - 2*mem[(l, x)][0]
    D_ = mem[(u, x)][1] + mem[(v, x)][1] - 2*mem[(l, 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())
for K in range(18) :
    if 2 ** K >= N :
        break

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

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

# 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 in path[cur] :
        if rank[nex] < 0 :
            queue.append(nex)
            parent[0][nex] = cur
            d = cd[(min(cur, nex), max(cur, nex))][1]
            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の先読み
xyuvl = []
colors = [set() 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
    l = lca(u, v)
    xyuvl.append([x, y, u, v, l])
    colors[u].add(x)
    colors[v].add(x)
    colors[l].add(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 in path[cur] :
        if nex == pre :
            continue
        c, d = cd[(min(cur, nex), max(cur, nex))]
        C[c] += 1
        D[c] += d
        dfs(nex, cur)
        C[c] -= 1
        D[c] -= d

dfs(0, -1)
   
for x, y, u, v, l in xyuvl :
    dist_ = dist[u] + dist[v] - 2*dist[l]
    C_ = mem[(u, x)][0] + mem[(v, x)][0] - 2*mem[(l, x)][0]
    D_ = mem[(u, x)][1] + mem[(v, x)][1] - 2*mem[(l, 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())
K = 17

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

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

# 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 in path[cur] :
        if rank[nex] < 0 :
            queue.append(nex)
            parent[0][nex] = cur
            d = cd[(min(cur, nex), max(cur, nex))][1]
            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の先読み
xyuvl = []
colors = [set() 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
    l = lca(u, v)
    xyuvl.append([x, y, u, v, l])
    colors[u].add(x)
    colors[v].add(x)
    colors[l].add(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 in path[cur] :
        if nex == pre :
            continue
        c, d = cd[(min(cur, nex), max(cur, nex))]
        C[c] += 1
        D[c] += d
        dfs(nex, cur)
        C[c] -= 1
        D[c] -= d

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

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,a,b = LI()
    print(min(a*n,b))
    return

#B
def B():
    n,d = LI()
    x = LIR(n)
    f = defaultdict(lambda : 0)
    for i in range(1000000):
        f[i*i] = 1
    ans = 0
    for i in range(n):
        for j in range(i+1,n):
            s = 0
            for k in range(d):
                s += (x[i][k]-x[j][k])**2
            if f[s]:
                ans += 1
    print(ans)
    return

#C
def C():
    l,r = LI()
    if r-l > 2019:
        print(0)
        quit()
    ans = float("inf")
    for i in range(l,r+1):
        for j in range(i+1,r+1):
            if i*j%2019 < ans:
                ans = i*j%2019
    print(ans)
    return

#D
def D():
    n = I()
    a = LI()
    for i in range(n):
        a[i] *= 2
    x = a[0]
    for i in range(1,n):
        if i%2:
            x -= a[i]
        else:
            x += a[i]
    b = [x//2]
    for i in range(n-1):
        b.append(abs(b[-1]-a[i]))
    print(*b)
    return

#E
def E():
    n,k = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    if k == 1:
        if n == 1:
            print(1)
            quit()
        else:
            print(0)
            quit()
    if k == 2:
        print(2)
        quit()
    d = [0]*n
    v.append([])
    v.append([])
    q = deque([0])
    bfs = [1]*n
    bfs[0] = 0
    f = [0]*n
    while q:
        x= q.popleft()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                q.append(y)
    ans = 1
    q = deque([0])
    dp = [None]*n
    dp[0] = k
    bfs = [1]*n
    bfs[0] = 0
    while q:
        x = q.popleft()
        m = len(v[x])
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                dp[y] = k-m
                m -= 1
                q.append(y)
    for i in dp:
        ans *= i
        ans %= mod
    print(ans)
    return

#F
def F():
    def lca(x,y):
        k = depth[x]-depth[y]
        while k > 0:
            x = par[x][int(math.log(k,2))]
            k = depth[x]-depth[y]
        k = -k
        while k > 0:
            y = par[y][int(math.log(k,2))]
            k = depth[y]-depth[x]
        if x == y:
            return x
        for i in range(M+1)[::-1]:
            if i < len(par[x]):
                if par[x][i] != par[y][i]:
                    x = par[x][i]
                    y = par[y][i]
        return par[x][0]

    def euler_tour(x,check,color):
        for i,c,d,k in f[x]:
            if k:
                query[i] -= 2*(-color[c][0]+color[c][1]*d)
            else:
                query[i] += -color[c][0]+color[c][1]*d
        for y,c,d in v[x]:
            if not check[y]:
                check[y] = 1
                color[c][0] += d
                color[c][1] += 1
                euler_tour(y,check,color)
                check[y] = 0
                color[c][0] -= d
                color[c][1] -= 1

    M = 16 #2^17 >= 10^5
    n,Q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b,c,d = LI()
        a -= 1
        b -= 1
        c -= 1
        v[a].append((b,c,d))
        v[b].append((a,c,d))
    par = [[] for i in range(n)]
    dist = [-1]*n
    dist[0] = 0
    depth = [0]*n
    q = deque([0])
    while q:
        x = q.popleft()
        for y,c,d in v[x]:
            if dist[y] < 0:
                dist[y] = dist[x]+d
                depth[y] = depth[x]+1
                q.append(y)
                par[y].append(x)

    l = [i for i in range(n)]
    l.sort(key = lambda x:depth[x])
    for i in range(M):
        k = 1<<(i+1)
        for x in l[::-1]:
            if depth[x] < k:break
            par[x].append(par[par[x][i]][i])
    f = [[] for i in range(n)] #各頂点にqueryの情報を持たせる ← すごい
    query = [0]*Q #オイラーツアー、LCAを用いた距離計算により各クエリの答えを計算
    for i in range(Q):
        x,y,a,b = LI()
        x -= 1
        a -= 1
        b -= 1
        f[a].append((i,x,y,0))
        f[b].append((i,x,y,0))
        l = lca(a,b)
        f[l].append((i,x,y,1))
        query[i] = dist[a]+dist[b]-2*dist[l]
    check = [0]*n
    check[0] = 1
    color = [[0,0] for i in range(n)] #色ごとにオイラーツアーでdist_sum(color),num(color)を計算(その色の距離,その色の数)
    euler_tour(0,check,color)
    for i in query:
        print(i)
    return


#Solve
if __name__ == "__main__":
    F()

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())
K = 17

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

# 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の先読み
xyuvl = []
colors = [set() 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
    l = lca(u, v)
    xyuvl.append([x, y, u, v, l])
    colors[u].add(x)
    colors[v].add(x)
    colors[l].add(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, l in xyuvl :
    dist_ = dist[u] + dist[v] - 2*dist[l]
    C_ = mem[(u, x)][0] + mem[(v, x)][0] - 2*mem[(l, x)][0]
    D_ = mem[(u, x)][1] + mem[(v, x)][1] - 2*mem[(l, 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())
K = 17

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

# 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 = [set() 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].add(x)
    colors[v].add(x)
    colors[lca(u, v)].add(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

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

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

def dfs1(cur, pre) :    
    for nex, _, d in path[cur] :
        if nex == pre :
            continue
        parent[0][nex] = cur
        rank[nex] = rank[cur] + 1
        dist[nex] = dist[cur] + d
        dfs1(nex, cur)

dfs1(0, -1)

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

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

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

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

    return parent[0][a]

# Queryの先読み
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]))

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

def dfs2(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
        dfs2(nex, cur)
        C[c] -= 1
        D[c] -= d

dfs2(0, -1)
   
for x, y, u, v in xyuv :
    lca_ = lca(u, v)
    f1 = dist[u] + dist[v] - 2*dist[lca_]
    f2 = mem[(u, x)][0] + mem[(v, x)][0] - 2*mem[(lca_, x)][0]
    f3 = mem[(u, x)][1] + mem[(v, x)][1] - 2*mem[(lca_, x)][1]
    print(f1 + f2 * y - f3)