結果

問題 No.1038 TreeAddQuery
ユーザー noshi91
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

//#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0