結果
問題 | No.1038 TreeAddQuery |
ユーザー | noshi91 |
提出日時 | 2020-04-24 23:03:34 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,282 ms / 4,000 ms |
コード長 | 14,457 bytes |
コンパイル時間 | 3,135 ms |
コンパイル使用メモリ | 112,492 KB |
実行使用メモリ | 69,772 KB |
最終ジャッジ日時 | 2023-08-16 14:57:22 |
合計ジャッジ時間 | 19,998 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 10 ms
4,380 KB |
testcase_04 | AC | 11 ms
4,376 KB |
testcase_05 | AC | 11 ms
4,608 KB |
testcase_06 | AC | 10 ms
4,384 KB |
testcase_07 | AC | 12 ms
4,416 KB |
testcase_08 | AC | 775 ms
54,040 KB |
testcase_09 | AC | 887 ms
56,792 KB |
testcase_10 | AC | 913 ms
57,004 KB |
testcase_11 | AC | 907 ms
56,976 KB |
testcase_12 | AC | 936 ms
57,688 KB |
testcase_13 | AC | 1,282 ms
69,772 KB |
testcase_14 | AC | 1,149 ms
62,844 KB |
testcase_15 | AC | 1,097 ms
61,492 KB |
testcase_16 | AC | 1,054 ms
60,916 KB |
testcase_17 | AC | 1,042 ms
60,160 KB |
testcase_18 | AC | 170 ms
36,812 KB |
testcase_19 | AC | 212 ms
38,500 KB |
testcase_20 | AC | 220 ms
38,468 KB |
testcase_21 | AC | 259 ms
40,068 KB |
testcase_22 | AC | 381 ms
44,812 KB |
testcase_23 | AC | 424 ms
46,216 KB |
testcase_24 | AC | 646 ms
55,472 KB |
testcase_25 | AC | 1,233 ms
69,720 KB |
testcase_26 | AC | 667 ms
53,680 KB |
ソースコード
//#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 n91 namespace 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->lazy node_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); else return 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); else return 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 T operation(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 n91 int main() { n91::main_(); return 0; }