2820번: 자동차 공장 - 세그먼트 트리(오일러 경로 테크닉)

오일러 경로 테크닉으로 서브트리를 관리할 수 있다. 이때 서브트리를 구간으로 만들 때, 그 구간 앞뒤로 양수 월급, 음수 월급을 저장해두면 부분합을 통해 특정 노드의 월급의 합을 구할 수 있다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

#define F first
#define S second
const int MAXN = 500001;
int N, M;
vector<int> graph[MAXN];
int money[MAXN];
pii ett[MAXN];
int DFS_num = 0;
int segTree[MAXN*4];

void update(int s, int e, int m, int idx, int x)
{
    if(m > e || s > m) return;
    if(s == e)
    {
        segTree[idx] += x;
        return;
    }
    
    update(s, (s+e)/2, m, idx*2, x);
    update((s+e)/2+1, e, m, idx*2+1, x);
    segTree[idx] = segTree[idx*2] + segTree[idx*2+1];
}

int sum(int s, int e, int l, int r, int idx)
{
    if(l > e || s > r) return 0;
    if(l <= s && e <= r) return segTree[idx];
    
    return sum(s, (s+e)/2, l, r, idx*2) + sum((s+e)/2+1, e, l, r, idx*2+1);
}

void DFS(int u)
{
    ett[u].F = ++DFS_num;
    for(int v : graph[u]) DFS(v);
    ett[u].S = DFS_num;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> N >> M;
	for(int v=1; v<=N; v++)
	{
	    cin >> money[v];
	    if(v > 1)
	    {
	        int u; cin >> u;
	        graph[u].push_back(v);
	    }
	}
	
	DFS(1);
	
	for(int i=1; i<=N; i++)
    {
        update(1, N, ett[i].F, 1, money[i]);
        update(1, N, ett[i].F+1, 1, -money[i]);
    }
	   
	while(M--)
	{
	    char c; cin >> c;
	    if(c == 'p')
	    {
	        int a, x; cin >> a >> x;
	        update(1, N, ett[a].F+1, 1, x);
	        update(1, N, ett[a].S+1, 1, -x);
	    }
	    else
	    {
	        int a; cin >> a;
	        cout << sum(1, N, 1, ett[a].F, 1) << "\n";
	    }
	}
}