회사 문화3

#include <bits/stdc++.h>

#define MAX_N 100001
using namespace std;

int fenwick[MAX_N + 1], p[MAX_N + 1], sub[MAX_N + 1], treeNo[MAX_N + 1];
vector<int> adj[MAX_N + 1];
int n, m, op, root;

void update(int u, int val) {
    while(u <= n + 1) {
        fenwick[u] += val;
        u += u & -u;
    }
}

int qry(int u) {
    int res = 0;
    while(u > 0) {
        res += fenwick[u];
        u -= u & -u;
    }
    return res;
}

int dfs(int u, int& no) {
    sub[u] = 1;
    treeNo[u] = no;
    for(auto& v : adj[u])
        sub[u] += dfs(v, ++no);

    return sub[u];
}

void ott() {
    for(int i = 1; i <= n; i++) {
        if(p[i] == -1) root = i;
        else adj[p[i]].push_back(i);
    }
    int no = 1;
    dfs(root, no);
}

int main() {
    cin>>n>>m;
    for(int i = 1; i <= n; i++) cin>>p[i];
    ott();
    int u, val;
    while(m--) {
        cin>>op;
        if(op == 1) {
            cin>>u>>val;
            update(treeNo[u], val);
        } else {
            cin>>u;
            cout<<qry(treeNo[u] + sub[u] - 1) - qry(treeNo[u] - 1)<<endl;
        }
    }

    return 0;
}