test/AOJ/GRL_5_E.test.cpp

• View this file on GitHub
• Last update: 2025-11-24 18:49:07+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_E

Depends on

• build/pch/stdc++.hpp
• library/algebra/Reverse.hpp
• library/algebra/group/Add.hpp
• library/algebra/group/CntSum.hpp
• library/algebra/lazy/AddSum.hpp
• library/algebra/lazy/Reverse.hpp
• library/graph/Graph.hpp
• library/segtree/LazySegmentTree.hpp
• library/tree/HLD.hpp
• library/tree/Tree.hpp
• library/tree/TreeLazy.hpp

Code

#define PROBLEM                                                                \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_E"
#include <bits/stdc++.h>

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

#include "library/algebra/lazy/AddSum.hpp"
#include "library/tree/Tree.hpp"
#include "library/tree/TreeLazy.hpp"
using ll = long long;

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

    int n;
    std::cin >> n;

    Tree t(n);
    REP (i, n) {
        int k;
        std::cin >> k;
        REP (_, k) {
            int c;
            std::cin >> c;
            t.add_edge(i, c);
        }
    }
    t.build(0);

    TreeLazy<Tree, LazyAddSum<ll>> TL(t, cnt_init(n, 0LL));
    // 辺の情報は子に持たせる
    // 各頂点 v について、根から 1 移動した点が必要
    // Tree に jump を実装してないので無理くり求める
    std::vector<int> root2(n, -1);
    for (int v : t.BFS) {
        if (v == 0)
            continue;
        int p = t.parent(v).to;
        if (p == 0)
            root2[v] = v;
        else
            root2[v] = root2[p];
    }

    int q;
    std::cin >> q;
    REP (_, q) {
        int c;
        std::cin >> c;
        if (c) {
            int u;
            std::cin >> u;
            std::cout << TL.path_prod(u, root2[u]).first << "\n";
        } else {
            int v, w;
            std::cin >> v >> w;
            TL.path_apply(v, root2[v], w);
        }
    }
}

#line 1 "test/AOJ/GRL_5_E.test.cpp"
#define PROBLEM                                                                \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_E"
#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/group/CntSum.hpp"
template <typename X> struct GroupCntSum {
    using P = std::pair<X, X>;
    using value_type = P;
    static constexpr P op(const P &x, const P &y) {
        return {x.first + y.first, x.second + y.second};
    }
    static constexpr void Rchop(P &x, const P &y) {
        x.first += y.first;
        x.second += y.second;
    }
    static constexpr void Lchop(const P &x, P &y) {
        y.first += x.first;
        y.second += x.second;
    }
    static constexpr P inverse(const P &x) { return {-x.fi, -x.se}; }
    static constexpr P unit() { return {0, 0}; }
    static constexpr bool commute = true;
};
template <typename X> std::vector<std::pair<X, X>> cnt_init(int n, const X &x) {
    return std::vector<std::pair<X, X>>(n, {x, 1});
}
template <typename X>
std::vector<std::pair<X, X>> cnt_init(const std::vector<X> &v) {
    int n = v.size();
    std::vector<std::pair<X, X>> res(n);
    for (int i = 0; i < n; i++)
        res[i] = {v[i], 1};
    return res;
}
#line 4 "library/algebra/lazy/AddSum.hpp"
template <typename X> struct LazyAddSum {
    using MX = GroupCntSum<X>;
    using MF = GroupAdd<X>;
    using S = typename MX::value_type;
    static constexpr S mapping(const X &f, const S &x) {
        return {x.first + f * x.second, x.second};
    }
};
#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 2 "library/algebra/Reverse.hpp"
template<typename Algebra>
struct AlgebraReverse:Algebra{
  using X=typename Algebra::value_type;
  static constexpr X op(const X& x, const X& y){ return Algebra::op(y,x); }
  static constexpr void Rchop(X&x,const X&y){ Algebra::Lchop(y,x); }
  static constexpr void Lchop(const X&x,X&y){ Algebra::Rchop(y,x); }
};
#line 3 "library/algebra/lazy/Reverse.hpp"
template <typename Lazy> struct LazyReverse : Lazy {
    using MX = AlgebraReverse<typename Lazy::MX>;
};
#line 2 "library/segtree/LazySegmentTree.hpp"

template <typename Lazy> class LazySegmentTree {
    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;

    X reflect(int k) {
        if (k < size)
            return Lazy::mapping(laz[k], dat[k]);
        return dat[k];
    }
    void point_apply(int k, const F &f) {
        if (k < size)
            MF::Lchop(f, laz[k]);
        else
            dat[k] = Lazy::mapping(f, dat[k]);
    }
    void push(int k) {
        dat[k] = reflect(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);
    }
    void update(int i) { dat[i] = MX::op(reflect(2 * i), reflect(2 * i + 1)); }
    void recalc(int k) {
        while (k >>= 1)
            update(k);
    }

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

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

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

    X prod(int L, int R) {
        assert(0 <= L and L <= R and R <= n);
        if (L == R)
            return MX::unit();
        thrust(L += size);
        thrust((R += size - 1)++);
        X vl = MX::unit(), vr = MX::unit();
        while (L < R) {
            if (L & 1)
                MX::Rchop(vl, reflect(L++));
            if (R & 1)
                MX::Lchop(reflect(--R), vr);
            L >>= 1, R >>= 1;
        }
        return MX::op(vl, vr);
    }

    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);
        }
        recalc(l);
        recalc(r);
    }
};
#line 2 "library/tree/HLD.hpp"
template <typename TREE> struct HLD {
    int n;
    TREE T;
    std::vector<int> sz, head, id, id2, rev_id;
    bool prepared;
    HLD(TREE T_)
        : T(T_), n(T_.n), sz(n), head(n), id(n), id2(n), rev_id(n), prepared(false) {}
    HLD() = default;

  private:
    void dfs_sz(int v) {
        sz[v] = 1;
        for (auto &e : T.son(v)) {
            dfs_sz(e.to);
            sz[v] += sz[e.to];
            if (sz[e.to] > sz[T.son(v)[0].to])
                std::swap(e, T.son(v)[0]);
        }
    }
    void dfs_hld(int v, int &k) {
        id[v] = k++;
        rev_id[id[v]] = v;
        for (int i = 0; i < T.son(v).size(); i++) {
            int to = T.son(v)[i];
            head[to] = (i ? to : head[v]);
            dfs_hld(to, k);
        }
        id2[v] = k;
    }

  public:
    std::vector<int> build(int r = 0) {
        assert(!prepared);
        prepared = true;
        if (~T.root)
            assert(T.root == r);
        else
            T.build(r);
        head[r] = r;
        dfs_sz(r);
        int k = 0;
        dfs_hld(r, k);
        return id;
    }

    int lca(int u, int v) const {
        assert(prepared);
        while (head[u] != head[v])
            if (T.depth[head[u]] > T.depth[head[v]])
                u = T.parent(head[u]);
            else
                v = T.parent(head[v]);
        return (T.depth[u] < T.depth[v] ? u : v);
    }
    int distance(int u, int v) const {
        int w = lca(u, v);
        return T.depth[u] + T.depth[v] - T.depth[w] * 2;
    }

    // v の k 個上の頂点を返す
    int kth_parent(int v, int k) const {
        assert(prepared);
        if(T.depth[v] < k)
            return -1;
        while(T.depth[v] - T.depth[head[v]] < k){
            k -= T.depth[v] - T.depth[head[v]] + 1;
            v = T.parent(head[v]);
        }
        return rev_id[id[v] - k];
    }

    // u から v へ k 回移動した頂点を返す
    int jump(int u, int v, int k) const {
        assert(prepared);
        int w = lca(u, v);
        if(T.depth[u] + T.depth[v] - T.depth[w] * 2 < k)
            return -1;
        if(T.depth[u] - T.depth[w] >= k)
            return kth_parent(u, k);
        return kth_parent(v, T.depth[u] + T.depth[v] - T.depth[w] * 2 - k);
    }

    // l=lca(u,v) とした時、[u,l] パスと [v,l] パス を閉区間の組みで返す
    using path_t = std::vector<std::pair<int, int>>;
    std::pair<path_t, path_t> path(int u, int v) const {
        assert(prepared);
        path_t path_u, path_v;
        while (u != v) {
            if (head[u] == head[v]) {
                if (T.depth[u] < T.depth[v])
                    path_v.emplace_back(id[v], id[u]);
                else
                    path_u.emplace_back(id[u], id[v]);
                break;
            }
            if (T.depth[head[u]] < T.depth[head[v]]) {
                path_v.emplace_back(id[v], id[head[v]]);
                v = T.parent(head[v]);
            } else {
                path_u.emplace_back(id[u], id[head[u]]);
                u = T.parent(head[u]);
            }
        }
        if (u == v)
            path_u.emplace_back(id[u], id[u]);
        return {path_u, path_v};
    }

    // [l,r) が v の部分木
    std::pair<int, int> subtree(int v) const {
        assert(prepared);
        return {id[v], id2[v]};
    }
};
#line 5 "library/tree/TreeLazy.hpp"
template <typename TREE, typename Lazy> struct TreeLazy {
    using MX = typename Lazy::MX;
    using MF = typename Lazy::MF;
    using X = typename MX::value_type;
    using F = typename MF::value_type;
    using Lazy_r = LazyReverse<Lazy>;
    int n;
    TREE T;
    HLD<Tree> hld;
    std::vector<int> hld_id, euler_in, euler_out;
    LazySegmentTree<Lazy> seg;
    LazySegmentTree<Lazy_r> seg_r;

    TreeLazy(const TREE &T_, int r = 0)
        : T(T_), hld(T_), n(T_.n), seg(n), seg_r(n) {
        T.build(r);
        hld_id = hld.build(r);
    }
    TreeLazy(const TREE &T_, std::vector<X> a, int r = 0)
        : T(T_), hld(T_), n(T_.n) {
        T.build(r);
        hld_id = hld.build(r);
        std::vector<X> hld_a(n);
        for (int v = 0; v < n; v++)
            hld_a[hld_id[v]] = a[v];
        seg = LazySegmentTree<Lazy>(hld_a);
        if (!MX::commute)
            seg_r = LazySegmentTree<Lazy_r>(hld_a);
    }

    void set(int v, X x) {
        seg.set(hld_id[v], x);
        if (!MX::commute)
            seg_r.set(hld_id[v], x);
    }
    void multiply(int v, X x) {
        seg.multiply(hld_id[v], x);
        if (!MX::commute)
            seg_r.multiply(hld_id[v], x);
    }
    X get(int v) { return seg.get(hld_id[v]); }

    // [u,v]パスの monoid 積
    X path_prod(int u, int v) {
        auto [path_u, path_v] = hld.path(u, v);
        X prod_u = MX::unit(), prod_v = MX::unit();
        for (const auto &[l, r] : path_u) {
            X val = (MX::commute ? seg.prod(r, l + 1) : seg_r.prod(r, l + 1));
            MX::Rchop(prod_u, val);
        }
        for (const auto &[l, r] : path_v) {
            X val = seg.prod(r, l + 1);
            MX::Lchop(val, prod_v);
        }
        return MX::op(prod_u, prod_v);
    }
    // root -> path
    X path_root_prod(int v) { return path_prod(T.root, v); }

    void path_apply(int u, int v, const F &f) {
        auto [path_u, path_v] = hld.path(u, v);
        for (const auto &[l, r] : path_u) {
            seg.apply(r, l + 1, f);
            if (!MX::commute)
                seg_r.apply(r, l + 1, f);
        }
        for (const auto &[l, r] : path_v) {
            seg.apply(r, l + 1, f);
            if (!MX::commute)
                seg_r.apply(r, l + 1, f);
        }
    }
    void path_root_apply(int v, const F &f) { path_apply(T.root, v, f); }

    X subtree_prod(int v) {
        assert(MX::commute);
        auto [l, r] = hld.subtree(v);
        return seg.prod(l, r);
    }
    void subtree_apply(int v, const F &f) {
        auto [l, r] = hld.subtree(v);
        seg.apply(l, r, f);
        if (!MX::commute)
            seg_r.apply(l, r, f);
    }
};
#line 10 "test/AOJ/GRL_5_E.test.cpp"
using ll = long long;

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

    int n;
    std::cin >> n;

    Tree t(n);
    REP (i, n) {
        int k;
        std::cin >> k;
        REP (_, k) {
            int c;
            std::cin >> c;
            t.add_edge(i, c);
        }
    }
    t.build(0);

    TreeLazy<Tree, LazyAddSum<ll>> TL(t, cnt_init(n, 0LL));
    // 辺の情報は子に持たせる
    // 各頂点 v について、根から 1 移動した点が必要
    // Tree に jump を実装してないので無理くり求める
    std::vector<int> root2(n, -1);
    for (int v : t.BFS) {
        if (v == 0)
            continue;
        int p = t.parent(v).to;
        if (p == 0)
            root2[v] = v;
        else
            root2[v] = root2[p];
    }

    int q;
    std::cin >> q;
    REP (_, q) {
        int c;
        std::cin >> c;
        if (c) {
            int u;
            std::cin >> u;
            std::cout << TL.path_prod(u, root2[u]).first << "\n";
        } else {
            int v, w;
            std::cin >> v >> w;
            TL.path_apply(v, root2[v], w);
        }
    }
}

Back to top page