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

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

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

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

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

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

        if u == v:
            return u

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

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

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

    dfs(root)
    make_parent(level)

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

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

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

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

n, q = map(int, input().split())
f(n,q)

Submission status: Accepted

Solution code:
def f_colorful_tree(N, Q, Edges, Queries):
    # 参考: https://atcoder.jp/contests/abc133/submissions/6316420
    # https://atcoder.jp/contests/abc133/submissions/6321437

    import sys
    sys.setrecursionlimit(10**5)

    # 入力は1-basedだが、頂点と色の番号については0-basedで考える(以降も同様)
    tree = [[] for _ in range(N)]
    for a, b, c, d in Edges:
        tree[a - 1].append((b - 1, c - 1, d))
        tree[b - 1].append((a - 1, c - 1, d))

    """Least Common Ancestorを求めるための前処理"""
    depth_from_root = [0] * N
    # [k][v]: 頂点vから2**k個根に近づいたときの頂点番号(根の親は-1とする)
    # 頂点数Nが最大 10**5 なので、2**k >= 10**5 となる k=17 までリストを確保する
    parent_to_root = [[-1] * N for _ in range(18)]
    distance_from_root = [0] * N

    def dfs1(parent, current, depth, distance):
        depth_from_root[current] = depth
        parent_to_root[0][current] = parent
        distance_from_root[current] = distance
        for child, _, dist in tree[current]:  # 色についての情報は必要ない
            if child != parent:
                dfs1(current, child, depth + 1, distance + dist)

    dfs1(-1, 0, 0, 0)
    for i in range(17):
        for j in range(N):
            parent_to_root[i + 1][j] = parent_to_root[i][parent_to_root[i][j]]

    def least_common_ancestor(a, b):
        # editorialと同じことをやる
        if depth_from_root[a] > depth_from_root[b]:
            a, b = b, a
        for i in range(18):
            if (depth_from_root[b] - depth_from_root[a]) & (1 << i):
                b = parent_to_root[i][b]
        if a == b:
            return a
        for i in range(18)[::-1]:
            if parent_to_root[i][a] != parent_to_root[i][b]:
                a = parent_to_root[i][a]
                b = parent_to_root[i][b]
        return parent_to_root[0][a]

    """先読みした(オフライン)クエリに対して解を求める"""
    ans = [0] * Q
    v_need = [[] for i in range(N)]
    for i, (x, y, u, v) in enumerate(Queries):
        # 色xの辺の距離を一律yに変更したとき、頂点u-v間の距離を求める
        lca = least_common_ancestor(u - 1, v - 1)
        # 色の情報を必要としているのは u, v, lca の3点
        # それぞれの点に対して以下の情報を格納する
        # (何番目のクエリか, どの色の距離を変えるか, 変える距離はいくらか, 係数)
        # 係数は u-v間の距離 = 根-u + 根-v - 2 * 根-LCA(u, v) であることを反映
        v_need[u - 1].append((i, x - 1, y, 1))
        v_need[v - 1].append((i, x - 1, y, 1))
        v_need[lca].append((i, x - 1, y, -2))

    color_appear = [0] * N  # [c]: 今訪れている頂点までに色cは何回現れたか
    color_distance = [0] * N  # [c]: 今訪れている頂点まででの色cの辺の距離の和

    def dfs2(parent, current):
        nonlocal color_distance
        for i, x, y, coefficient in v_need[current]:
            ans[i] += (coefficient * (distance_from_root[current]
                                      - color_distance[x] + y * color_appear[x]))
        for child, x, y in tree[current]:
            if child == parent:
                continue
            color_appear[x] += 1
            color_distance[x] += y
            dfs2(current, child)
            # 例えば a→b→c→b→d と移動したことを a→b→d とみなす
            # (オイラーツアーのようにする)ため、戻ってきたなら引く
            color_appear[x] -= 1
            color_distance[x] -= y

    dfs2(-1, 0)
    return '\n'.join(map(str, ans))

N, Q = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(N - 1)]
Queries = [[int(i) for i in input().split()] for j in range(Q)]
print(f_colorful_tree(N, Q, Edges, Queries))

Submission status: Accepted

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

N_q=[[] for i in range(N+1)]
for ind,(c,pl,x,y) in enumerate(Query):
    N_q[x].append([ind,c,pl,1])
    N_q[y].append([ind,c,pl,1])
    N_q[LCA(x,y)[1]].append([ind,c,pl,0])

ANS=[0]*Q

LENG=0
C_LENGTH=[0]*N
C_SUM=[0]*N

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

        for que,c,pl,boo in N_q[ind]:
            if boo==1:
                ANS[que]+=LENG+C_SUM[c]*pl-C_LENGTH[c]

            else:
                ANS[que]-=(LENG+C_SUM[c]*pl-C_LENGTH[c])*2
            
    else:
        LENG-=l
        C_LENGTH[c]-=l
        C_SUM[c]-=1

for ans in ANS:
    print(ans)

Submission status: Accepted

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)

N_q=[[] for i in range(N+1)]
for ind,(c,pl,x,y) in enumerate(Query):
    N_q[x].append([ind,c,pl,1])
    N_q[y].append([ind,c,pl,1])
    N_q[LCA(x,y)[1]].append([ind,c,pl,0])

ANS=[0]*Q

LENG=0
C_LENGTH=[0]*N
C_SUM=[0]*N

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

        for que,c,pl,boo in N_q[ind]:
            if boo==1:
                ANS[que]+=LENG+C_SUM[c]*pl-C_LENGTH[c]

            else:
                ANS[que]-=(LENG+C_SUM[c]*pl-C_LENGTH[c])*2
            
    else:
        LENG-=l
        C_LENGTH[c]-=l
        C_SUM[c]-=1

for ans in ANS:
    print(ans)

Submission status: Accepted

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

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

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

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

# parent, now_point, depth, dist

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

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

dfs(-1,0,0,0)

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

# LCAの準備が完了

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

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

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

for i in ans:
    print(i)

Submission status: Accepted

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

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
from bisect import bisect_right as br
N, K = map(int, input().split())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y, c, d = map(int, input().split())
    X[x-1].append((y-1, c-1, d))
    X[y-1].append((x-1, c-1, d))

P = [(-1, 0, 0)] * N
Q = [(0, 0, 0)]
R = []
ET = []
ct = 0
CT = [0] * (N-1) * 2
CTA = [-1]* N
BT = [[[-1], [0], [0]] for _ in range(N)]
while Q:
    i, c, d = Q.pop()
    if i < 0:
        BT[c][0].append(ct)
        BT[c][1].append(BT[c][1][-1]-1)
        BT[c][2].append(BT[c][2][-1]-d)
        ct += 1
        continue
    R.append(i)
    if i > 0:
        if CTA[i] < 0: CTA[i] = ct
        BT[c][0].append(ct)
        BT[c][1].append(BT[c][1][-1]+1)
        BT[c][2].append(BT[c][2][-1]+d)
        ct += 1
    
    for a, c, d in X[i][::-1]:
        if a != P[i][0]:
            ET.append((i, a))
            P[a] = (i, c, d)
            for k in range(len(X[a])):
                if X[a][k][0] == i:
                    del X[a][k]
                    break
            Q.append((~a, c, d))
            Q.append((a, c, d))

L = [[0, 0] for _ in range(N)]
for i in R[1:]:
    p, c, d = P[i]
    L[i][0] = L[p][0] + 1
    L[i][1] = L[p][1] + d

D = [[P[i][0] for i in range(N)]] + [[-1]*N for _ in range(16)]
for k in range(1, 17):
    for i in range(N):
        a = D[k-1][i]
        if a > 0:
            D[k][i] = D[k-1][a]

def lca(u0, v0):
    u, v = u0, v0
    if L[u][0] < L[v][0]:
        u, v = v, u
    
    while L[u][0] > L[v][0]:
        d = L[u][0] - L[v][0]
        dd = d.bit_length() - 1
        u = D[dd][u]
    if u == v:
        return u
    
    for i in range(17)[::-1]:
        if D[i][u] != D[i][v]:
            u = D[i][u]
            v = D[i][v]
    
    return D[0][u]
    

def calc(x, y, w):
    aa = br(BT[x][0], CTA[w]) - 1
    c = BT[x][1][aa]
    d = BT[x][2][aa]
    return L[w][1] + c*y - d

for _ in range(K):
    x, y, u, v = map(int, input().split())
    x, u, v = x-1, u-1, v-1
    ll = lca(u, v)
    print(calc(x, y, u) + calc(x, y, v) - 2*calc(x, y, ll))

Submission status: Accepted

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)]
    par[0].append(0)
    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: Accepted

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 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 = 17 #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)]
    par[0].append(0)
    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):
        for x in l:
            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: Accepted

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

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

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

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

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

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

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