Language: C++

#include<iostream>
#include<vector>
#include<map>
#include<functional>
#include<algorithm>

template<typename Compare>
struct rmqf {
  int const BS = 16;
  int const MASK = (1<<BS) -1;

  Compare comp;
  std::vector<int> small;
  std::vector<std::vector<int>> large;

  static int ctz(int x) { return __builtin_ctz(x); }
  static int msb(int x) { return 31-__builtin_clz(x); }
  int min(int l, int r) const { return comp(r, l)? r: l; } // retrurn index l when eq

  rmqf(){}
  rmqf(int N, Compare&& c): comp(c), large(1) { init(N); }
  void init(int N) {
    std::vector<int> st;
    st.reserve(BS);
    small.reserve(N);
    large.reserve(28);
    large[0].reserve(N/BS);

    // make small and large[0]
    for(int i = 0; i < N; ++i) {
      while(!st.empty() && comp(i, st.back())) st.pop_back();
      small.push_back(st.empty()? 0: small[st.back()]);
      small.back() |= 1 << i%BS;
      st.push_back(i);
      if((i%BS) == BS-1) {
        large[0].push_back(st[0]);
        st.resize(0);
      }
    }

    // double large
    for(int i = 1; i+i <= N/BS; i += i) {
      std::vector<int> v;
      std::vector<int>const& pv = large.back();
      int sz = N/BS - (i+i-1);
      v.reserve(sz);
      for(int k = 0; k < sz; ++k) v.push_back(min(pv[k], pv[k+i]));
      large.emplace_back(std::move(v));
    }
  }

  // min for [l, r]; should hold <= l <= r < N
  int min_closed(int l, int r) const {
    auto mcs = [&](int l, int r)->int { return ctz(small[r] & MASK << l); };
    int lb = l/BS + 1, rb = r/BS;
    if(lb < rb) { // include at least one whole block
      int p = msb(rb - lb);
      int lh = min((lb-1)*BS + mcs(l%BS, lb*BS-1), large[p][lb]);
      int rh = min(large[p][rb-(1<<p)], rb*BS + ctz(small[r]));
      return min(lh, rh);
    }
    if(lb == rb) { // adjacent block
      return min((lb-1)*BS + mcs(l%BS, lb*BS-1), lb*BS + ctz(small[r]));
    }
    return rb*BS + mcs(l%BS, r); // in-block
  }
};

template<typename Edge>
struct euler_tour {
  using Graph = std::vector<std::vector<Edge>>;
  using Comp = std::function<bool(int,int)>;
  using Op = std::function<void(int,Edge const&,int)>;
  Graph& G;
  int N;
  std::vector<int> par, in, out, dep, vs;
  Op pre, post;
  rmqf<Comp> r;

  euler_tour(Graph& Graph, Op&& pre_f, Op&& post_f):
    G(Graph), N(G.size()), par(N), in(N), out(N),
    dep(N*2-1), vs(N*2-1), pre(pre_f), post(post_f) {
    int k = 0;
    dfs(0, -1, 0, k);
    r.comp = [&dep = std::as_const(dep)](int l, int r)->bool
      { return dep[l] < dep[r]; };
    r.init(dep.size());
  }

  void dfs(int v, int p, int d, int &k) {
    par[v] = p;
    vs[in[v] = k] = v;
    dep[k++] = d;
    for(auto& e: G[v]) if(e.to != p) {
      pre(v, e, k);
      dfs(e.to, v, d+1, k);
      vs[k] = v;
      dep[k++] = d;
      post(v, e, k-1);
    }
    out[v] = k;
  }

  int lca(int u, int v) {
    int in_u = in[u], in_v = in[v];
    if(in_u > in_v) std::swap(in_u, in_v);
    return vs[r.min_closed(in_u, in_v)];
  }
};

struct edge {
  int to, color, cost;
  edge(){}
  edge(int t, int c, int d): to(t), color(c), cost(d) {}
};

int main() {
  int N, Q; std::cin >> N >> Q;
  std::vector<std::vector<edge>> G(N);
  for(int i = 0; i < N-1; ++i) {
    int a, b, c, d; std::cin >> a >> b >> c >> d; --a; --b; --c;
    G[a].emplace_back(b, c, d);
    G[b].emplace_back(a, c, d);
  }
  std::vector<int> dist(N);
  dist[0] = 0;
  std::vector<std::pair<int,int>> pzv(1, {0, 0});
  std::vector<std::vector<std::pair<int,int>>> num(N,pzv), sum(N,pzv);
  std::vector<int> ntmp(N,0), stmp(N,0);
  euler_tour<edge> et(G,
    [&](int v, edge const& e, int k)->void {
      dist[e.to] = dist[v] + e.cost;
      sum[e.color].emplace_back(k, stmp[e.color] += e.cost);
      num[e.color].emplace_back(k, ++ntmp[e.color]);
    },
    [&](int v, edge const& e, int k)->void {
      sum[e.color].emplace_back(k, stmp[e.color] -= e.cost);
      num[e.color].emplace_back(k, --ntmp[e.color]);
    }
  );

  for(int i = 0; i < Q; ++i) {
    int x, y, u, v; std::cin >> x >> y >> u >> v; --x; --u; --v;
    auto calc_dist = [&](int w)->int {
      if(w == 0) return 0;
      int res = dist[w], k = et.in[w];
      auto it = std::partition_point(num[x].begin(), num[x].end(),
                  [&](auto const& p){ return p.first <= k; });
      res += (it-1)->second*y;
      it = std::partition_point(sum[x].begin(), sum[x].end(),
             [&](auto const& p){ return p.first <= k; });
      res -= (it-1)->second;
      return res;
    };
    int ans = calc_dist(u)+calc_dist(v)-2*calc_dist(et.lca(u,v));
    std::cout << ans << "\n";
  }
  return 0;
}


Compiler output:
a.cc: In constructor 'euler_tour<Edge>::euler_tour(Graph&, Op&&, Op&&)':
a.cc:85:27: error: 'as_const' is not a member of 'std'
   85 |     r.comp = [&dep = std::as_const(dep)](int l, int r)->bool
      |                           ^~~~~~~~
a.cc:6:1: note: 'std::as_const' is defined in header '<utility>'; this is probably fixable by adding '#include <utility>'
    5 | #include<algorithm>
  +++ |+#include <utility>
    6 | 
a.cc: In lambda function:
a.cc:86:16: error: 'this' was not captured for this lambda function
   86 |       { return dep[l] < dep[r]; };
      |                ^~~
a.cc:86:25: error: 'this' was not captured for this lambda function
   86 |       { return dep[l] < dep[r]; };
      |                         ^~~
a.cc: In instantiation of 'euler_tour<Edge>::euler_tour(Graph&, Op&&, Op&&) [with Edge = edge; Graph = std::vector<std::vector<edge> >; Op = std::function<void(int, const edge&, int)>]':
a.cc:140:3:   required from here
  140 |   );
      |   ^
a.cc:86:16: error: 'this' was not captured for this lambda function
   86 |       { return dep[l] < dep[r]; };
      |                ^~~
a.cc:86:16: error: invalid use of non-static data member 'euler_tour<edge>::dep'
a.cc:76:34: note: declared here
   76 |   std::vector<int> par, in, out, dep, vs;
      |                                  ^~~
a.cc:86:25: error: 'this' was not captured for this lambda function
   86 |       { return dep[l] < dep[r]; };
      |                         ^~~
a.cc:86:25: error: invalid use of non-static data member 'euler_tour<edge>::dep'
a.cc:76:34: note: declared here
   76 |   std::vector<int> par, in, out, dep, vs;
      |                                  ^~~