結果

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

ソースコード

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

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