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:
import sys
sys.setrecursionlimit(10**7)

def main0(n,g,xyuv):
  # LCAを求める。自作する。
  # 各頂点の深さ。根は深さ0
  depth=[0]*n
  tour=[]
  hatsu=[0]*n
  dist=[0]*n
  tmp=0
  def et(p,v,tour,tmp,pc,pd):
    hatsu[v]=len(tour)-1
    for nv,c,d in g[v]:
      if nv==p:continue
      depth[nv]=depth[v]+1
      tmp+=d
      dist[nv]=tmp
      tour.append((nv,c,d))
      tour=et(v,nv,tour,tmp,c,d)
      tmp-=d
      tour.append((v,c,-d))
    return tour
  tour.append((0,0,0))
  tour=et(-1,0,tour,0,0,0)
  class SegmentTree():
    def __init__(self,size,f=lambda x,y:x+y,default=0):
      self.size=pow(2,(size-1).bit_length())
      self.f=f
      self.default=default
      self.data=[default]*(self.size*2)
    def update(self,i,x):
      i+=self.size
      self.data[i]=x
      while i:
        i>>=1
        self.data[i]=self.f(self.data[i*2],self.data[i*2+1])
    # 区間[l,r)へのクエリ
    def query(self,l,r):
      l,r=l+self.size,r+self.size
      lret,rret=self.default,self.default
      while l<r:
        if l&1:
          lret=self.f(self.data[l],lret)
          l+=1
        if r&1:
          r-=1
          rret=self.f(self.data[r],rret)
        l>>=1
        r>>=1
      return self.f(lret,rret)

  def func(x,y):
    if x[0]<y[0]:return x
    return y
  st=SegmentTree(len(tour),func,(n+1,0))
  for i,x in enumerate(tour):
    v=x[0]
    st.update(i,(depth[v],v))
  def lca(u,v):
    x,y=hatsu[u],hatsu[v]
    if x<y:
      y+=1
    else:
      x,y=y,x
      y+=1
    return st.query(x,y)[1]
  dc={}
  dcary={}
  for i,(v,c,d) in enumerate(tour):
    if c in dc:
      ci=1 if d>0 else -1
      dc[c].append((dc[c][-1][0]+ci,dc[c][-1][1]+d))
      dcary[c].append(i)
    else:
      dc[c]=[(0,0),(1,d)]
      dcary[c]=[0,i]
  ret=[]
  from bisect import bisect_right as bl
  for x,y,u,v in xyuv:
    u,v=u-1,v-1
    w=lca(u,v)
    uvlen=dist[u]+dist[v]-dist[w]*2
    if x not in dc:
      ret.append(uvlen)
      continue
    widx=bl(dcary[x],hatsu[w])-1
    wnum,wsum=dc[x][widx]
    uidx=bl(dcary[x],hatsu[u])-1
    vidx=bl(dcary[x],hatsu[v])-1
    unum,usum=dc[x][uidx]
    vnum,vsum=dc[x][vidx]
    uvsum=usum+vsum-wsum*2
    uvnum=unum+vnum-wnum*2
    #print(uvlen-uvsum+uvnum*y,uvlen,usum,vsum,wsum,uvnum,w)
    ret.append(uvlen-uvsum+uvnum*y)
  return ret

if __name__=='__main__':
  n,q=map(int,input().split())
  abcd=[list(map(int,input().split())) for _ in range(n-1)]
  xyuv=[list(map(int,input().split())) for _ in range(q)]
  g=[[] for _ in range(n)]
  for a,b,c,d in abcd:
    a,b=a-1,b-1
    g[a].append((b,c,d))
    g[b].append((a,c,d))
  ary0=main0(n,g,xyuv)
  print(*ary0,sep='\n')

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self, n, decrement=1):
        self.n = n
        self.edges = [[] for _ in range(n)]
        self.edges2 = [[] for _ in range(n)]
        self.root = None
        self.depth = [-1]*n
        self.size = [1]*n       # 部分木のノードの数
        self.color = [[] for _ in range(n)]
        self.cost = [0]*n
        self.decrement = decrement

    def add_edge(self, u, v):
        u, v = u-self.decrement, v-self.decrement
        self.edges[u].append(v)
        self.edges[v].append(u)

    def add_edges(self, edges):
        for u, v, c, d in edges:
            u, v = u-self.decrement, v-self.decrement
            self.edges[u].append(v)
            self.edges[v].append(u)
            self.edges2[u].append((v, c, d))
            self.edges2[v].append((u, c, d))

    def set_root(self, root):
        root -= self.decrement
        self.root = root
        self.par = [-1]*self.n
        self.depth[root] = 0
        self.order = [root]     # 帰りがけに使う
        next_set = [root]
        while next_set:
            p = next_set.pop()
            for q, c, d in self.edges2[p]:
                if self.depth[q] != -1: continue
                self.par[q] = p
                self.color[c].append(q)
                self.cost[q] = d
                self.depth[q] = self.depth[p]+1
                self.order.append(q)
                next_set.append(q)
        for p in self.order[::-1]:
            for q in self.edges[p]:
                if self.par[p] == q: continue
                self.size[p] += self.size[q]

    def heavy_light_decomposition(self):
        """
        heavy edge を並べてリストにした物を返す (1-indexed if decrement=True)
        """
        # assert self.root is not None
        self.vid = [-1]*self.n
        self.hld = [-1]*self.n
        self.head = [-1]*self.n
        self.head[self.root] = self.root
        self.heavy_node = [-1]*self.n
        next_set = [self.root]
        for i in range(self.n):
            """ for tree graph, dfs ends in N times """
            p = next_set.pop()
            self.vid[p] = i
            self.hld[i] = p+self.decrement
            maxs = 0
            for q in self.edges[p]:
                """ encode direction of Heavy edge into heavy_node """
                if self.par[p] == q: continue
                if maxs < self.size[q]:
                    maxs = self.size[q]
                    self.heavy_node[p] = q
            for q in self.edges[p]:
                """ determine "head" of heavy edge """
                if self.par[p] == q or self.heavy_node[p] == q: continue
                self.head[q] = q
                next_set.append(q)
            if self.heavy_node[p] != -1:
                self.head[self.heavy_node[p]] = self.head[p]
                next_set.append(self.heavy_node[p])
        return self.hld

    def lca(self, u, v):
        # assert self.head is not None
        u, v = u-self.decrement, v-self.decrement
        while True:
            if self.vid[u] > self.vid[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                v = self.par[self.head[v]]
            else:
                return u + self.decrement

    def distance(self, u, v):
        # assert self.head is not None
        p = self.lca(u, v)
        u, v, p = u-self.decrement, v-self.decrement, p-self.decrement
        return self.depth[u] + self.depth[v] - 2*self.depth[p]

    def find(self, u, v, x):
        return self.distance(u,x)+self.distance(x,v)==self.distance(u,v)

    def path_to_list(self, u, v, edge_query=False):
        """
        パス上の頂点の集合を self.hld 上の開区間の集合として表す
        ここで、self.hld は heavy edge を並べて数列にしたものである
        """
        # assert self.head is not None
        u, v = u-self.decrement, v-self.decrement
        while True:
            if self.vid[u] > self.vid[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                yield self.vid[self.head[v]], self.vid[v] + 1
                v = self.par[self.head[v]]
            else:
                yield self.vid[u] + edge_query, self.vid[v] + 1
                return

    def point(self, u):
        return self.vid[u-self.decrement]

class SegmentTree:

    def __init__(self, n, op, e):
        """
        :param n: 要素数
        :param op: 二項演算
        :param e: 単位減
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 1 << (self.n - 1).bit_length()      # st[self.size + i] = array[i]
        self.tree = [self.e] * (self.size << 1)

    def built(self, array):
        """arrayを初期値とするセグメント木を構築"""
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """i 番目の要素を x に更新　(0-indexed) """
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def get(self, l, r):
        """ [l, r)の区間取得の結果を返す　(0-indexed) """
        l += self.size
        r += self.size
        res_l = self.e
        res_r = self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.tree[r], res_r)
            l >>= 1
            r >>= 1
        return self.op(res_l, res_r)

    def max_right(self, l, f):
        """
        以下の条件を両方満たす r を(いずれか一つ)返す
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        if l == self.n: return self.n
        l += self.size
        sm = self.e
        while True:
            while l % 2 == 0: l >>= 1
            if not f(self.op(sm, self.tree[l])):
                while l < self.size:
                    l = 2 * l
                    if f(self.op(sm, self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.tree[l])
            l += 1
            if (l & -l) == l: break
        return self.n

    def min_left(self, r, f):
        """
        以下の条件を両方満たす l を(いずれか一つ)返す
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        if r == 0: return 0
        r += self.size
        sm = self.e
        while True:
            r -= 1
            while r > 1 and (r % 2): r >>= 1
            if not f(self.op(self.tree[r], sm)):
                while r < self.size:
                    r = 2 * r + 1
                    if f(self.op(self.tree[r], sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.tree[r], sm)
            if (r & -r) == r: break
        return 0

    def __iter__(self):
        for a in self.tree[self.size:self.size+self.n]:
            yield a

    def __str__(self):
        return str(self.tree[self.size:self.size+self.n])

#########################################################################################################
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
tree = Tree(N)
edges, query = [], [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c, d = map(int, input().split())
    edges.append((a, b, c-1, d))
for i in range(Q):
    c, y, u, v = map(int, input().split())
    query[c-1].append((y, u, v, i))
tree.add_edges(edges)
tree.set_root(1)
hld = tree.heavy_light_decomposition()

e = (0, 0)
op = lambda x, y: (x[0]+y[0], x[1]+y[1])
st = SegmentTree(N, op, e)
res = [0]*Q
for p in range(N):
    st.update(tree.point(p+1), (tree.cost[p],0))
for c in range(N):
    for p in tree.color[c]:
        st.update(tree.point(p+1), (0,1))
    for y, u, v, i in query[c]:
        for l, r in tree.path_to_list(u, v, True):
            cost, cnt = st.get(l, r)
            res[i] += cost + cnt*y
    for p in tree.color[c]:
        st.update(tree.point(p+1), (tree.cost[p],0))

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

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self, n, decrement=1):
        self.n = n
        self.edges = [[] for _ in range(n)]
        self.edges2 = [[] for _ in range(n)]
        self.root = None
        self.depth = [-1]*n
        self.size = [1]*n       # 部分木のノードの数
        self.color = [[] for _ in range(n)]
        self.cost = [0]*n
        self.decrement = decrement

    def add_edge(self, u, v):
        u, v = u-self.decrement, v-self.decrement
        self.edges[u].append(v)
        self.edges[v].append(u)

    def add_edges(self, edges):
        for u, v, c, d in edges:
            u, v = u-self.decrement, v-self.decrement
            self.edges[u].append(v)
            self.edges[v].append(u)
            self.edges2[u].append((v, c, d))
            self.edges2[v].append((u, c, d))

    def set_root(self, root):
        root -= self.decrement
        self.root = root
        self.par = [-1]*self.n
        self.depth[root] = 0
        self.order = [root]     # 帰りがけに使う
        next_set = [root]
        while next_set:
            p = next_set.pop()
            for q, c, d in self.edges2[p]:
                if self.depth[q] != -1: continue
                self.par[q] = p
                self.color[c].append(q)
                self.cost[q] = d
                self.depth[q] = self.depth[p]+1
                self.order.append(q)
                next_set.append(q)
        for p in self.order[::-1]:
            for q in self.edges[p]:
                if self.par[p] == q: continue
                self.size[p] += self.size[q]

    def heavy_light_decomposition(self):
        """
        heavy edge を並べてリストにした物を返す (1-indexed if decrement=True)
        """
        # assert self.root is not None
        self.vid = [-1]*self.n
        self.hld = [-1]*self.n
        self.head = [-1]*self.n
        self.head[self.root] = self.root
        self.heavy_node = [-1]*self.n
        next_set = [self.root]
        for i in range(self.n):
            """ for tree graph, dfs ends in N times """
            p = next_set.pop()
            self.vid[p] = i
            self.hld[i] = p+self.decrement
            maxs = 0
            for q in self.edges[p]:
                """ encode direction of Heavy edge into heavy_node """
                if self.par[p] == q: continue
                if maxs < self.size[q]:
                    maxs = self.size[q]
                    self.heavy_node[p] = q
            for q in self.edges[p]:
                """ determine "head" of heavy edge """
                if self.par[p] == q or self.heavy_node[p] == q: continue
                self.head[q] = q
                next_set.append(q)
            if self.heavy_node[p] != -1:
                self.head[self.heavy_node[p]] = self.head[p]
                next_set.append(self.heavy_node[p])
        return self.hld

    def lca(self, u, v):
        # assert self.head is not None
        u, v = u-self.decrement, v-self.decrement
        while True:
            if self.vid[u] > self.vid[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                v = self.par[self.head[v]]
            else:
                return u + self.decrement

    def distance(self, u, v):
        # assert self.head is not None
        p = self.lca(u, v)
        u, v, p = u-self.decrement, v-self.decrement, p-self.decrement
        return self.depth[u] + self.depth[v] - 2*self.depth[p]

    def find(self, u, v, x):
        return self.distance(u,x)+self.distance(x,v)==self.distance(u,v)

    def path_to_list(self, u, v, edge_query=False):
        """
        パス上の頂点の集合を self.hld 上の開区間の集合として表す
        ここで、self.hld は heavy edge を並べて数列にしたものである
        """
        # assert self.head is not None
        u, v = u-self.decrement, v-self.decrement
        while True:
            if self.vid[u] > self.vid[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                yield self.vid[self.head[v]], self.vid[v] + 1
                v = self.par[self.head[v]]
            else:
                yield self.vid[u] + edge_query, self.vid[v] + 1
                return

    def point(self, u):
        return self.vid[u-self.decrement]

class SegmentTree:

    def __init__(self, n, op, e):
        """
        :param n: 要素数
        :param op: 二項演算
        :param e: 単位減
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 1 << (self.n - 1).bit_length()      # st[self.size + i] = array[i]
        self.tree = [self.e] * (self.size << 1)

    def built(self, array):
        """arrayを初期値とするセグメント木を構築"""
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """i 番目の要素を x に更新　(0-indexed) """
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def get(self, l, r):
        """ [l, r)の区間取得の結果を返す　(0-indexed) """
        l += self.size
        r += self.size
        res_l = self.e
        res_r = self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.tree[r], res_r)
            l >>= 1
            r >>= 1
        return self.op(res_l, res_r)

    def max_right(self, l, f):
        """
        以下の条件を両方満たす r を(いずれか一つ)返す
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        if l == self.n: return self.n
        l += self.size
        sm = self.e
        while True:
            while l % 2 == 0: l >>= 1
            if not f(self.op(sm, self.tree[l])):
                while l < self.size:
                    l = 2 * l
                    if f(self.op(sm, self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.tree[l])
            l += 1
            if (l & -l) == l: break
        return self.n

    def min_left(self, r, f):
        """
        以下の条件を両方満たす l を(いずれか一つ)返す
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        if r == 0: return 0
        r += self.size
        sm = self.e
        while True:
            r -= 1
            while r > 1 and (r % 2): r >>= 1
            if not f(self.op(self.tree[r], sm)):
                while r < self.size:
                    r = 2 * r + 1
                    if f(self.op(self.tree[r], sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.tree[r], sm)
            if (r & -r) == r: break
        return 0

    def __iter__(self):
        for a in self.tree[self.size:self.size+self.n]:
            yield a

    def __str__(self):
        return str(self.tree[self.size:self.size+self.n])

#########################################################################################################
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
tree = Tree(N)
edges, query = [], [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c, d = map(int, input().split())
    edges.append((a, b, c-1, d))
for i in range(Q):
    c, y, u, v = map(int, input().split())
    query[c-1].append((y, u, v, i))
tree.add_edges(edges)
tree.set_root(1)
hld = tree.heavy_light_decomposition()

e = (0, 0)
op = lambda x, y: (x[0]+y[0], x[1]+y[1])
st = SegmentTree(N, op, e)
res = [0]*Q
for p in range(N):
    st.update(tree.point(p+1), (tree.cost[p],0))
for c in range(N):
    for p in tree.color[c]:
        st.update(tree.point(p+1), (0,1))
    for y, u, v, i in query[c]:
        for l, r in tree.path_to_list(u, v, True):
            cost, cnt = st.get(l, r)
            res[i] += cost + cnt*y
    for p in tree.color[c]:
        st.update(tree.point(p+1), (tree.cost[p],0))

print(*res, sep="\n")

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
他の色ならば長さ0として色毎にグラフを作りたいけど無理よな，持ち方的にも計算量的にも．

木なので道は1通り，LCAとかで最短距離求まる
max(d)=10**4なのは何かできそう？

u,vの経路上にx色のものが(何本あるか,距離合計がいくつか)が必要
(距離，[各色のcount])を持って計算すれば，uv間の距離，uv間に何回x色のものが出たか，は求まるが，x色の辺の距離合計がわからん

色の情報を距離に付与するのも厳しそう．

距離を変更して都度全部計算するのは無理なので，
最後の答えに差分を追加するか，差分更新するか

色を指定されたらその色の辺をO(1)で出せるようにしておいてから
スタート/ゴールの(u,v)を指定された時，「所望の辺を含むか?」を高速に求められれば良いか？
いや，同じ色にM個固まっていると，その色を見るときにM回で大変．例えば全部色1 & (u,v)が毎回変わるとして，Q回のなかで毎回O(N)個の辺を舐めることになる
一応，所望の辺を含むか，はLCAを考えれば行けそう?

u=>vの辺を構築しても，本数がO(N)とかになって結局舐める辺が多い
結局，あるルートに同じ色の辺が大量に固まっていると何もできん

あー，LCAなら(u,v)の距離ではなく，
根からuまで，根からvまで，根からlcaまで，
がそれぞれもとまればできるので，各頂点iに対して，その頂点までの(x色の本数，x色の合計)を持てば良い．
全ての頂点のこれは持てないのでクエリ先読みし，必要なものだけ．これならメモリはO(Q)．

だけど必要な色がN種類あったら距離求めるのN回やるのか？
いや，ある辺を見たとき，更新する色は1色のみだけなのでなんかできる．
色毎に[本数,合計]を持っておき，辺をなめていく
所望のu,v,lcaの頂点がきたときに該当色の[本数，合計]を記憶していく．

"""
def main():
    mod=10**9+7
    N,Q=MI()
    adj=[[]for _ in range(N)]
    from collections import defaultdict
    uv2cd = defaultdict(set)#各辺の色と長さがわかるように
    for _ in range(N-1):
        a,b,c,d=MI()
        a-=1
        b-=1
        c-=1
        adj[a].append(b)
        adj[b].append(a)
        uv2cd[(a,b)]=(c,d)
        uv2cd[(b,a)]=(c,d)
        
    # N: 頂点数
    # G[v]: 頂点vの子頂点 (親頂点は含まない)

    def EulerTour(n, X, i0):
        # 隣接グラフXを消費しながら，親リストPを作りながら進む．
        # i0が根
        
        P = [-1] * n#親
        st = [~i0, i0]
        ct = -1
        ET = []#オイラーツアー 
        ET1 = [0] * n#最初に出てくるとき
        ET2 = [0] * n#最後に出てくるとき
        DE = [0] * n#深さ
        de = -1
        while st:
            #頂点 i を見る
            
            i = st.pop()
            
            #帰り際の処理，ここを入れる場合，オイラーツアーの最後に「-1」がつくので注意
            if i < 0:
                #"""
                #↓ 戻りも数字を足す場合はこれを使う
                ct += 1
                # ↓ 戻りもETに入れる場合はこれを使う
                ET.append(P[~i])#notのnot
                #"""
                ET2[~i] = ct
                de -= 1
                continue
            
            #行きがけの処理
            if i >= 0:
                ET.append(i)
                ct += 1
                if ET1[i] == 0: ET1[i] = ct
                de += 1
                DE[i] = de
                
            for a in X[i][::-1]:
                if a != P[i]:
                    P[a] = i
                    for k in range(len(X[a])):
                        if X[a][k] == i:
                            del X[a][k]
                            break
                    st.append(~a)
                    st.append(a)
        return (ET, ET1, ET2, DE, P)

    # Euler Tour の構築
    S,F,Frev,depth,P=EulerTour(N,adj,0)
    """
    S:訪問順
    F:最初に出てくるとき(頂点の開始番号)
    Frev：最後に出てくるとき(頂点の終了番号)
    """

    # 存在しない範囲は深さが他よりも大きくなるようにする
    INF = (N, None)

    # LCAを計算するクエリの前計算
    M = 2*N
    M0 = 2**(M-1).bit_length()
    data = [INF]*(2*M0)
    for i, v in enumerate(S):
        data[M0-1+i] = (depth[v], i)
    for i in range(M0-2, -1, -1):
        data[i] = min(data[2*i+1], data[2*i+2])

    # LCAの計算 (generatorで最小値を求める)
    def _query(a, b):
        yield INF
        a += M0; b += M0
        while a < b:
            if b & 1:
                b -= 1
                yield data[b-1]
            if a & 1:
                yield data[a-1]
                a += 1
            a >>= 1; b >>= 1

    # LCAの計算 (外から呼び出す関数)
    def query(u, v):
        fu = F[u]; fv = F[v]
        if fu > fv:
            fu, fv = fv, fu
        return S[min(_query(fu, fv+1))[1]]
    
    QL=[]
    v2x = defaultdict(set)#ある頂点と紐づくクエリ．頂点vに来るときに，どの色を計算すべきか格納
    
    for _ in range(Q):
        x,y,u,v=MI()
        x-=1
        u-=1
        v-=1
        lca=query(u,v)
        QL.append((x,y,u,v,lca))
        v2x[(u)].add(x)
        v2x[(v)].add(x)
        v2x[(lca)].add(x)
    
    count_xv = defaultdict(int)#頂点と色を指定された時の出現回数
    dist_xv = defaultdict(int)#頂点と色を指定された時の距離合計
    
    #今見ているやつ
    count=[0]*N#色毎の出現回数
    dist=[0]*N#色毎の累積距離
    used=[0]*N#巡回済か
    used[0]=1
    
    dist_nonchange=[0]*N#色を無視した距離（頂点毎)
    dsum=0
    
    now=0
    for nxt in S[1:-1]:
        x,d=uv2cd[(now,nxt)]
        if used[nxt]==0:#行き
            count[x]+=1
            dist[x]+=d
            used[nxt]=1
            
            dsum+=d
            dist_nonchange[nxt]=dsum
            
            for xx in v2x[nxt]:#各頂点毎に，見なければならない色を見る
                count_xv[(xx,nxt)]=count[xx]
                dist_xv[(xx,nxt)]=dist[xx]
        else:#帰り
            count[x]-=1
            dist[x]-=d

            dsum-=d
        
        # print(now,nxt,x,d,dsum)    
        
        now=nxt
            

    for i in range(Q):
        x,y,u,v,lca=QL[i]
        # 全部の色の合計距離から，その頂点までの該当色分を全部引いて，新たにy*本数を足す
        tempu=dist_nonchange[u] - dist_xv[(x,u)] + y*count_xv[(x,u)]
        tempv=dist_nonchange[v] - dist_xv[(x,v)] + y*count_xv[(x,v)]
        templca=dist_nonchange[lca] - dist_xv[(x,lca)] + y*count_xv[(x,lca)]
        
        ans=tempu + tempv - 2*templca
        
        print(ans)
        # print()
        # print(i,x,y,u,v,lca)
        # print(tempu,tempv,templca,ans)
        # print(dist_nonchange[v], dist_xv[(x,v)], count_xv[(x,v)])

        
        
        
            
    
    

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5+5)
from collections import defaultdict,deque
input = sys.stdin.readline

class LCA:
    def __init__(self,n):
        self.size = n+1
        self.bitlen = n.bit_length()
        self.ancestor = [[0]*self.size for i in range(self.bitlen)]
        self.depth = [-1]*self.size
        self.dis = [-1]*self.size
        self.depth[1] = 0
        self.dis[1] = 0
    def make(self,root):
        q = deque([root])
        while q:
            now = q.popleft()
            for nex,c,w in e[now]:
                if self.depth[nex]>= 0:
                    continue
                self.depth[nex] = self.depth[now]+1
                self.dis[nex] = self.dis[now]+w
                self.ancestor[0][nex] = now
                q.append(nex)
        for i in range(1,self.bitlen):
            for j in range(self.size):
                if self.ancestor[i-1][j] > 0:
                    self.ancestor[i][j] = self.ancestor[i-1][self.ancestor[i-1][j]]
    
    def lca(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.ancestor[s.bit_length()-1][x]
            dif -= s
        while x != y:
            j = 0
            while self.ancestor[j][x] != self.ancestor[j][y]:
                j += 1
            if j == 0:
                return self.ancestor[0][x]
            x = self.ancestor[j-1][x]
            y = self.ancestor[j-1][y]
        return x

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+1)]
ans = []
for i in range(q):
    x,y,u,v = map(int,input().split())
    a = lca.lca(u,v)
    ans.append(lca.dis[u]+lca.dis[v]-2*lca.dis[a])
    Q[u].append((x,y,i,1))
    Q[v].append((x,y,i,1))
    Q[a].append((x,y,i,-2))
count = defaultdict(int)
weight = defaultdict(int)
def dfs1(now,p):
    for x,y,ind,z in Q[now]:
        ans[ind] += z*(y*count[x]-weight[x])
    for nex,c,w in e[now]:
        if nex == p:
            continue
        count[c] += 1
        weight[c] += w
        dfs1(nex,now)
        count[c] -= 1
        weight[c] -= w
dfs1(1,0)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5+5)
from collections import defaultdict,deque
input = sys.stdin.readline
class LCA:

    def __init__(self,n):
        self.size = n+1
        self.bitlen = n.bit_length()
        self.lca = [[0]*self.size for i in range(self.bitlen)]
        self.depth = [-1]*self.size
        self.dis = [-1]*self.size
        self.depth[1] = 0
        self.dis[1] = 0
    def make(self,root):
        q = deque([root])
        while q:
            now = q.popleft()
            for nex,c,w in e[now]:
                if self.depth[nex]>= 0:
                    continue
                self.depth[nex] = self.depth[now]+1
                self.dis[nex] = self.dis[now]+w
                self.lca[0][nex] = now
                q.append(nex)
        for i in range(1,self.bitlen):
            for j in range(self.size):
                if self.lca[i-1][j] > 0:
                    self.lca[i][j] = self.lca[i-1][self.lca[i-1][j]]
    
    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[s.bit_length()-1][x]
            dif -= s
        while x != y:
            j = 0
            while self.lca[j][x] != self.lca[j][y]:
                j += 1
            if j == 0:
                return self.lca[0][x]
            x = self.lca[j-1][x]
            y = self.lca[j-1][y]
        return x

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+1)]
ans = []
for i in range(q):
    x,y,u,v = map(int,input().split())
    a = lca.search(u,v)
    ans.append(lca.dis[u]+lca.dis[v]-2*lca.dis[a])
    Q[u].append((x,y,i,1))
    Q[v].append((x,y,i,1))
    Q[a].append((x,y,i,-2))


count = defaultdict(int)
weight = defaultdict(int)
def dfs1(now,p):
    for x,y,ind,z in Q[now]:
        ans[ind] += z*(y*count[x]-weight[x])
    for nex,c,w in e[now]:
        if nex == p:
            continue
        count[c] += 1
        weight[c] += w
        dfs1(nex,now)
        count[c] -= 1
        weight[c] -= w
    
dfs1(1,0)

for i in ans:
    print(i)