백준 16404번: 주식회사 승범이네 (C++)

https://www.acmicpc.net/problem/16404

16404번: 주식회사 승범이네

---

Solved By:  Euler Tour Technique, Segment Tree, Lazy Propagation

 

#include <iostream>
#include <vector>
#include <utility>
#define MAX (500000 + 1)
#define pii pair<int, int>
#define ll long long
using namespace std;

int n, m;
vector<int> adj[MAX];
pii ett[MAX];
ll sgTree[MAX * 4];
ll lazy[MAX * 4];
vector<ll> result;

int dfsN = 0;
void dfs(int now, int par){
    ett[now].first = ++dfsN;
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        if(next == par) continue;
        dfs(next, par);
    }
    
    ett[now].second = dfsN;
}

void lazyUpdate(int start, int end, int node){
    if(!lazy[node]) return;
    
    sgTree[node] += lazy[node] * (end - start + 1);
    if(start != end) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    
    lazy[node] = 0;
}

void update(int start, int end, int node, int left, int right, ll val){
    lazyUpdate(start, end, node);
    if(end < left || start > right) return;
    if(left <= start && end <= right){
        if(start == end){
            sgTree[node] += (end - start + 1) * val;
        }
        else{
            lazy[node * 2] += val;
            lazy[node * 2 + 1] += val;
        }
        return;
    }
    
    int mid = (start + end) >> 1;
    update(start, mid, node * 2, left, right, val);
    update(mid + 1, end, node * 2 + 1, left, right, val);
}


ll query(int start, int end, int node, int idx){
    lazyUpdate(start, end, node);
    if(idx < start || end < idx) return 0;
    if(start == end) return sgTree[node];
    
    int mid = (start + end) >> 1;
    
    if(idx <= mid){
        return query(start, mid, node * 2, idx) ;
    }
    else{
        return query(mid + 1, end, node * 2 + 1, idx);
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int v; cin >> v;
        if(v == -1) continue;
        adj[v].push_back(i);
    }
    
    dfs(1, 0);
    
    for(int i = 0; i < m; i++){
        int q;
        cin >> q;
        if(q == 1){
            int a, w;
            cin >> a >> w;
            update(1, n, 1, ett[a].first, ett[a].second, w);
        }
        else if(q == 2){
            int a;
            cin >> a;
            result.push_back(query(1, n, 1, ett[a].first));
        }
    }
    
    for(int i = 0; i < result.size(); i++){
        if(i == result.size() - 1) cout << result[i];
        else cout << result[i] << '\n';
    }
    return 0;
}