Language: C++

#ifdef OJ_MISC_OFFLINE

#include "prolog.h"

#else
#define LOG
#define PRINT
#define LCERR
#include <iostream>
auto optimize_cpp_stdio = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::setvbuf(stdout, nullptr, _IOFBF, BUFSIZ);
    return 0;
}();
#endif

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>

namespace {

using namespace std;

struct Edge {
    int from;
    int to;
    int c;
    int w;
};

struct Query {
    int c;
    int w;
    int n1;
    int n2;
};

struct PathSum {
    int total_w = 0;
    unordered_map<int, int> clr_cnt;
    unordered_map<int, int> clr_w;
};

struct Input {
    vector<Edge> edges;
    vector<Query> queries;
};

void dfs_root_undirected_tree(const vector<vector<Edge>>& graph, int cur, int parent,
                              vector<Edge>& res) {
    for (const auto& ed : graph[cur]) {
        if (ed.to == parent)
            continue;
        res.emplace_back(ed);
        dfs_root_undirected_tree(graph, ed.to, cur, res);
    }
}

vector<Edge> root_undirected_tree(const vector<Edge>& edges) {
    const int N = edges.size() + 1;
    vector<vector<Edge>> graph(N + 1);
    for (const auto& e : edges) {
        graph[e.from].emplace_back(e);
        Edge rev_e = e;
        swap(rev_e.from, rev_e.to);
        graph[e.to].emplace_back(rev_e);
    }
    vector<Edge> res;
    dfs_root_undirected_tree(graph, 1, -1, res);
    return res;
}

class CustomizedRangeMinSegTree {
public:
    struct Node {
        int min = 0;
        int idx = 0;
    };

    const int INF = 1000000000;

    explicit CustomizedRangeMinSegTree(const vector<int>& pnums)
            : N(pnums.size()), nums(pnums), st(4 * N) {
        build(0, 0, nums.size());
    }

    /**
     * Query for the value and (one of the) position of the minimum on range [l, h)
     * @return value, position
     */
    pair<int, int> query(int ql, int qh) { return query(0, 0, nums.size(), ql, qh); }

private:

    pair<int, int> query(int id, int l, int h, int ql, int qh) {
        if (h <= ql || qh <= l) return make_pair(INF, 0);
        if (ql <= l && h <= qh) return make_pair(st[id].min, st[id].idx);
        int mid = l + (h - l) / 2;
        auto lret = query(lc(id), l, mid, ql, qh);
        auto rret = query(rc(id), mid, h, ql, qh);
        return lret.first <= rret.first ? lret : rret;
    }

    void build(int id, int l, int h) {
        Node& cn = st[id];
        if (l + 2 > h) {
            st[id] = Node{nums[l], l};
            return;
        }
        int mid = l + (h - l) / 2;
        build(lc(id), l, mid);
        build(rc(id), mid, h);
        cn = st[lc(id)].min <= st[rc(id)].min ? st[lc(id)] : st[rc(id)];
    }

    static int lc(int id) { return id * 2 + 1; }

    static int rc(int id) { return id * 2 + 2; }

    const int N;
    const vector<int>& nums;
    vector<Node> st;
};

class LCATreeWithPathSum {
public:
    struct Node { // Node of the input tree, not the segment tree
        vector<Edge> edges;
        PathSum psum;
        int depth = 0;
        int euc_idx = -1; // Index of the first visit of this node on the euclidean tour
    };

    explicit LCATreeWithPathSum(const vector<Edge>& dir_edges) : N(int(dir_edges.size() + 1)) {
        build_tree(dir_edges);
        annotate_depth(root, 0);
        PathSum psum_buf;
        annotate_path_sum(root, psum_buf);
        build_euc_tour(root);
        rmin = make_unique<CustomizedRangeMinSegTree>(euc_depth);
    }

    int lca(int n1, int n2) const {
        if (n1 == n2) return n1;
        int l = tree[n1].euc_idx;
        int h = tree[n2].euc_idx;
        if (l > h) swap(l, h);
        h += 1;
        auto rmin_ret = rmin->query(l, h);
        return euc_tour[rmin_ret.second];
    }

    const PathSum& path_sum(int n) const { return tree[n].psum; }

private:

    void build_tree(const vector<Edge>& edges) {
        tree.resize(N + 1); // 0 is not used
        vector<int> indegree(N + 1); // for finding root
        for (const auto& e : edges) {
            tree[e.from].edges.emplace_back(e);
            indegree[e.to] += 1;
        }
        for (int i = 1; i <= N; ++i) {
            if (indegree[i] == 0) {
                root = i;
                break;
            }
        }
    }

    void annotate_depth(int cur, int depth) {
        tree[cur].depth = depth;
        for (const auto& e : tree[cur].edges) {
            annotate_depth(e.to, depth + 1);
        }
    }

    void annotate_path_sum(int cur, PathSum& cur_sum) {
        tree[cur].psum = cur_sum;
        for (const auto& e : tree[cur].edges) {
            cur_sum.total_w += e.w;
            cur_sum.clr_cnt[e.c] += 1;
            cur_sum.clr_w[e.c] += e.w;
            annotate_path_sum(e.to, cur_sum);
            if(cur_sum.clr_cnt[e.c] == 1) {
                cur_sum.clr_cnt.erase(e.c);
                cur_sum.clr_w.erase(e.c);
            } else {
                cur_sum.clr_cnt[e.c] -= 1;
                cur_sum.clr_w[e.c] -= e.w;
            }
            cur_sum.total_w -= e.w;
        }
    }

    void build_euc_tour(int cur) {
        tree[cur].euc_idx = int(euc_tour.size());
        auto add_cur_to_tour = [this, cur]() {
            euc_tour.emplace_back(cur);
            euc_depth.emplace_back(tree[cur].depth);
        };
        add_cur_to_tour();
        for (const auto& e : tree[cur].edges) {
            build_euc_tour(e.to);
            add_cur_to_tour();
        }
    }

    const int N;
    vector<Node> tree;
    int root = 0;
    vector<int> euc_tour;
    vector<int> euc_depth;
    unique_ptr<CustomizedRangeMinSegTree> rmin;
};

int colored_path_sum(const PathSum& psum, int xclr, int xw) {
    int res = psum.total_w;
    auto iter = psum.clr_cnt.find(xclr);
    if (iter == psum.clr_cnt.end()) {
        return res;
    }
    res -= psum.clr_w.at(xclr);
    res += iter->second * xw;
    return res;
}

vector<int> colorful_tree(const Input& input) {
    vector<Edge> directed_edges = root_undirected_tree(input.edges);
    LCATreeWithPathSum lcatree{directed_edges};
    vector<int> result;
    for (const Query& q : input.queries) {
        int lca = lcatree.lca(q.n1, q.n2);
        int p1 = colored_path_sum(lcatree.path_sum(q.n1), q.c, q.w);
        int p2 = colored_path_sum(lcatree.path_sum(q.n2), q.c, q.w);
        int plca = colored_path_sum(lcatree.path_sum(lca), q.c, q.w);
        LOG("lca:{} p1:{} p2:{} plca:{}\n", lca, p1, p2, plca);
        result.emplace_back(p1 + p2 - 2 * plca);
    }
    return result;
}

int solve() {
    // handle IO here
    size_t N, Q;
    cin >> N >> Q;
    Input input;
    input.edges.resize(N - 1);
    input.queries.resize(Q);
    for (size_t i = 0; i < N - 1; ++i) {
        Edge& e = input.edges[i];
        cin >> e.from >> e.to >> e.c >> e.w;
    }
    for (size_t i = 0; i < Q; ++i) {
        Query& q = input.queries[i];
        cin >> q.c >> q.w >> q.n1 >> q.n2;
    }

    auto result = colorful_tree(input);
    for (int r : result) {
        cout << r << '\n';
    }
    return 0;
}

} // anonymous namespace

#ifdef OJ_MISC_OFFLINE

#include "epilog.h"

#else

int main() {
    return solve();
}

#endif


Compiler output:
a.cc:224:5: error: 'unique_ptr' does not name a type
  224 |     unique_ptr<CustomizedRangeMinSegTree> rmin;
      |     ^~~~~~~~~~
a.cc: In constructor '{anonymous}::LCATreeWithPathSum::LCATreeWithPathSum(const std::vector<{anonymous}::Edge>&)':
a.cc:149:9: error: 'rmin' was not declared in this scope
  149 |         rmin = make_unique<CustomizedRangeMinSegTree>(euc_depth);
      |         ^~~~
a.cc:149:16: error: 'make_unique' was not declared in this scope
  149 |         rmin = make_unique<CustomizedRangeMinSegTree>(euc_depth);
      |                ^~~~~~~~~~~
a.cc:28:1: note: 'std::make_unique' is defined in header '<memory>'; this is probably fixable by adding '#include <memory>'
   27 | #include <vector>
  +++ |+#include <memory>
   28 | 
a.cc:149:53: error: expected primary-expression before '>' token
  149 |         rmin = make_unique<CustomizedRangeMinSegTree>(euc_depth);
      |                                                     ^
a.cc: In member function 'int {anonymous}::LCATreeWithPathSum::lca(int, int) const':
a.cc:158:25: error: 'rmin' was not declared in this scope
  158 |         auto rmin_ret = rmin->query(l, h);
      |                         ^~~~