Untitled

mail@pastecode.io avatar
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