結果
| 問題 | No.1038 TreeAddQuery |
| ユーザー |
 suisen
|
| 提出日時 | 2022-08-05 20:53:50 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 514 ms / 4,000 ms |
| コード長 | 10,782 bytes |
| コンパイル時間 | 1,683 ms |
| コンパイル使用メモリ | 115,128 KB |
| 実行使用メモリ | 65,744 KB |
| 最終ジャッジ日時 | 2024-09-15 16:31:41 |
| 合計ジャッジ時間 | 12,000 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 KB |
| testcase_01 | AC | 1 ms
6,940 KB |
| testcase_02 | AC | 1 ms
6,944 KB |
| testcase_03 | AC | 6 ms
6,940 KB |
| testcase_04 | AC | 8 ms
6,940 KB |
| testcase_05 | AC | 7 ms
6,940 KB |
| testcase_06 | AC | 6 ms
6,944 KB |
| testcase_07 | AC | 8 ms
6,940 KB |
| testcase_08 | AC | 408 ms
53,564 KB |
| testcase_09 | AC | 406 ms
54,520 KB |
| testcase_10 | AC | 418 ms
53,260 KB |
| testcase_11 | AC | 426 ms
54,068 KB |
| testcase_12 | AC | 422 ms
54,824 KB |
| testcase_13 | AC | 495 ms
65,580 KB |
| testcase_14 | AC | 514 ms
57,992 KB |
| testcase_15 | AC | 496 ms
58,392 KB |
| testcase_16 | AC | 483 ms
55,064 KB |
| testcase_17 | AC | 480 ms
55,704 KB |
| testcase_18 | AC | 365 ms
62,288 KB |
| testcase_19 | AC | 353 ms
60,976 KB |
| testcase_20 | AC | 323 ms
60,940 KB |
| testcase_21 | AC | 314 ms
60,412 KB |
| testcase_22 | AC | 302 ms
58,368 KB |
| testcase_23 | AC | 300 ms
58,476 KB |
| testcase_24 | AC | 321 ms
55,436 KB |
| testcase_25 | AC | 509 ms
65,744 KB |
| testcase_26 | AC | 449 ms
65,492 KB |
ソースコード
#include <iostream>
#include <chrono>
#include <algorithm>
#include <array>
#include <cassert>
#include <deque>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
namespace suisen {
namespace default_operator {
template <typename T>
auto zero() -> decltype(T { 0 }) { return T { 0 }; }
template <typename T>
auto one() -> decltype(T { 1 }) { return T { 1 }; }
template <typename T>
auto add(const T &x, const T &y) -> decltype(x + y) { return x + y; }
template <typename T>
auto sub(const T &x, const T &y) -> decltype(x - y) { return x - y; }
template <typename T>
auto mul(const T &x, const T &y) -> decltype(x * y) { return x * y; }
template <typename T>
auto div(const T &x, const T &y) -> decltype(x / y) { return x / y; }
template <typename T>
auto mod(const T &x, const T &y) -> decltype(x % y) { return x % y; }
template <typename T>
auto neg(const T &x) -> decltype(-x) { return -x; }
template <typename T>
auto inv(const T &x) -> decltype(one<T>() / x) { return one<T>() / x; }
} // default_operator
namespace default_operator_noref {
template <typename T>
auto zero() -> decltype(T { 0 }) { return T { 0 }; }
template <typename T>
auto one() -> decltype(T { 1 }) { return T { 1 }; }
template <typename T>
auto add(T x, T y) -> decltype(x + y) { return x + y; }
template <typename T>
auto sub(T x, T y) -> decltype(x - y) { return x - y; }
template <typename T>
auto mul(T x, T y) -> decltype(x * y) { return x * y; }
template <typename T>
auto div(T x, T y) -> decltype(x / y) { return x / y; }
template <typename T>
auto mod(T x, T y) -> decltype(x % y) { return x % y; }
template <typename T>
auto neg(T x) -> decltype(-x) { return -x; }
template <typename T>
auto inv(T x) -> decltype(one<T>() / x) { return one<T>() / x; }
} // default_operator
} // namespace suisen
namespace suisen {
template <typename T, T(*_add)(T, T) = default_operator_noref::add<T>, T(*_zero)() = default_operator_noref::zero<T>, T(*_neg)(T) = default_operator_noref::neg<T>>
struct PointGetRangeContourAddOnTree {
using value_type = T;
private:
struct InternalFenwickTree {
InternalFenwickTree() = default;
InternalFenwickTree(int n) : _n(n), _dat(_n + 1, _zero()) {}
value_type get(int i) const {
value_type res = _zero();
for (++i; i; i -= i & -i) res = _add(res, _dat[i]);
return res;
}
void add(int l, int r, const value_type& val) {
l = std::max(0, l), r = std::min(r, _n);
if (l < r) add(l, val), add(r, _neg(val));
}
private:
int _n;
std::vector<value_type> _dat;
void add(int r, const value_type& val) {
for (++r; r <= _n; r += r & -r) _dat[r] = _add(_dat[r], val);
}
};
using sequence_type = InternalFenwickTree;
struct AuxInfo {
int8_t child_index;
int dist;
};
struct TreeNode {
std::vector<int> adj;
typename std::array<AuxInfo, 30>::iterator info_it;
};
public:
PointGetRangeContourAddOnTree(int n = 0, const value_type& fill_value = _zero()) : PointGetRangeContourAddOnTree(std::vector<value_type>(n, fill_value)) {}
PointGetRangeContourAddOnTree(const std::vector<value_type>& dat) : _n(dat.size()), _dat(dat), _nodes(_n), _par(_n, -1), _info(_n), _subtrees(_n) {
_par.reserve(2 * _n);
_subtrees.reserve(2 * _n);
for (int i = 0; i < _n; ++i) {
_nodes[i].info_it = _info[i].begin();
}
}
void add_edge(int u, int v) {
_nodes[u].adj.push_back(v);
_nodes[v].adj.push_back(u);
}
void build() {
std::vector<int> sub_size(_n, 0);
std::vector<int> ctr(_n, -1);
sub_size.reserve(2 * _n);
ctr.reserve(2 * _n);
std::vector<std::vector<int>> ch(_n);
ch.reserve(2 * _n);
auto merge = [&](std::vector<int>&& l, std::vector<int>&& r) -> std::vector<int>&& {
if (l.size() > r.size()) std::swap(l, r);
for (int v : l) r.push_back(v);
return std::move(r);
};
auto rec = [&](auto rec, int r, int siz) -> int {
int c = -1;
auto get_centroid = [&](auto get_centroid, int u, int p) -> void {
sub_size[u] = 1;
for (int v : _nodes[u].adj) if (v != p) {
get_centroid(get_centroid, v, u);
if (v == c) {
sub_size[u] = siz - sub_size[c];
break;
}
sub_size[u] += sub_size[v];
}
if (c < 0 and sub_size[u] * 2 > siz) c = u;
};
get_centroid(get_centroid, r, -1);
for (int v : _nodes[c].adj) {
const int comp_size = sub_size[v];
_nodes[v].adj.erase(std::find(_nodes[v].adj.begin(), _nodes[v].adj.end(), c));
ctr[v] = rec(rec, v, comp_size);
sub_size[v] = comp_size;
}
auto comp = [&](int i, int j) { return sub_size[i] > sub_size[j]; };
std::priority_queue<int, std::vector<int>, decltype(comp)> pq{ comp };
for (int v : _nodes[c].adj) {
ch[v] = { v };
pq.push(v);
}
auto build_sequence = [this](const std::vector<int>& roots, const bool child_index) {
std::deque<std::pair<int, int>> dq;
for (int r : roots) dq.emplace_back(r, -1);
int dist = -1, nxt = roots.front();
while (dq.size()) {
const auto [u, pu] = dq.front();
dq.pop_front();
if (u == nxt) ++dist, nxt = -1;
auto& node = _nodes[u];
*node.info_it++ = { child_index, dist };
for (int v : node.adj) if (v != pu) {
dq.emplace_back(v, u);
if (nxt < 0) nxt = v;
}
}
return sequence_type(dist + 1);
};
while (pq.size() >= 2) {
const int u = pq.top(); pq.pop();
const int v = pq.top(); pq.pop();
if (pq.empty()) {
_par[ctr[u]] = _par[ctr[v]] = c;
_subtrees[c][0] = build_sequence(ch[u], 0);
_subtrees[c][1] = build_sequence(ch[v], 1);
break;
}
const int new_node = sub_size.size();
sub_size.push_back(sub_size[u] + sub_size[v]);
ctr.push_back(new_node);
_par.push_back(-1);
_par[ctr[u]] = _par[ctr[v]] = new_node;
_subtrees.emplace_back();
_subtrees[new_node][0] = build_sequence(ch[u], 0);
_subtrees[new_node][1] = build_sequence(ch[v], 1);
ch.push_back(merge(std::move(ch[u]), std::move(ch[v])));
ch[u].clear(), ch[u].shrink_to_fit();
ch[v].clear(), ch[v].shrink_to_fit();
pq.push(new_node);
}
if (pq.size()) {
int u = pq.top(); pq.pop();
_par[ctr[u]] = c;
_subtrees[c][0] = build_sequence(ch[u], 0);
}
for (int v : _nodes[c].adj) _nodes[v].adj.push_back(c);
return c;
};
rec(rec, 0, _n);
}
value_type get(int u) const {
value_type res = _dat[u];
int v = _par[u];
const auto it_end = _nodes[u].info_it;
for (auto it = _info[u].begin(); it != it_end; ++it) {
res = _add(res, _subtrees[std::exchange(v, _par[v])][it->child_index].get(it->dist));
}
return res;
}
void set(int u, const value_type& new_val) {
add(u, _add(new_val, _neg(get(u))));
}
void add(int u, const value_type &val) {
_nodes[u].dat = _add(_dat[u], val);
}
void add(int u, int dl, int dr, const value_type &val) {
if (dl <= 0 and 0 < dr) _dat[u] = _add(_dat[u], val);
_subtrees[u][0].add(dl - 1, dr - 1, val);
_subtrees[u][1].add(dl - 1, dr - 1, val);
int v = _par[u];
const auto it_end = _nodes[u].info_it;
for (auto it = _info[u].begin(); it != it_end; ++it) {
int ql = dl - it->dist - 2, qr = dr - it->dist - 2;
if (v < _n and ql <= -1 and -1 < qr) _dat[v] = _add(_dat[v], val);
_subtrees[std::exchange(v, _par[v])][it->child_index ^ 1].add(ql, qr, val);
}
}
private:
int _n;
std::vector<value_type> _dat;
std::vector<TreeNode> _nodes;
std::vector<int> _par;
std::vector<std::array<AuxInfo, 30>> _info;
std::vector<std::array<sequence_type, 2>> _subtrees;
};
} // namespace suisen
int main() {
auto beg_time = std::chrono::system_clock::now();
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
suisen::PointGetRangeContourAddOnTree<long long> g(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
std::cin >> u >> v;
--u, --v;
g.add_edge(u, v);
}
g.build();
auto mid_time = std::chrono::system_clock::now();
std::cerr << "build time : " << std::chrono::duration_cast<std::chrono::milliseconds>(mid_time - beg_time).count() << std::endl;
for (int i = 0; i < q; ++i) {
int x, y, z;
std::cin >> x >> y >> z;
--x, ++y;
std::cout << g.get(x) << '\n';
g.add(x, 0, y, z);
}
auto end_time = std::chrono::system_clock::now();
std::cerr << "query time : " << std::chrono::duration_cast<std::chrono::milliseconds>(end_time - mid_time).count() << std::endl;
return 0;
}