結果
問題 | No.899 γatheree |
ユーザー |
|
提出日時 | 2019-10-04 22:19:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 859 ms / 2,000 ms |
コード長 | 7,270 bytes |
コンパイル時間 | 2,813 ms |
コンパイル使用メモリ | 211,928 KB |
最終ジャッジ日時 | 2025-01-07 20:38:10 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h>#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))#define ALL(x) std::begin(x), std::end(x)using namespace std;/*** @note lazy_propagation_segment_tree<max_monoid, plus_operator_monoid> is the starry sky tree* @note verified https://www.hackerrank.com/contests/world-codesprint-12/challenges/factorial-array/submissions/code/1304452669* @note verified https://www.hackerrank.com/contests/world-codesprint-12/challenges/animal-transport/submissions/code/1304454860* @note intersting discussion about range-extension and partial-function-extension: https://github.com/kmyk/competitive-programming-library/issues/3*/template <class Monoid, class OperatorMonoid>struct lazy_propagation_segment_tree { // on monoidsstatic_assert (std::is_same<typename Monoid::value_type, typename OperatorMonoid::target_type>::value, "");typedef typename Monoid::value_type value_type;typedef typename OperatorMonoid::value_type operator_type;const Monoid mon;const OperatorMonoid op;int n;std::vector<value_type> a;std::vector<operator_type> f;lazy_propagation_segment_tree() = default;lazy_propagation_segment_tree(int a_n, value_type initial_value = Monoid().unit(), Monoid const & a_mon = Monoid(), OperatorMonoid const & a_op =OperatorMonoid()): mon(a_mon), op(a_op) {n = 1; while (n <= a_n) n *= 2;a.resize(2 * n - 1, mon.unit());std::fill(a.begin() + (n - 1), a.begin() + ((n - 1) + a_n), initial_value); // set initial valuesREP_R (i, n - 1) a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]); // propagate initial valuesf.resize(std::max(0, (2 * n - 1) - n), op.identity());}void point_set(int i, value_type z) {assert (0 <= i and i < n);point_set(0, 0, n, i, z);}void point_set(int i, int il, int ir, int j, value_type z) {if (i == n + j - 1) { // 0-baseda[i] = z;} else if (ir <= j or j+1 <= il) {// nop} else {range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);f[i] = op.identity();point_set(2 * i + 1, il, (il + ir) / 2, j, z);point_set(2 * i + 2, (il + ir) / 2, ir, j, z);a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]);}}void range_apply(int l, int r, operator_type z) {assert (0 <= l and l <= r and r <= n);range_apply(0, 0, n, l, r, z);}void range_apply(int i, int il, int ir, int l, int r, operator_type z) {if (l <= il and ir <= r) { // 0-baseda[i] = op.apply(z, a[i]);if (i < f.size()) f[i] = op.compose(z, f[i]);} else if (ir <= l or r <= il) {// nop} else {range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);f[i] = op.identity(); // unnecessary if the oprator monoid is commutativerange_apply(2 * i + 1, il, (il + ir) / 2, l, r, z);range_apply(2 * i + 2, (il + ir) / 2, ir, l, r, z);a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]);}}value_type range_concat(int l, int r) {assert (0 <= l and l <= r and r <= n);value_type lacc = mon.unit(), racc = mon.unit();for (int l1 = (l += n), r1 = (r += n) - 1; l1 > 1; l /= 2, r /= 2, l1 /= 2, r1 /= 2) { // 1-based loop, 2x faster than recursionif (l < r) {if (l % 2 == 1) lacc = mon.append(lacc, a[(l ++) - 1]);if (r % 2 == 1) racc = mon.append(a[(-- r) - 1], racc);}lacc = op.apply(f[l1 / 2 - 1], lacc);racc = op.apply(f[r1 / 2 - 1], racc);}return mon.append(lacc, racc);}};struct plus_monoid {typedef int64_t value_type;int64_t unit() const { return 0; }int64_t append(int64_t a, int64_t b) const { return a + b; }};struct const_operator_monoid {typedef int64_t value_type;typedef int64_t target_type;int64_t identity() const { return INT64_MIN; } // a dummy valueint64_t apply(value_type a, target_type b) const { return a == INT64_MIN ? b : a; }int64_t compose(value_type a, value_type b) const { return a == INT64_MIN ? b : a; }};/*** @brief something like euler tour but do BFS* @arg g must be a tree, directed or undirected* @note for constraints, see the unittest* @arg parent is initialized* @arg left and* @arg right are the ranges of descendants of k-th level* @note O(N * DEPTH)* @sa https://yukicoder.me/problems/no/899*/template <int DEPTH>void do_bfs_tour(vector<vector<int> > const & g, int root, vector<int> & tour, vector<int> & parent, vector<array<int, DEPTH> > & left, vector<array<int, DEPTH> > & right) {int n = g.size();tour.clear();parent.assign(n, -1);left.resize(n);right.resize(n);queue<int> que;que.push(root);while (not que.empty()) {int x = que.front();que.pop();int i = tour.size();// initialize currenttour.push_back(x);fill(ALL(left[x]), n);fill(ALL(right[x]), n);// update parentint y = x;REP (d, DEPTH) {y = parent[y];if (y == -1) break;left[y][d] = min(left[y][d], i);right[y][d] = i + 1;}// go childrenfor (int y : g[x]) if (y != parent[x]) {parent[y] = x;que.push(y);}}}int main() {// input the initial stateint n; cin >> n;vector<vector<int> > g(n);REP (i, n - 1) {int x, y; cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}vector<int64_t> a(n);REP (i, n) {cin >> a[i];}// prepareconst int root = 0;vector<int> tour, parent;vector<array<int, 2> > left, right;do_bfs_tour<2>(g, root, tour, parent, left, right);vector<int> lookup(n);REP (i, n) {lookup[tour[i]] = i;}lazy_propagation_segment_tree<plus_monoid, const_operator_monoid> segtree(n);REP (x, n) {segtree.point_set(lookup[x], a[x]);}// queryint q; cin >> q;while (q --) {int x; cin >> x;int64_t acc = 0;auto f = [&](int l, int r) {acc += segtree.range_concat(l, r);segtree.range_apply(l, r, 0);};f(left[x][1], right[x][1]);f(left[x][0], right[x][0]);if (x == root) {f(lookup[x], lookup[x] + 1);} else {f(left[parent[x]][0], right[parent[x]][0]);f(lookup[parent[x]], lookup[parent[x]] + 1);if (parent[x] != root) {f(lookup[parent[parent[x]]], lookup[parent[parent[x]]] + 1);}}segtree.point_set(lookup[x], acc);cout << acc << endl;}return 0;}