Untitled
unknown
plain_text
17 days ago
2.3 kB
2
Indexable
Never
/*** Before Any Submission *** * * Initialize and Preprocess * * Can you preprocess something? * * Can you convert a loop into math formula? * * cases of Zero, Max, and Min * * Overflow? * * Out of bounds? Limits of loops * * Check every array ,, negative accessing? * * Every condition is okay? * * Math formula is right? */ #include <bits/stdc++.h> #pragma GCC optimization("Ofast") #define ll long long #define ld long double #define nl '\n' #define pill pair<ll, ll> #define fs first #define sc second #define pb push_back #define db(xx) cout<<#xx<<": "<<xx<<nl #define dl(xx) cout<<#xx<<": "<<xx<<' ' #define rv return void using namespace std; //============================ vector<vector<ll>> gr; vector<ll> in,sub; ll timer=0; ll a[(int)2e5+5],tmp[(int)2e5+5]; void dfs(int nd, int p){ sub[nd] = 1; in[nd] = ++timer; a[in[nd]] = tmp[nd]; for(auto nx:gr[nd]){ if(nx!=p) dfs(nx,nd),sub[nd]+=sub[nx]; } } struct FenwickTree { vector<ll> bit; ll n; FenwickTree(ll n) { this->n = n; bit.assign(n, 0); } ll sum(ll r) { ll ret = 0; for (; r >= 0; r = (r & (r + 1)) - 1) ret += bit[r]; return ret; } void add(ll idx, ll delta) { for (; idx < n; idx = idx | (idx + 1)) bit[idx] += delta; } }; void run() { ll n,q; cin>>n>>q; for (int i = 0; i < n; ++i) cin>>tmp[i]; gr.resize(n+1); in.resize(n+1); sub.resize(n+1); FenwickTree fn = FenwickTree(n); for (int i = 0,u,v; i < n-1; ++i) { cin>>u>>v; --u,--v; gr[u].pb(v); gr[v].pb(u); } dfs(0,-1); int op; while(q--) { cin >> op; if (op == 1) { ll nd, val; cin >> nd >> val; --nd; fn.add(in[nd], val - a[in[nd]]); a[in[nd]] = val; } else { int nd; cin >> nd; --nd; cout << fn.sum(in[nd] + sub[nd]-1)-fn.sum(in[nd]) << nl; } } } //============================ int main() { cin.tie(0)->sync_with_stdio(0); run(); }
Leave a Comment