#include #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 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 struct lazy_propagation_segment_tree { // on monoids static_assert (std::is_same::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 a; std::vector 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 values REP_R (i, n - 1) a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]); // propagate initial values f.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-based a[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-based a[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 commutative range_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 recursion if (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 value int64_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 void do_bfs_tour(vector > const & g, int root, vector & tour, vector & parent, vector > & left, vector > & right) { int n = g.size(); tour.clear(); parent.assign(n, -1); left.resize(n); right.resize(n); queue que; que.push(root); while (not que.empty()) { int x = que.front(); que.pop(); int i = tour.size(); // initialize current tour.push_back(x); fill(ALL(left[x]), n); fill(ALL(right[x]), n); // update parent int 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 children for (int y : g[x]) if (y != parent[x]) { parent[y] = x; que.push(y); } } } int main() { // input the initial state int n; cin >> n; vector > g(n); REP (i, n - 1) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } vector a(n); REP (i, n) { cin >> a[i]; } // prepare const int root = 0; vector tour, parent; vector > left, right; do_bfs_tour<2>(g, root, tour, parent, left, right); vector lookup(n); REP (i, n) { lookup[tour[i]] = i; } lazy_propagation_segment_tree segtree(n); REP (x, n) { segtree.point_set(lookup[x], a[x]); } // query int 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; }