結果
問題 | No.1038 TreeAddQuery |
ユーザー |
![]() |
提出日時 | 2020-04-24 23:03:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,547 ms / 4,000 ms |
コード長 | 14,457 bytes |
コンパイル時間 | 1,950 ms |
コンパイル使用メモリ | 109,012 KB |
最終ジャッジ日時 | 2025-01-10 00:29:24 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
//#define NDEBUG#include <algorithm>#include <cstddef>#include <cstdint>#include <iostream>#include <utility>#include <vector>namespace n91 {using i8 = std::int_fast8_t;using i32 = std::int_fast32_t;using i64 = std::int_fast64_t;using u8 = std::uint_fast8_t;using u32 = std::uint_fast32_t;using u64 = std::uint_fast64_t;using isize = std::ptrdiff_t;using usize = std::size_t;struct rep {struct itr {usize i;constexpr itr(const usize i) noexcept : i(i) {}void operator++() noexcept { ++i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};const itr f, l;constexpr rep(const usize f, const usize l) noexcept: f(std::min(f, l)), l(l) {}constexpr auto begin() const noexcept { return f; }constexpr auto end() const noexcept { return l; }};struct revrep {struct itr {usize i;constexpr itr(const usize i) noexcept : i(i) {}void operator++() noexcept { --i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};const itr f, l;constexpr revrep(const usize f, const usize l) noexcept: f(l - 1), l(std::min(f, l) - 1) {}constexpr auto begin() const noexcept { return f; }constexpr auto end() const noexcept { return l; }};template <class T> auto md_vec(const usize n, const T &value) {return std::vector<T>(n, value);}template <class... Args> auto md_vec(const usize n, Args... args) {return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));}template <class T> constexpr T difference(const T &a, const T &b) noexcept {return a < b ? b - a : a - b;}template <class T> void chmin(T &a, const T &b) noexcept {if (b < a)a = b;}template <class T> void chmax(T &a, const T &b) noexcept {if (a < b)a = b;}template <class F> class rec_lambda {F f;public:rec_lambda(F &&f) : f(std::move(f)) {}template <class... Args> auto operator()(Args &&... args) const {return f(*this, std::forward<Args>(args)...);}};template <class F> auto make_rec(F &&f) { return rec_lambda<F>(std::move(f)); }template <class T> T scan() {T ret;std::cin >> ret;return ret;}constexpr char eoln = '\n';template <class T> T ceildiv(const T &l, const T &r) {return l / r + (l % r != 0 ? 1 : 0);}} // namespace n91namespace ei1333 {using namespace std;template <typename T> struct edge {int src, to;T cost;edge(int to, T cost) : src(-1), to(to), cost(cost) {}edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}edge &operator=(const int &x) {to = x;return *this;}operator int() const { return to; }};template <typename T> using Edges = vector<edge<T>>;template <typename T> using WeightedGraph = vector<Edges<T>>;using UnWeightedGraph = vector<vector<int>>;template <typename T> using Matrix = vector<vector<T>>;template <typename G> struct CentroidDecomposition {const G &g;vector<int> sub;vector<vector<int>> belong;vector<bool> v;CentroidDecomposition(const G &g): g(g), sub(g.size()), v(g.size()), belong(g.size()) {}inline int build_dfs(int idx, int par) {sub[idx] = 1;for (auto &to : g[idx]) {if (to == par || v[to])continue;sub[idx] += build_dfs(to, idx);}return sub[idx];}inline int search_centroid(int idx, int par, const int mid) {for (auto &to : g[idx]) {if (to == par || v[to])continue;if (sub[to] > mid)return search_centroid(to, idx, mid);}return idx;}inline void belong_dfs(int idx, int par, int centroid) {belong[idx].emplace_back(centroid);for (auto &to : g[idx]) {if (to == par || v[to])continue;belong_dfs(to, idx, centroid);}}inline int build(UnWeightedGraph &t, int idx) {int centroid = search_centroid(idx, -1, build_dfs(idx, -1) / 2);v[centroid] = true;belong_dfs(centroid, -1, centroid);for (auto &to : g[centroid]) {if (!v[to])t[centroid].emplace_back(build(t, to));}v[centroid] = false;return centroid;}inline int build(UnWeightedGraph &t) {t.resize(g.size());return build(t, 0);}};} // namespace ei1333#include <cassert>#include <cstddef>#include <memory>#include <utility>#include <vector>template <class ValueMonoid, class OperatorMonoid, class Modifier>class lazy_st_trees {public:using value_structure = ValueMonoid;using value_type = typename value_structure::value_type;using operator_structure = OperatorMonoid;using operator_type = typename operator_structure::value_type;using modifier = Modifier;private:class node_type {public:node_type *left, *right, *parent;typename lazy_st_trees::value_type value, sum;typename lazy_st_trees::operator_type lazy;bool reversed; // reverse->lazynode_type(node_type *const p): left(p), right(p), parent(p), value(value_structure::identity()),sum(value_structure::identity()),lazy(operator_structure::identity()), reversed(0) {}};using container_type = ::std::vector<node_type>;public:using size_type = typename container_type::size_type;private:using pointer = node_type *;using const_pointer = const node_type *;static void reverse(const pointer ptr) {ptr->lazy = operator_structure::reverse(::std::move(ptr->lazy));ptr->reversed ^= 1;}static void push(const pointer ptr) {if (ptr->reversed) {ptr->reversed = 0;ptr->value = value_structure::reverse(::std::move(ptr->value));::std::swap(ptr->left, ptr->right);reverse(ptr->left);reverse(ptr->right);}ptr->left->lazy = operator_structure::operation(ptr->left->lazy, ptr->lazy);ptr->right->lazy =operator_structure::operation(ptr->right->lazy, ptr->lazy);ptr->value = modifier::operation(ptr->value, ptr->lazy);ptr->lazy = operator_structure::identity();}void propagate(pointer ptr) {pointer prev = nullptr;while (ptr != nil()) {::std::swap(ptr->parent, prev);::std::swap(ptr, prev);}while (prev) {push(prev);::std::swap(prev->parent, ptr);::std::swap(prev, ptr);}nil()->sum = value_structure::identity();nil()->lazy = operator_structure::identity();nil()->reversed = 0;}static value_type reflect(const const_pointer ptr) {return modifier::operation(ptr->reversed ? value_structure::reverse(ptr->sum) : ptr->sum,ptr->lazy);}static void calc(const pointer ptr) {ptr->sum = value_structure::operation(value_structure::operation(reflect(ptr->left), ptr->value),reflect(ptr->right));}static void rotate_l(const pointer ptr, const pointer ch) {ptr->right = ch->left;ch->left->parent = ptr;calc(ptr);ch->left = ptr;ptr->parent = ch;}static void rotate_r(const pointer ptr, const pointer ch) {ptr->left = ch->right;ch->right->parent = ptr;calc(ptr);ch->right = ptr;ptr->parent = ch;}static void splay(const pointer ptr) {for (pointer x, y = ptr;;) {x = ptr->parent;if (x->left == y) {y = x->parent;ptr->parent = y->parent;if (y->left == x)rotate_r(y, x), rotate_r(x, ptr);else if (y->right == x)rotate_l(y, ptr), rotate_r(x, ptr);elsereturn ptr->parent = y, rotate_r(x, ptr);} else if (x->right == y) {y = x->parent;ptr->parent = y->parent;if (y->right == x)rotate_l(y, x), rotate_l(x, ptr);else if (y->left == x)rotate_r(y, ptr), rotate_l(x, ptr);elsereturn ptr->parent = y, rotate_l(x, ptr);} else {return;}}}void expose(const pointer ptr) {propagate(ptr);pointer x = ptr, prev = nil();while (x != nil()) {splay(x);x->right = prev;calc(x);prev = x;x = x->parent;}splay(ptr);calc(ptr);}void reroot(const pointer ptr) {expose(ptr);reverse(ptr);}container_type nodes;pointer get_ptr(const size_type v) { return nodes.data() + v; }pointer nil() { return &nodes.back(); }public:lazy_st_trees() : nodes() {}explicit lazy_st_trees(const size_type size) : nodes() {nodes.reserve(size + 1);nodes.resize(size + 1, node_type(nodes.data() + size));}bool empty() const { return size() == 0; }size_type size() const { return nodes.size() - 1; }bool connected(const size_type v, const size_type u) {assert(v < size());assert(u < size());expose(get_ptr(v));expose(get_ptr(u));return nodes[v].parent != nil() || v == u;}value_type fold_path(const size_type v, const size_type u) {assert(v < size());assert(u < size());assert(connected(v, u));reroot(get_ptr(v));expose(get_ptr(u));return nodes[u].sum;}void reroot(const size_type v) {assert(v < size());reroot(get_ptr(v));}void link(const size_type parent, const size_type child) {assert(parent < size());assert(child < size());assert(!connected(parent, child));reroot(get_ptr(child));nodes[child].parent = get_ptr(parent);}void cut(const size_type v) {assert(v < size());expose(get_ptr(v));nodes[v].left->parent = nil();nodes[v].left = nil();nodes[v].sum = nodes[v].value;}void update_path(const size_type v, const size_type u,const operator_type &value) {assert(v < size());assert(u < size());assert(connected(v, u));reroot(get_ptr(v));expose(get_ptr(u));nodes[u].lazy = value;}template <class F> void update_vertex(const size_type v, const F &f) {assert(v < size());expose(get_ptr(v));nodes[v].value = f(::std::move(nodes[v].value));calc(get_ptr(v));}};template <class T> class plus_monoid_2 {public:using value_type = T;static constexpr T operation(const T &x, const T &y) noexcept {return x + y;}static constexpr T identity() noexcept { return 0; }static constexpr T reverse(const T &x) noexcept { return x; }};#include <tuple>class trivial_group {public:using value_type = std::tuple<>;static constexpr value_type operation(const value_type,const value_type) noexcept {return value_type();}static constexpr value_type identity() noexcept { return value_type(); }static constexpr value_type inverse(const value_type) noexcept {return value_type();}static constexpr value_type reverse(const value_type) noexcept {return value_type();}};template <class T> class trivial_action {public:static constexpr Toperation(const T &lhs, const typename trivial_group::value_type) noexcept {return lhs;}};namespace n91 {template <class T> class plus_monoid {public:using value_type = T;static T operation(const T l, const T r) { return l + r; }static constexpr T identity = 0;};#include <cassert>#include <cstddef>#include <vector>template <class M> class fenwick_tree {using T = typename M::value_type;public:using value_type = T;private:std::vector<T> tree;public:fenwick_tree() = default;explicit fenwick_tree(const usize size) : tree(size + 1, M::identity) {}bool empty() const { return size() == 0; }usize size() const { return tree.size() - 1; }T fold_prefix(usize last) const {assert(last <= size());T ret = M::identity;while (last != 0) {ret = M::operation(tree[last], ret);last &= last - 1;}return ret;}void add(usize index, const T value) {assert(index < size());index += 1;while (index < tree.size()) {tree[index] = M::operation(tree[index], value);index += index & ~index + 1;}}};void main_() {//*std::ios::sync_with_stdio(false);std::cin.tie(nullptr);//*/const usize n = scan<usize>();const usize q = scan<usize>();lazy_st_trees<plus_monoid_2<usize>, trivial_group, trivial_action<usize>> lst(n);ei1333::UnWeightedGraph g(n);for (const usize i : rep(0, n - 1)) {const usize a = scan<usize>() - 1;const usize b = scan<usize>() - 1;g[a].push_back(b);g[b].push_back(a);lst.link(a, b);}for (const usize i : rep(0, n)) {lst.update_vertex(i, [](auto) { return 1; });}ei1333::CentroidDecomposition<ei1333::UnWeightedGraph> cd(g);ei1333::UnWeightedGraph tree;usize root = cd.build(tree);std::vector<usize> par(n);make_rec([&](const auto &dfs, const usize v) -> void {for (const usize e : tree[v]) {par[e] = v;dfs(e);}})(root);const auto dist = [&](const usize x, const usize y) -> usize {return lst.fold_path(x, y) - 1;};std::vector<fenwick_tree<plus_monoid<u64>>> al(n), sub(n);make_rec([&](const auto &dfs, const usize v) -> usize {usize res = 1;for (const usize e : tree[v]) {res += dfs(e);}al[v] = fenwick_tree<plus_monoid<u64>>(res - 1 + 2);sub[v] = fenwick_tree<plus_monoid<u64>>(res - 1 + 3);return res;})(root);const auto sub_or = [&](auto &ft, const usize i, const u64 val) {ft.add(std::min(i, ft.size() - 1), -val);};for (const usize loop : rep(0, q)) {const usize x = scan<usize>() - 1;const usize y = scan<usize>();const u64 z = scan<u64>();{u64 ans = 0;ans += al[x].fold_prefix(1);usize xt = x;while (xt != root) {const usize pre = xt;xt = par[xt];const usize d = dist(x, xt);ans += al[xt].fold_prefix(d + 1);ans -= sub[pre].fold_prefix(d + 1);}std::cout << ans << eoln;}{al[x].add(0, z);sub_or(al[x], y + 1, z);usize xt = x;while (xt != root) {const usize pre = xt;xt = par[xt];const usize d = dist(x, xt);if (y < d)continue;al[xt].add(0, z);sub_or(al[xt], y - d + 1, z);sub[pre].add(0, z);sub_or(sub[pre], y - d + 1, z);}}}}} // namespace n91int main() {n91::main_();return 0;}