# 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;
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();
}```