자동차 공장

#include <bits/stdc++.h>
#define MAX_N 500001

using namespace std;
int n, m, no = 1;

int adj[MAX_N];
int w[MAX_N];
int in[MAX_N], out[MAX_N];
int fenwick[MAX_N + 1];
vector<int> radj[MAX_N];

void dfs(int u) {
    in[u] = no;
    for(auto& v : radj[u]) {
        no++;
        dfs(v);
    }
    out[u] = no;
}

void ott() {
    for(int i = 1; i <= n; i++) {
        radj[adj[i]].push_back(i);
    }
    dfs(1);
}

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

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

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    cin>>w[1];
    for(int i = 2; i <= n; i++) {
        cin>>w[i]>>adj[i];
    }

    ott();

    char op;
    int u, c;
    while(m--) {
        cin>>op;
        if(op == 'p') {
            cin>>u>>c;
            update(in[u] + 1, c);
            update(out[u] + 1, -c);
        } else {
            cin>>u;
            cout<<query(in[u]) + w[u]<<'\n';
        }
    }
}