matsutaku-library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub MatsuTaku/matsutaku-library

:heavy_check_mark: test/yosupo/dynamic_tree_vertex_add_path_sum.test.cpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum"
#include "include/mtl/link_cut_tree.hpp"
#include <bits/stdc++.h>
using namespace std;

struct Sum {
    long long x;
    Sum(long long x = 0) : x(x) {}
    Sum operator*(const Sum& rhs) const {
        return Sum(x + rhs.x);
    }
    Sum& operator*=(const Sum& rhs) {
        return *this = *this * rhs;
    }
    Sum act(const Sum& rhs) const {
        return Sum(x + rhs.x);
    }
};

int main() {
    int n,q; cin>>n>>q;
    vector<int> A(n);
    for (int i = 0; i < n; i++)
        cin>>A[i];
    LinkCutTree<Sum, Sum> T(A.begin(), A.end());
    for (int i = 0; i < n-1; i++) {
        int u,v; cin>>u>>v; 
        T.link(u,v);
    }
    for (int i = 0; i < q; i++) {
        int t; cin>>t;
        if (t == 0) {
            int u,v,w,x; cin>>u>>v>>w>>x;
            T.cut(u,v);
            T.link(w,x);
        } else if (t == 1) {
            int p,x; cin>>p>>x;
            T.update(p, x);
        } else {
            int u,v; cin>>u>>v;
            cout << T.prod(u,v).x << endl;
        }
    }
}
#line 1 "test/yosupo/dynamic_tree_vertex_add_path_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum"
#line 2 "include/mtl/splay_tree.hpp"
#include <memory>
#include <cassert>

template<class NodeType>
struct SplayTreeNodeBase {
    using node_type = NodeType;
    using node_shared = std::shared_ptr<node_type>;
    using node_weak = std::weak_ptr<node_type>;
    node_shared l,r;
    node_weak p;
    bool rev;
    bool is_root() const {
        return p.expired() || (p.lock()->l.get() != this && p.lock()->r.get() != this); 
    }
};
template<class T>
struct SplayTreeNodeTraits {
    using node_type = typename T::node_type;
    using node_shared = typename T::node_shared;
    using node_weak = typename T::node_weak;
};

template<class Node>
struct SplayTreeBase {
    using node_traits = SplayTreeNodeTraits<Node>;
    using node_type = typename node_traits::node_type;
    using node_shared = typename node_traits::node_shared;
    using node_weak = typename node_traits::node_weak;
    SplayTreeBase() = default;

    void rotate_left(const node_shared& u) const {
        auto p = u->p.lock(), q = p->p.lock();
        p->r = u->l;
        if (p->r)
            p->r->p = p;
        u->l = p;
        p->p = u;
        u->p = q;
        if (q) {
            if (q->l == p)
                q->l = u;
            else if (q->r == p)
                q->r = u;
        }
    }
    void rotate_right(const node_shared& u) const {
        auto p = u->p.lock(), q = p->p.lock();
        p->l = u->r;
        if (p->l)
            p->l->p = p;
        u->r = p;
        p->p = u;
        u->p = q;
        if (q) {
            if (q->l == p)
                q->l = u;
            else if (q->r == p)
                q->r = u;
        }
    }
    virtual void reverse_prod(const node_shared& u) const {}
    virtual void propagate(const node_shared& u) const {}
    virtual void aggregate(const node_shared& u) const {}
    void splay(const node_shared& u) const {
        if (u->is_root()) {
            this->propagate(u);
            this->aggregate(u);
            return;
        }
        do {
            assert(u);
            auto p = u->p.lock();
            assert(p);
            if (p->is_root()) {
                this->propagate(p);
                this->propagate(u);
                if (p->l == u)
                    rotate_right(u);
                else if (p->r == u)
                    rotate_left(u);
                else throw "invalid tree";
                this->aggregate(p);
                this->aggregate(u);
            } else {
                auto q = p->p.lock();
                this->propagate(q);
                this->propagate(p);
                this->propagate(u);
                if (q->l == p) {
                    if (p->l == u) { // zig-zig
                        rotate_right(p);
                        rotate_right(u);
                        this->aggregate(q);
                        this->aggregate(p);
                    } else if (p->r == u) { // zig-zag
                        rotate_left(u);
                        rotate_right(u);
                        this->aggregate(p);
                        this->aggregate(q);
                    } else throw "invalid tree";
                } else if (q->r == p) { 
                    if (p->r == u) { // zig-zig
                        rotate_left(p);
                        rotate_left(u);
                        this->aggregate(q);
                        this->aggregate(p);
                    } else if (p->l == u) { // zig-zag
                        rotate_right(u);
                        rotate_left(u);
                        this->aggregate(p);
                        this->aggregate(q);
                    } else throw "invalid tree";
                }
                this->aggregate(u);
            }
        } while (!u->is_root());
    }

};
#line 2 "include/mtl/monoid.hpp"
#include <utility>
#if __cpp_concepts >= 202002L
#include <concepts>
#endif

template<class T, T (*op)(T, T), T (*e)()>
struct Monoid {
  T x;
  Monoid() : x(e()) {}
  template<class... Args>
  Monoid(Args&&... args) : x(std::forward<Args>(args)...) {}
  Monoid operator*(const Monoid& rhs) const {
    return Monoid(op(x, rhs.x));
  }
  const T& val() const {
    return x;
  }
};

struct VoidMonoid {
  VoidMonoid() {}
  VoidMonoid operator*(const VoidMonoid& rhs) const {
    return VoidMonoid();
  }
};

#if __cpp_concepts >= 202002L
template<class T>
concept IsMonoid = requires (T m) {
  { m * m } -> std::same_as<T>;
};
#endif

template<class T, T (*op)(T, T), T (*e)()>
struct CommutativeMonoid : public Monoid<T, op, e> {
    using Base = Monoid<T, op, e>;
    CommutativeMonoid(T x=e()) : Base(x) {}
    CommutativeMonoid operator+(const CommutativeMonoid& rhs) const {
        return CommutativeMonoid(*this * rhs);
    }
};

#if __cpp_concepts >= 202002L
template<class T>
concept IsCommutativeMonoid = requires (T m) {
  { m + m } -> std::same_as<T>;
};
#endif

template<class S, class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()>
struct OperatorMonoid {
    F f;
    OperatorMonoid() : f(id()) {}
    template<class... Args>
    OperatorMonoid(Args&&... args) : f(std::forward<Args>(args)...) {}
    OperatorMonoid& operator*=(const OperatorMonoid& rhs) {
        f = composition(rhs.f, f);
        return *this;
    }
    S act(const S& s) const {
        return mapping(f, s);
    }
};

struct VoidOperatorMonoid {
    VoidOperatorMonoid() {}
    VoidOperatorMonoid& operator*=(const VoidOperatorMonoid& rhs) {
        return *this;
    }
    template<class T>
    T act(const T& s) const {
        return s;
    }
};

#if __cpp_concepts >= 202002L
template<class F, class S>
concept IsOperatorMonoid = requires (F f, S s) {
    { f *= f } -> std::same_as<F&>;
    { f.act(s) } -> std::same_as<S>;
};
#endif
#line 3 "include/mtl/link_cut_tree.hpp"
#include <vector>
#include <iostream>

template<class NodeType>
struct LinkCutTreeBase : public SplayTreeBase<NodeType> {
    using Base = SplayTreeBase<NodeType>;
    using node_traits = SplayTreeNodeTraits<NodeType>;
    using node_shared = typename node_traits::node_shared;
    void expose(const node_shared& x) const {
        node_shared r = nullptr;
        for (node_shared p = x; p; p = p->p.lock()) {
            Base::splay(p);
            p->r = r;
            r = p;
            this->aggregate(p);
        }
        Base::splay(x);
    }
    void evert(const node_shared& v) const {
        expose(v);
        v->rev ^= true;
        this->reverse_prod(v);
        this->propagate(v);
    }
    void cut(const node_shared& c) const {
        expose(c);
        auto l = c->l;
        c->l = nullptr;
        l->p.reset();
        this->aggregate(c);
    }
    void link(const node_shared& c, const node_shared& p) const {
        evert(c);
        expose(p);
        p->r = c;
        c->p = p;
        this->aggregate(p);
    }
    void print_tree(const node_shared& u) const {
        if (!u) return;
        if (u->l and u->l->p.lock() == u) {
            print_tree(u->l);
        }
        std::cerr<<u->m.x<<' ';
        if (u->r and u->r->p.lock() == u) {
            print_tree(u->r);
        }
    }
};

template<class M, class O>
struct LinkCutTreeNode : SplayTreeNodeBase<LinkCutTreeNode<M, O>> {
    M m, prod, rprod;
    O f;
    using Base = SplayTreeNodeBase<LinkCutTreeNode<M, O>>;
    LinkCutTreeNode() = default;
    template<class... Args>
    LinkCutTreeNode(Args&&... args) 
        : Base(), m(std::forward<Args>(args)...), prod(m), rprod(m), f() {}
};

template<class M, class O=VoidOperatorMonoid>
#if __cpp_concepts >= 202002L
requires IsMonoid<M> && IsOperatorMonoid<O, M>
#endif
struct LinkCutTree : LinkCutTreeBase<LinkCutTreeNode<M, O>> {
    using node_type = LinkCutTreeNode<M, O>;
    using Base = LinkCutTreeBase<LinkCutTreeNode<M, O>>;
    using monoid_type = M;
    using operator_monoid_type = O;
    using node_shared = typename SplayTreeNodeTraits<LinkCutTreeNode<M, O>>::node_shared;
    std::vector<node_shared> nodes;
    LinkCutTree(size_t n) : Base(), nodes(n) {
        for (size_t i = 0; i < n; ++i)
            nodes[i] = std::make_shared<node_type>();
    }
    template<class InputIt>
    LinkCutTree(InputIt first, InputIt last) : Base(), nodes(std::distance(first, last)) {
        size_t i = 0;
        for (auto it = first; it != last; ++it)
            nodes[i++] = std::make_shared<node_type>(*it);
    }
    void reverse_prod(const node_shared& u) const override {
        std::swap(u->prod, u->rprod);
    }
    void propagate(const node_shared& u) const override {
        bool cl = u->l and u->l->p.lock() == u;
        bool cr = u->r and u->r->p.lock() == u;
        if (cl) {
            u->l->m = u->f.act(u->l->m);
            u->l->prod = u->f.act(u->l->prod);
            u->l->rprod = u->f.act(u->l->rprod);
            u->l->f *= u->f;
        }
        if (cr) {
            u->r->m = u->f.act(u->r->m);
            u->r->prod = u->f.act(u->r->prod);
            u->r->rprod = u->f.act(u->r->rprod);
            u->r->f *= u->f;
        }
        if (u->rev) {
            std::swap(u->l, u->r);
            if (cr) {
                u->l->rev ^= true;
                reverse_prod(u->l);
            }
            if (cl) {
                u->r->rev ^= true;
                reverse_prod(u->r);
            }
            u->rev = false;
        }
        u->f = operator_monoid_type();
    }
    void aggregate(const node_shared& u) const override {
        u->prod = u->m;
        u->rprod = u->m;
        if (u->l and u->l->p.lock() == u) {
            u->prod = u->l->prod * u->prod;
            u->rprod = u->rprod * u->l->rprod;
        }
        if (u->r and u->r->p.lock() == u) {
            u->prod = u->prod * u->r->prod;
            u->rprod = u->r->rprod * u->rprod;
        }
    }
    void cut(size_t u, size_t v) const {
        Base::evert(nodes[u]);
        Base::expose(nodes[v]);
        auto l = nodes[v]->l;
        nodes[v]->l = nullptr;
        l->p.reset();
        this->aggregate(nodes[v]);
    }
    void link(size_t u, size_t v) const {
        Base::link(nodes[v], nodes[u]);
    }
    monoid_type prod(size_t u, size_t v) const {
        Base::evert(nodes[u]);
        Base::expose(nodes[v]);
        return nodes[v]->prod;
    }
    template<class... Args>
    void set(size_t i, Args&&... args) const {
        auto u = nodes[i];
        Base::splay(u);
        u->m = monoid_type(std::forward<Args>(args)...);
        this->aggregate(u);
    }
    void update(size_t i, const operator_monoid_type& f) const {
        auto u = nodes[i];
        Base::splay(u);
        u->m = f.act(u->m);
        this->aggregate(u);
    }
    void update(size_t u, size_t v, const operator_monoid_type& f) const {
        Base::evert(nodes[u]);
        auto nv = nodes[v];
        Base::expose(nv);
        nv->m = f.act(nv->m);
        nv->prod = f.act(nv->prod);
        nv->rprod = f.act(nv->rprod);
        nv->f *= f;
        Base::splay(nv);
    }
};
#line 3 "test/yosupo/dynamic_tree_vertex_add_path_sum.test.cpp"
#include <bits/stdc++.h>
using namespace std;

struct Sum {
    long long x;
    Sum(long long x = 0) : x(x) {}
    Sum operator*(const Sum& rhs) const {
        return Sum(x + rhs.x);
    }
    Sum& operator*=(const Sum& rhs) {
        return *this = *this * rhs;
    }
    Sum act(const Sum& rhs) const {
        return Sum(x + rhs.x);
    }
};

int main() {
    int n,q; cin>>n>>q;
    vector<int> A(n);
    for (int i = 0; i < n; i++)
        cin>>A[i];
    LinkCutTree<Sum, Sum> T(A.begin(), A.end());
    for (int i = 0; i < n-1; i++) {
        int u,v; cin>>u>>v; 
        T.link(u,v);
    }
    for (int i = 0; i < q; i++) {
        int t; cin>>t;
        if (t == 0) {
            int u,v,w,x; cin>>u>>v>>w>>x;
            T.cut(u,v);
            T.link(w,x);
        } else if (t == 1) {
            int p,x; cin>>p>>x;
            T.update(p, x);
        } else {
            int u,v; cin>>u>>v;
            cout << T.prod(u,v).x << endl;
        }
    }
}

Test cases

Env Name Status Elapsed Memory
g++ example_00 :heavy_check_mark: AC 5 ms 3 MB
g++ max_random_00 :heavy_check_mark: AC 1258 ms 29 MB
g++ max_random_01 :heavy_check_mark: AC 1165 ms 29 MB
g++ max_random_02 :heavy_check_mark: AC 1425 ms 29 MB
g++ random_00 :heavy_check_mark: AC 821 ms 20 MB
g++ random_01 :heavy_check_mark: AC 861 ms 23 MB
g++ random_02 :heavy_check_mark: AC 598 ms 10 MB
g++ random_03 :heavy_check_mark: AC 502 ms 25 MB
g++ random_04 :heavy_check_mark: AC 348 ms 5 MB
g++ small_00 :heavy_check_mark: AC 7 ms 4 MB
g++ small_01 :heavy_check_mark: AC 6 ms 3 MB
g++ small_02 :heavy_check_mark: AC 7 ms 3 MB
clang++ example_00 :heavy_check_mark: AC 6 ms 3 MB
clang++ max_random_00 :heavy_check_mark: AC 1368 ms 29 MB
clang++ max_random_01 :heavy_check_mark: AC 1375 ms 29 MB
clang++ max_random_02 :heavy_check_mark: AC 1354 ms 29 MB
clang++ random_00 :heavy_check_mark: AC 948 ms 20 MB
clang++ random_01 :heavy_check_mark: AC 997 ms 23 MB
clang++ random_02 :heavy_check_mark: AC 644 ms 10 MB
clang++ random_03 :heavy_check_mark: AC 546 ms 25 MB
clang++ random_04 :heavy_check_mark: AC 451 ms 5 MB
clang++ small_00 :heavy_check_mark: AC 7 ms 3 MB
clang++ small_01 :heavy_check_mark: AC 6 ms 3 MB
clang++ small_02 :heavy_check_mark: AC 6 ms 3 MB
Back to top page