結果
問題 | No.1790 Subtree Deletion |
ユーザー |
![]() |
提出日時 | 2021-12-19 03:37:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 140 ms / 3,000 ms |
コード長 | 1,631 bytes |
コンパイル時間 | 2,322 ms |
コンパイル使用メモリ | 227,232 KB |
最終ジャッジ日時 | 2025-01-27 03:38:03 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include<bits/stdc++.h> namespace { #include<atcoder/all> using namespace std; using namespace atcoder; #define rep(i,n)for (int i = 0; i < int(n); ++i) #define rrep(i,n)for (int i = int(n)-1; i >= 0; --i) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() template<class T> void chmax(T& a, const T& b) {a = max(a, b);} template<class T> void chmin(T& a, const T& b) {a = min(a, b);} using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; ll op(ll x, ll y) { return x ^ y; } ll e() { return 0; } bool compositoin(bool f, bool g) { return f && g; } bool id() { return true; } ll mapping(bool f, ll x) { return f * x; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<vector<pair<int, ll>>> g(n); rep(i, n - 1) { int l, r; ll a; cin >> l >> r >> a; l--; r--; g[l].emplace_back(r, a); g[r].emplace_back(l, a); } VI in_time(n), out_time(n); VL a_par(n); int time = 0; auto dfs = [&](auto self, int u, int p) -> void { in_time[u] = time; time++; for(auto [v, a] : g[u]) { if (v != p) { a_par[time] = a; self(self, v, u); } } out_time[u] = time; }; dfs(dfs, 0, -1); lazy_segtree<ll, op, e, bool, mapping, compositoin, id> seg(a_par); int q; cin >> q; rep(_, q) { int t, x; cin >> t >> x; x--; if (t == 1) { seg.apply(in_time[x], out_time[x], false); } else { ll ans = seg.prod(in_time[x] + 1, out_time[x]); cout << ans << '\n'; } } }