結果
問題 | No.899 γatheree |
ユーザー |
|
提出日時 | 2019-09-17 17:24:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,449 bytes |
コンパイル時間 | 1,750 ms |
コンパイル使用メモリ | 186,256 KB |
実行使用メモリ | 18,048 KB |
最終ジャッジ日時 | 2024-07-07 13:17:46 |
合計ジャッジ時間 | 6,219 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 1 |
other | WA * 23 |
ソースコード
#include <bits/stdc++.h>using namespace std::literals::string_literals;using i64 = long long;using std::cout;using std::endl;using std::cin;template<typename T>std::vector<T> make_v(size_t a){return std::vector<T>(a);}template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}template<typename Monoid, typename OperatorMonoid = Monoid>class lazy_segment_tree {using value_type = Monoid;using operator_type = OperatorMonoid;using size_type = size_t;using F = std::function<value_type (value_type, value_type)>;using G = std::function<value_type (value_type, operator_type, int, int)>;using H = std::function<operator_type (operator_type, operator_type)>;size_type size_;size_type height_;F f;G g;H h;value_type id;operator_type id_op;std::vector<value_type> data;std::vector<operator_type> lazy;std::vector<size_type> depth;const size_type get_height(const size_type& size) const {size_type height = 1;while(1 << height < size) height++;return height;}const size_type base_size() const {return 1 << height_;}const value_type reflect(const size_type & k) {if(lazy[k] == id_op) return data[k];int l = (k - (1 << depth[k])) * (base_size() >> depth[k]);int r = l + (base_size() >> depth[k]);return g(data[k], lazy[k], l, r);}void eval(const size_type & k) {if(lazy[k] == id_op) return;lazy[k << 1 ^ 0] = h(lazy[k << 1 ^ 0], lazy[k]);lazy[k << 1 ^ 1] = h(lazy[k << 1 ^ 1], lazy[k]);data[k] = reflect(k);lazy[k] = id_op;}void thrust(const size_type & k) {for(int i = height_; i; i--) eval(k >> i);}void recalc(size_type k) {while(k >>= 1) data[k] = f(reflect(k << 1 ^ 0), reflect(k << 1 ^ 1));}public:lazy_segment_tree() {}lazy_segment_tree(int n, const F & f, const G & g, const H & h, const value_type & id, const operator_type & id_op) :size_(n), f(f), g(g), h(h), id(id), id_op(id_op) {height_ = get_height(size_);data.assign(base_size() << 1, id);lazy.assign(base_size() << 1, id_op);depth.assign(base_size() << 1, 0);for(int i = 0; i < height_ + 1; i++)for(int j = (1 << i); j < (1 << (i + 1)); j++) depth[j] = i;}void update(size_type a, size_type b, operator_type x) {thrust(a += base_size());thrust(b += base_size() - 1);for(size_type l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {if(l & 1) lazy[l] = h(lazy[l], x), l++;if(r & 1) --r, lazy[r] = h(lazy[r], x);}recalc(a);recalc(b);}void change(size_type k, const value_type x) {thrust(k += base_size());data[k] = x;lazy[k] = id_op;recalc(k);}const value_type fold(size_type a, size_type b) {thrust(a += base_size());thrust(b += base_size() - 1);value_type left_value = id;value_type right_value = id;for(size_type l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {if(l & 1) left_value = f(left_value, reflect(l++));if(r & 1) right_value = f(reflect(--r), right_value);}return f(left_value, right_value);}const value_type operator[](const size_type & k) {return fold(k, k + 1);}};int main() {int n; scanf("%d", &n);std::vector<std::vector<int>> g(n);for(int i = 0; i < n - 1; i++) {int a, b; scanf("%d%d", &a, &b);g[a].push_back(b);g[b].push_back(a);}std::vector<i64> a(n);for(int i = 0; i < n; i++) scanf("%d", &a[i]);std::vector<int> vid(n), inv(n), par(n, -1), L(n), R(n);auto dfs = [&](auto && dfs, int v, int p, int & cnt) -> void {L[v] = cnt;for(auto e: g[v]) {if(e == p) continue;par[e] = v;vid[e] = cnt++;inv[vid[e]] = e;}R[v] = cnt;for(auto e: g[v]) {if(e == p) continue;dfs(dfs, e, v, cnt);}};int cnt = 1;dfs(dfs, 0, -1, cnt);auto f = [](i64 a, i64 b) { return a + b; };auto gg = [](i64 a, i64 b, int l, int r) { return b * (i64)(r - l); };auto h = [](i64 a, i64 b) { return b; };lazy_segment_tree<i64, i64> seg(n, f, gg, h, 0, -1);for(int i = 0; i < n; i++) seg.change(vid[i], a[i]);int q; scanf("%d", &q);while(q--) {int v; scanf("%d", &v);i64 A = seg.fold(L[v], R[v]);i64 B = seg[vid[v]];i64 C = (par[v] != -1 ? seg[vid[par[v]]] : 0);seg.update(L[v], R[v], 0);seg.change(vid[v], A + B + C);if(par[v] != -1) seg.change(vid[par[v]], 0);printf("%lld\n", A + B + C);// for(int i = 0; i < n; i++) cout << seg[i] << " "; cout << endl;}return 0;}