Language: C++

#include <bits/stdc++.h>
using namespace std;
#pragma GCC Optimize("Ofast")
#define int long long

struct HLDecomposition {
    int n,pos;
    vector<vector<int> > G;
    vector<int> vid, head, sub, hvy, par, dep, inv, type;

    HLDecomposition(){}
    HLDecomposition(int sz):
            n(sz),pos(0),G(n),
            vid(n,-1),head(n),sub(n,1),hvy(n,-1),
            par(n),dep(n),inv(n),type(n){}

    void add_edge(int u, int v) {
        G[u].push_back(v);
        G[v].push_back(u);
    }

    void build(vector<int> rs=vector<int>(1,0)) {
        int c=0;
        for(int r:rs){
            dfs(r);
            bfs(r, c++);
        }
    }

    void dfs(int rt) {
        using T = pair<int,int>;
        stack<T> st;
        par[rt]=-1;
        dep[rt]=0;
        st.emplace(rt,0);
        while(!st.empty()){
            int v=st.top().first;
            int &i=st.top().second;
            if(i<(int)G[v].size()){
                int u=G[v][i++];
                if(u==par[v]) continue;
                par[u]=v;
                dep[u]=dep[v]+1;
                st.emplace(u,0);
            }else{
                st.pop();
                int res=0;
                for(int u:G[v]){
                    if(u==par[v]) continue;
                    sub[v]+=sub[u];
                    if(res<sub[u]) res=sub[u],hvy[v]=u;
                }
            }
        }
    }

    void bfs(int r,int c) {
        int &k=pos;
        queue<int> q({r});
        while(!q.empty()){
            int h=q.front();q.pop();
            for(int i=h;i!=-1;i=hvy[i]) {
                type[i]=c;
                vid[i]=k++;
                inv[vid[i]]=i;
                head[i]=h;
                for(int j:G[i])
                    if(j!=par[i]&&j!=hvy[i]) q.push(j);
            }
        }
    }

    // for_each(vertex)
    // [l,r] <- attention!!
    void for_each(int u, int v, const function<void(int, int)>& f) {
        while(1){
            if(vid[u]>vid[v]) swap(u,v);
            f(max(vid[head[v]],vid[u]),vid[v]);
            if(head[u]!=head[v]) v=par[head[v]];
            else break;
        }
    }

    // for_each(edge)
    // [l,r] <- attention!!
    void for_each_edge(int u, int v, const function<void(int, int)>& f) {
        while(1){
            if(vid[u]>vid[v]) swap(u,v);
            if(head[u]!=head[v]){
                f(vid[head[v]],vid[v]);
                v=par[head[v]];
            } else{
                if(u!=v) f(vid[u]+1,vid[v]);
                break;
            }
        }
    }

    int lca(int u,int v){
        while(1){
            if(vid[u]>vid[v]) swap(u,v);
            if(head[u]==head[v]) return u;
            v=par[head[v]];
        }
    }

    int distance(int u,int v){
        return dep[u]+dep[v]-2*dep[lca(u,v)];
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    HLDecomposition hld(n);
    map<pair<int, int>, int> cs, ds;
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--, b--;
        cs[{min(a, b), max(a, b)}] = c;
        ds[{min(a, b), max(a, b)}] = d;
        hld.add_edge(a, b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    hld.build();
    vector<int> C(n), D(n), depth(n);
    function<void(int, int, int)> dfs = [&](int v, int p, int d) {
        depth[v] = d;
        for (int s : adj[v]) {
            if (s != p) {
                C[s] = cs[{min(v, s), max(v, s)}];
                D[s] = ds[{min(v, s), max(v, s)}];
                dfs(s, v, d + ds[{min(v, s), max(v, s)}]);
            }
        }
    };
    dfs(0, -1, 0);
    vector<int> Chld(n), Dhld(n);
    for (int i = 0; i < n; i++) {
        Chld[hld.vid[i]] = C[i];
        Dhld[hld.vid[i]] = D[i];
    }

    vector<vector<pair<int, int>>> Dsum(n), Nsum(n);
    for (int i = 0; i < n; i++) {
        int x = C[i];
        if (Dsum[x].empty()) {
            Dsum[x].emplace_back(i, D[i]);
            Nsum[x].emplace_back(i, 1);
        } else {
            Dsum[x].emplace_back(i, Dsum[x].back().second + D[i]);
            Nsum[x].emplace_back(i, Nsum[x].back().second + 1);
        }
    }

    auto dist = [&](int u, int v) {
        int w = hld.lca(u, v);
        return depth[u] + depth[v] - 2 * depth[w];
    };
    int reg;
    int X;
    // [i, j]
    auto color_sum = [&](int i, int j) -> void {
        if (Dsum[X].empty()) {
            return;
        }
        auto itr = lower_bound(Dsum[X].begin(), Dsum[X].end(), make_pair(j, 0));
        int R;
        if (itr->first == j) {
            R = itr->second;
        } else {
            if (itr == Dsum[X].begin()) R = 0;
            else {
                --itr;
                R = itr->second;
            }
        }
        if (i == 0) {
            reg += R;
            return;
        };
        auto itl = lower_bound(Dsum[X].begin(), Dsum[X].end(), make_pair(i - 1, 0));
        int L;
        if (itl->first == i - 1) {
            L = itl->second;
        } else {
            if (itl == Dsum[X].begin()) L = 0;
            else {
                --itl;
                L = itl->second;
            }
        }
        reg += R - L;
    };
    auto color_num = [&](int i, int j) -> void {
        if (Nsum[X].empty()) {
            return;
        }
        auto itr = lower_bound(Nsum[X].begin(), Nsum[X].end(), make_pair(j, 0));
        int R;
        if (itr->first == j) {
            R = itr->second;
        } else {
            if (itr == Nsum[X].begin()) R = 0;
            else {
                --itr;
                R = itr->second;
            }
        }
        if (i == 0) {
            reg += R;
            return;
        }
        auto itl = lower_bound(Nsum[X].begin(), Nsum[X].end(), make_pair(i - 1, 0));
        int L;
        if (itl->first == i - 1) {
            L = itl->second;
        } else {
            if (itl == Nsum[X].begin()) L = 0;
            else {
                --itl;
                L = itl->second;
            }
        }
        reg += R - L;
    };

    while (q--) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        u--, v--;
        int ret = dist(u, v);
        X = x;
        reg = 0;
        hld.for_each_edge(u, v, color_sum);
        ret -= reg;
        reg = 0;
        hld.for_each_edge(u, v, color_num);
        ret += reg * y;
        cout << ret << endl;
    }
}

Compiler output:
In file included from /usr/include/c++/14/bits/stl_algobase.h:71,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_less_val::operator()(_Iterator, _Value&) const [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<long long int, long long int>*, std::vector<std::pair<long long int, long long int> > >; _Value = const std::pair<long long int, int>]':
/usr/include/c++/14/bits/stl_algobase.h:1504:14:   required from '_ForwardIterator std::__lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<pair<long long int, long long int>*, vector<pair<long long int, long long int> > >; _Tp = pair<long long int, int>; _Compare = __gnu_cxx::__ops::_Iter_less_val]'
 1504 |           if (__comp(__middle, __val))
      |               ~~~~~~^~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:1539:32:   required from '_ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = __gnu_cxx::__normal_iterator<pair<long long int, long long int>*, vector<pair<long long int, long long int> > >; _Tp = pair<long long int, int>]'
 1539 |       return std::__lower_bound(__first, __last, __val,
      |              ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
 1540 |                                 __gnu_cxx::__ops::__iter_less_val());
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:173:31:   required from here
  173 |         auto itr = lower_bound(Dsum[X].begin(), Dsum[X].end(), make_pair(j, 0));
      |                    ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:69:22: error: no match for 'operator<' (operand types are 'std::pair<long long int, long long int>' and 'const std::pair<long long int, int>')
   69 |       { return *__it < __val; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:1241:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __normal_iterator<_IteratorL, _Container>&, const __normal_iterator<_IteratorR, _Container>&)'
 1241 |     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1241:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:69:22: note:   'std::pair<long long int, long long int>' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
   69 |       { return *__it < __val; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1249:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __normal_iterator<_Iterator, _Container>&, const __normal_iterator<_Iterator, _Container>&)'
 1249 |     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1249:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:69:22: note:   'std::pair<long long int, long long int>' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
   69 |       { return *__it < __val; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/14/regex:68,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:181:
/usr/include/c++/14/bits/regex.h:1143:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator<(const sub_match<_BiIter>&, const sub_match<_BiIter>&)'
 1143 |     operator<(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1143:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:69:22: note:   'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   69 |       { return *__it < __val; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1224:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const sub_match<_BiIter>&)'
 1224 |     operator<(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1224:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:69:22: note:   'std::pair<long long int, long long int>' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
   69 |       { return *__it < __val; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1317:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(const sub_match<_BiIter>&, __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1317 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1317:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:69:22: note:   'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   69 |       { return *__it < __val; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1391:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type*, const sub_match<_BiIter>&)'
 1391 |     operator<(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1391:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:69:22: note:   'const std::pair<long long int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   69 |       { return *__it < __val; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1485:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1485 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1485:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:69:22: note:   'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   69 |       { return *__it < __val; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1560:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type&, const sub_match<_BiIter>&)'
 1560 |     operator<(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1560:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:69:22: note:   'const std::pair<long long int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   69 |       { return *__it < __val; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1660:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1660 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1660:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:69:22: note:   'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   69 |       { return *__it < __val; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:64:
/usr/include/c++/14/bits/stl_pair.h:1045:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
 1045 |     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1045:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:69:22: note:   deduced conflicting types for parameter '_T2' ('long long int' and 'int')
   69 |       { return *__it < __val; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:448:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  448 |     operator<(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:448:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:69:22: note:   'std::pair<long long int, long long int>' is not derived from 'const std::reverse_iterator<_Iterator>'
   69 |       { return *__it < __val; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  493 |     operator<(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:69:22: note:   'std::pair<long long int, long long int>' is not derived from 'const std::reverse_iterator<_Iterator>'
   69 |       { return *__it < __val; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1694:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const move_iterator<_IteratorL>&, const move_it