Language: C++

#include<bits/stdc++.h>
#define ll long long
#define S second
#define F first

using namespace std;

const int N = 2e5 + 5, M = 2 * N;

int tree[1<<19];
int head[N], to[M], nxt[M], ne, n;
int nodeToINdex[M], indexToNode[M], depth[N], parent[N], dfsOrder;
ll color[M], dist[M];

void init()
{
    memset(head + 1, -1, n * sizeof(head[0]));
    ne = 1;
}

void addEdge(int u, int v, int c, int d)
{
    nxt[ne] = head[u];
    to[ne] = v;
    color[ne] = c;
    dist[ne] = d;
    head[u] = ne++;
}

void addBiEdge(int u, int v, int c, int d)
{
    addEdge(u, v, c, d);
    addEdge(v, u, c, d);
}

void build(int ni = 0, int ns = 0, int ne = dfsOrder - 1)
{
   if(ns == ne)
   {
       tree[ni] = ns;
       return;
   }
   int lf = ni * 2 + 1, rt = lf + 1, mid = ns + (ne - ns)/2;
   build(lf, ns, mid);
   build(rt, mid + 1, ne);
   tree[ni] = depth[indexToNode[tree[lf]]] < depth[indexToNode[tree[rt]]] ? tree[lf] : tree[rt];
}

int RMQ(int qs, int qe, int ni = 0, int ns = 0, int ne = dfsOrder - 1)
{
    if(qs > ne or qe < ns) return dfsOrder;
    if(ns >= qs and ne <= qe) return tree[ni];
    int lf = ni * 2 + 1, rt = lf + 1, mid = ns + (ne - ns)/2;
    int LF = RMQ(qs, qe, lf, ns, mid);
    int RT = RMQ(qs, qe, rt, mid + 1, ne);
    return depth[indexToNode[LF]] < depth[indexToNode[RT]] ? LF : RT;
}

int LCA(int u, int v)
{
    u = nodeToINdex[u];
    v = nodeToINdex[v];
    if(u > v) swap(u, v);
    return indexToNode[RMQ(u, v)];
}

struct node;
extern node* empty;

struct node
{
    ll sum, cnt;
    node *lf, *rt;
    node():sum(0), cnt(0), lf(this), rt(this){}
    node(ll sum, ll cnt, node* lf = empty, node* rt = empty):sum(sum), cnt(cnt), lf(lf), rt(rt){}
};

node* empty = new node();
node* roots[1<<18];

node* insert(ll val, ll inc, node*& cur, int ns = 0, int ne = N)
{
    if(val < ns or val > ne) return cur;
    if(ns == ne) return new node(cur->sum + inc, cur->cnt + 1);
    ll mid = ns + (ne - ns) / 2;
    node* LF = insert(val, inc, cur->lf, ns, mid);
    node* RT = insert(val, inc, cur->rt, mid + 1, ne);
    return new node(LF->sum + RT->sum, LF->cnt + RT->cnt, LF, RT);
}

pair<ll, ll> query(int qs, int qe, node*& u, node*& v, node*& lca, int ns = 0, int ne = N)
{
   if(qs > ne or qe < ns) return {0, 0};
   if(ns >= qs and ne <= qe) return {u->sum + v->sum - 2 * lca->sum, u->cnt + v->cnt - 2 * lca->cnt};
   int mid = ns + (ne - ns) / 2;
   auto LF = query(qs, qe, u->lf, v->lf, lca->lf, ns, mid);
   auto RT = query(qs, qe, u->rt, v->rt, lca->rt, mid + 1, ne);
   return {LF.F + RT.F, LF.S + RT.S};
}

void dfs(int u, int pe)
{
    indexToNode[nodeToINdex[u] = dfsOrder++] = u;
    if(u > 1) roots[u] = insert(color[pe], dist[pe], roots[parent[u]]);
    for(int e = head[u] ; ~e ; e = nxt[e])
    {
        int v = to[e];
        if(v == parent[u]) continue;
        parent[v] = u;
        depth[v] = depth[u] + 1;
        dfs(v, e);
        indexToNode[dfsOrder++] = u;
    }
}

int main()
{
    roots[1] = empty;
    int u, v, q, c, d, x, y;
    scanf("%d%d", &n, &q);
    init();
    for(int i = 1 ; i < n ; i++)
    {
       scanf("%d%d%d%d", &u, &v, &c, &d);
       addBiEdge(u, v, c, d);
    }
    dfs(1, 0);
    indexToNode[dfsOrder] = n + 1;
    depth[n + 1] = 1e9;
    build();
    while(q--)
    {
        scanf("%d%d%d%d", &x, &y, &u, &v);
        int lca = LCA(u, v);
        auto cur = query(x, x, roots[u], roots[v], roots[lca]);
        printf("%lld\n", (roots[u]->sum + roots[v]->sum - 2 * roots[lca]->sum) - cur.F + cur.S * y);
    }
    return 0;
}


Compiler output:
a.cc:75:37: error: reference to 'empty' is ambiguous
   75 |     node(ll sum, ll cnt, node* lf = empty, node* rt = empty):sum(sum), cnt(cnt), lf(lf), rt(rt){}
      |                                     ^~~~~
In file included from /usr/include/c++/14/string:53,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:1:
/usr/include/c++/14/bits/range_access.h:302:5: note: candidates are: 'template<class _Tp> constexpr bool std::empty(initializer_list<_Tp>)'
  302 |     empty(initializer_list<_Tp> __il) noexcept
      |     ^~~~~
/usr/include/c++/14/bits/range_access.h:292:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr bool std::empty(const _Tp (&)[_Nm])'
  292 |     empty(const _Tp (&)[_Nm]) noexcept
      |     ^~~~~
/usr/include/c++/14/bits/range_access.h:282:5: note:                 'template<class _Container> constexpr decltype (__cont.empty()) std::empty(const _Container&)'
  282 |     empty(const _Container& __cont) noexcept(noexcept(__cont.empty()))
      |     ^~~~~
a.cc:68:14: note:                 'node* empty'
   68 | extern node* empty;
      |              ^~~~~
a.cc:75:55: error: reference to 'empty' is ambiguous
   75 |     node(ll sum, ll cnt, node* lf = empty, node* rt = empty):sum(sum), cnt(cnt), lf(lf), rt(rt){}
      |                                                       ^~~~~
/usr/include/c++/14/bits/range_access.h:302:5: note: candidates are: 'template<class _Tp> constexpr bool std::empty(initializer_list<_Tp>)'
  302 |     empty(initializer_list<_Tp> __il) noexcept
      |     ^~~~~
/usr/include/c++/14/bits/range_access.h:292:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr bool std::empty(const _Tp (&)[_Nm])'
  292 |     empty(const _Tp (&)[_Nm]) noexcept
      |     ^~~~~
/usr/include/c++/14/bits/range_access.h:282:5: note:                 'template<class _Container> constexpr decltype (__cont.empty()) std::empty(const _Container&)'
  282 |     empty(const _Container& __cont) noexcept(noexcept(__cont.empty()))
      |     ^~~~~
a.cc:68:14: note:                 'node* empty'
   68 | extern node* empty;
      |              ^~~~~
a.cc: In function 'int main()':
a.cc:118:16: error: reference to 'empty' is ambiguous
  118 |     roots[1] = empty;
      |                ^~~~~
/usr/include/c++/14/bits/range_access.h:302:5: note: candidates are: 'template<class _Tp> constexpr bool std::empty(initializer_list<_Tp>)'
  302 |     empty(initializer_list<_Tp> __il) noexcept
      |     ^~~~~
/usr/include/c++/14/bits/range_access.h:292:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr bool std::empty(const _Tp (&)[_Nm])'
  292 |     empty(const _Tp (&)[_Nm]) noexcept
      |     ^~~~~
/usr/include/c++/14/bits/range_access.h:282:5: note:                 'template<class _Container> constexpr decltype (__cont.empty()) std::empty(const _Container&)'
  282 |     empty(const _Container& __cont) noexcept(noexcept(__cont.empty()))
      |     ^~~~~
a.cc:78:7: note:                 'node* empty'
   78 | node* empty = new node();
      |       ^~~~~