test/yukicoder/1038.test.cpp

• View this file on GitHub
• Last update: 2025-11-24 18:49:07+09:00
• Problem: https://yukicoder.me/problems/no/1038

Depends on

• build/pch/stdc++.hpp
• library/algebra/group/Add.hpp
• library/algebra/lazy/AddMin.hpp
• library/algebra/monoid/Min.hpp
• library/graph/Graph.hpp
• library/segtree/DualSegmentTree.hpp
• library/tree/CentroidDecomposition.hpp
• library/tree/Tree.hpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/1038"
#include <bits/stdc++.h>

#define REP(i, n) for (int i = 0; i < (n); i++)

#include "library/algebra/lazy/AddMin.hpp"
#include "library/segtree/DualSegmentTree.hpp"
#include "library/tree/CentroidDecomposition.hpp"
#include "library/tree/Tree.hpp"

using ll = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;
    Tree T(n);
    T.scan(1);

    std::vector<std::tuple<int, int, int>> query(q);
    std::vector<std::vector<int>> query_at(n);
    REP (i, q) {
        auto &[x, y, z] = query[i];
        std::cin >> x >> y >> z;
        x--;
        query_at[x].push_back(i);
    }

    std::vector<ll> ans(q, 0);
    DualSegmentTree<LazyAddMin<ll>> seg(std::vector<ll>(n, 0));
    std::vector<int> D(n), events;
    int root;

    auto next_val = [&](int d, const auto &e) {
        for (int id : query_at[e.to])
            events.push_back(id);
        return D[e.to] = d + 1;
    };
    auto action = [&](int d, bool add) {
        if (d == 0)
            next_val(-1, Edge{root, root});
    };
    auto finish = [&](bool add) {
        std::ranges::sort(events);
        for (int id : events) {
            const auto &[x, y, z] = query[id];
            int d = D[x];
            if (add)
                ans[id] += seg[d];
            else
                ans[id] -= seg[d];
            if (d <= y)
                seg.apply(0, y - d + 1, z);
        }
        for (int id : events) {
            const auto &[x, y, z] = query[id];
            int d = D[x];
            if (d <= y)
                seg.apply(0, y - d + 1, -z);
        }
        events.resize(0);
    };

    CentroidDecomposition CD(T);
    for (root = 0; root < n; root++)
        CD.calc(root, 0, next_val, action, finish);

    REP (i, q)
        std::cout << ans[i] << "\n";
}

#line 1 "test/yukicoder/1038.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1038"
#include <bits/stdc++.h>

#define REP(i, n) for (int i = 0; i < (n); i++)

#line 2 "library/algebra/group/Add.hpp"
template<typename X>
struct GroupAdd {
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr void Rchop(X&x, const X&y){ x+=y; }
  static constexpr void Lchop(const X&x, X&y){ y+=x; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, long long n) noexcept { return X(n) * x; }
  static constexpr X unit() { return X(0); }
  static constexpr bool commute = true;
};
#line 1 "library/algebra/monoid/Min.hpp"
template <typename X> struct MonoidMin {
    using value_type = X;
    static constexpr X op(const X &x, const X &y) noexcept {
        return std::min(x, y);
    }
    static constexpr void Rchop(X &x, const X &y) {
        if (x > y)
            x = y;
    }
    static constexpr void Lchop(const X &x, X &y) {
        if (y > x)
            y = x;
    }
    static constexpr X unit() { return std::numeric_limits<X>::max() / 2; }
    static constexpr bool commute = true;
};
#line 4 "library/algebra/lazy/AddMin.hpp"
template <typename X> struct LazyAddMin {
    using MX = MonoidMin<X>;
    using MF = GroupAdd<X>;
    static constexpr X mapping(const X &f, const X &x) { return f + x; }
};
#line 1 "library/segtree/DualSegmentTree.hpp"
template <typename Lazy> class DualSegmentTree {
    using MX = typename Lazy::MX;
    using MF = typename Lazy::MF;
    using X = typename MX::value_type;
    using F = typename MF::value_type;
    int n, log, size;
    std::vector<X> dat;
    std::vector<F> laz;

    void point_apply(int k, const F &f) {
        if (k < size)
            MF::Lchop(f, laz[k]);
        else
            dat[k - size] = Lazy::mapping(f, dat[k - size]);
    }
    void push(int k) {
        point_apply(2 * k, laz[k]);
        point_apply(2 * k + 1, laz[k]);
        laz[k] = MF::unit();
    }
    void thrust(int k) {
        for (int i = log; i; i--)
            push(k >> i);
    }

  public:
    DualSegmentTree() : DualSegmentTree(0) {}
    DualSegmentTree(int n) : DualSegmentTree(std::vector<X>(n, MX::unit())) {}
    DualSegmentTree(const std::vector<X> &v) : n(v.size()), dat(v) {
        for (log = 1; (1 << log) < n; log++) {
        }
        size = 1 << log;
        laz.assign(size, MF::unit());
    }

    void set(int p, X x) {
        assert(0 <= p and p < n);
        thrust(p + size);
        dat[p] = x;
    }

    X operator[](int p) {
        assert(0 <= p and p < n);
        thrust(p + size);
        return dat[p];
    }

    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r)
            return;
        thrust(l += size);
        thrust(r += size - 1);
        for (int L = l, R = r + 1; L < R; L >>= 1, R >>= 1) {
            if (L & 1)
                point_apply(L++, f);
            if (R & 1)
                point_apply(--R, f);
        }
    }
};
#line 1 "library/tree/CentroidDecomposition.hpp"
template <typename TREE> class CentroidDecomposition {
    TREE T;
    std::vector<int> sz, pre, timing;

    int find_centroid(int v) {
        std::vector<int> S{v};
        pre[v] = -1;
        for (int i = 0; i < S.size(); i++) {
            const int u = S[i];
            sz[u] = 1;
            for (int to : T[u]) {
                if (to == pre[u] || ~timing[to])
                    continue;
                pre[to] = u;
                S.push_back(to);
            }
        }
        int SZ = S.size();
        std::ranges::reverse(S);
        for (int u : S) {
            if (SZ - sz[u] <= SZ / 2)
                return u;
            sz[pre[u]] += sz[u];
        }
        assert(false);
        return -1;
    };

  public:
    std::vector<int> order;
    CentroidDecomposition(TREE T) : T(T), sz(T.n), pre(T.n), timing(T.n, -1) {
        order.reserve(T.n);
        std::queue<int> que;
        que.push(0);
        while (que.size()) {
            int c = find_centroid(que.front());
            que.pop();
            timing[c] = order.size();
            order.push_back(c);
            for (int to : T[c])
                if (timing[to] < 0)
                    que.push(to);
        }
    }

    template <typename X, typename F, typename G, typename H>
    void calc(int root, X initial_val, const F &next_val, const G &action,
              const H &finish) {
        std::queue<std::tuple<int, int, X>> que;

        auto f = [&](int v_, int pre_, X val_, bool is_all) {
            que.emplace(v_, pre_, val_);
            while (que.size()) {
                auto [v, pre, val] = que.front();
                que.pop();
                action(val, is_all);
                for (const auto &e : T[v]) {
                    if (e.to == pre || timing[e.to] <= timing[root])
                        continue;
                    que.emplace(e.to, v, next_val(val, e));
                }
            }
            finish(is_all);
        };

        for (const auto &e : T[root])
            if (timing[e.to] > timing[root])
                f(e.to, root, next_val(initial_val, e), false);

        f(root, -1, initial_val, true);
    }

    template <typename X, typename F, typename G, typename H>
    void all_calc(X initial_val, const F &next_val, const G &action,
                  const H &finish) {
        for (int i = 0; i < T.n; i++)
            calc(i, initial_val, next_val, action, finish);
    }
};
#line 2 "library/graph/Graph.hpp"

#line 6 "library/graph/Graph.hpp"

struct Edge {
    int from, to;
    Edge() = default;
    Edge(int from, int to) : from(from), to(to) {}
    operator int() const { return to; }
};

struct Graph {
    int n;
    using edge_type = Edge;
    std::vector<edge_type> edges;

  protected:
    std::vector<int> in_deg;
    bool prepared;
    class OutgoingEdges {
        Graph *g;
        int l, r;

      public:
        OutgoingEdges(Graph *g, int l, int r) : g(g), l(l), r(r) {}
        edge_type *begin() { return &(g->edges[l]); }
        edge_type *end() { return &(g->edges[r]); }
        edge_type &operator[](int i) { return g->edges[l + i]; }
        int size() const { return r - l; }
    };
    class ConstOutgoingEdges {
        const Graph *g;
        int l, r;

      public:
        ConstOutgoingEdges(const Graph *g, int l, int r) : g(g), l(l), r(r) {}
        const edge_type *begin() const { return &(g->edges[l]); }
        const edge_type *end() const { return &(g->edges[r]); }
        const edge_type &operator[](int i) const { return g->edges[l + i]; }
        int size() const { return r - l; }
    };

  public:
    OutgoingEdges operator[](int v) {
        assert(prepared);
        return {this, in_deg[v], in_deg[v + 1]};
    }
    const ConstOutgoingEdges operator[](int v) const {
        assert(prepared);
        return {this, in_deg[v], in_deg[v + 1]};
    }

    bool is_prepared() const { return prepared; }

    Graph() : n(0), in_deg(1, 0), prepared(false) {}
    Graph(int n) : n(n), in_deg(n + 1, 0), prepared(false) {}
    Graph(int n, int m, bool directed = false, int indexed = 1)
        : n(n), in_deg(n + 1, 0), prepared(false) {
        scan(m, directed, indexed);
    }

    void resize(int n) { n = n; }

    void add_arc(int from, int to) {
        assert(!prepared);
        assert(0 <= from and from < n and 0 <= to and to < n);
        edges.emplace_back(from, to);
        in_deg[from + 1]++;
    }
    void add_edge(int u, int v) {
        add_arc(u, v);
        add_arc(v, u);
    }
    void add_arc(const edge_type &e) { add_arc(e.from, e.to); }
    void add_edge(const edge_type &e) { add_edge(e.from, e.to); }

    void scan(int m, bool directed = false, int indexed = 1) {
        edges.reserve(directed ? m : 2 * m);
        while (m--) {
            int u, v;
            std::cin >> u >> v;
            u -= indexed;
            v -= indexed;
            if (directed)
                add_arc(u, v);
            else
                add_edge(u, v);
        }
        build();
    }

    void build() {
        assert(!prepared);
        prepared = true;
        for (int v = 0; v < n; v++)
            in_deg[v + 1] += in_deg[v];
        std::vector<edge_type> new_edges(in_deg.back());
        auto counter = in_deg;
        for (auto &&e : edges)
            new_edges[counter[e.from]++] = e;
        edges = new_edges;
    }

    void graph_debug() const {
#ifndef __LOCAL
        return;
#endif
        assert(prepared);
        for (int from = 0; from < n; from++) {
            std::cerr << from << ";";
            for (int i = in_deg[from]; i < in_deg[from + 1]; i++)
                std::cerr << edges[i].to << " ";
            std::cerr << "\n";
        }
    }
};
#line 3 "library/tree/Tree.hpp"
struct Tree : Graph {
    using Graph::Graph;
    Tree() = default;
    int root = -1;
    std::vector<int> DFS, BFS, depth;

    void scan_root(int indexed = 1) {
        for (int i = 1; i < n; i++) {
            int p;
            std::cin >> p;
            add_edge(p - indexed, i);
        }
        build();
    }
    void scan(int indexed = 1) {
        Graph::scan(n - 1, false, indexed);
        build();
    }

    edge_type &parent(int v) {
        assert(~root and root != v);
        return (*this)[v][0];
    }
    const edge_type &parent(int v) const {
        assert(~root and root != v);
        return (*this)[v][0];
    }

    OutgoingEdges son(int v) {
        assert(~root);
        if (v == root)
            return {this, in_deg[v], in_deg[v + 1]};
        return {this, in_deg[v] + 1, in_deg[v + 1]};
    }

  private:
    void dfs(int v, int pre = -1) {
        for (auto &e : (*this)[v]) {
            if (e.to == pre)
                std::swap((*this)[v][0], e);
            else {
                depth[e.to] = depth[v] + 1;
                dfs(e.to, v);
            }
        }
        DFS.push_back(v);
    }

  public:
    void build(int r = 0) {
        if (!is_prepared())
            Graph::build();
        if (~root) {
            assert(r == root);
            return;
        }
        root = r;
        depth = std::vector<int>(n, 0);
        DFS.reserve(n);
        BFS.reserve(n);
        dfs(root);
        std::queue<int> que;
        que.push(root);
        while (que.size()) {
            int p = que.front();
            que.pop();
            BFS.push_back(p);
            for (const auto &e : son(p))
                que.push(e.to);
        }
    }
};
#line 10 "test/yukicoder/1038.test.cpp"

using ll = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;
    Tree T(n);
    T.scan(1);

    std::vector<std::tuple<int, int, int>> query(q);
    std::vector<std::vector<int>> query_at(n);
    REP (i, q) {
        auto &[x, y, z] = query[i];
        std::cin >> x >> y >> z;
        x--;
        query_at[x].push_back(i);
    }

    std::vector<ll> ans(q, 0);
    DualSegmentTree<LazyAddMin<ll>> seg(std::vector<ll>(n, 0));
    std::vector<int> D(n), events;
    int root;

    auto next_val = [&](int d, const auto &e) {
        for (int id : query_at[e.to])
            events.push_back(id);
        return D[e.to] = d + 1;
    };
    auto action = [&](int d, bool add) {
        if (d == 0)
            next_val(-1, Edge{root, root});
    };
    auto finish = [&](bool add) {
        std::ranges::sort(events);
        for (int id : events) {
            const auto &[x, y, z] = query[id];
            int d = D[x];
            if (add)
                ans[id] += seg[d];
            else
                ans[id] -= seg[d];
            if (d <= y)
                seg.apply(0, y - d + 1, z);
        }
        for (int id : events) {
            const auto &[x, y, z] = query[id];
            int d = D[x];
            if (d <= y)
                seg.apply(0, y - d + 1, -z);
        }
        events.resize(0);
    };

    CentroidDecomposition CD(T);
    for (root = 0; root < n; root++)
        CD.calc(root, 0, next_val, action, finish);

    REP (i, q)
        std::cout << ans[i] << "\n";
}

Back to top page