[BOJ 2820] 자동차 공장

[BOJ 2820] 자동차 공장 - P3

문제 설명

N명으로 이루어진 조직에서 트리 구조의 위계와 월급이 주어진다. 그리고 쿼리가 두 종류가 들어온다. 첫 번째는 i번째 사람의 모든 부하의 월급을 x만큼 변화시킨다. 두 번째는 i번째 사람의 월급을 출력한다.

문제 풀이

이 문제의 핵심은 i번 사람의 모든 부하의 월급을 어떻게 빨리 업데이트 하느냐이다. 한명씩 일일이 업데이트 한다면 O(N)만큼의 시간이 소모되므로 시간이 초과된다. 그러면 어떻게든 lazy propagation을 이용해서 log 만에 업데이트 하려는 생각을 했는데, lazy는 연속된 구간만 업데이트 할 수 있다는 한계가 있다. 따라서 불연속적인 트리가 주어진다면 불가능해진다. 그렇다면 여기서 발상을 뒤집어보자. i번 노드의 부하(자식)들을 특정 구간 안에 들어가도록 인덱스를 새롭게 지정하는 것이다. 이런 기법을 오일러 순회 기법 (Euler Tour Technique,줄여서 ETT)이라고 한다.

ETT는 위계가 있는 트리에서 루트부터 시작하는 DFS를 돌림믕로써, 특정 노드 i가 있을 때 i의 자식 중에서 인덱스(방문 순서)가 가장 작은 값은 l[i]에, 가장 큰 값은 r[i]에 저장한다. 특정 노드 i의 subtree에서 DFS 방문순서를 항상 연속적이기 때문에 lazy를 돌릴 수 있는 전제조건을 만족시켜 주는 수단이라고 생각하면 된다.
다시 말하자면 트리 구조에서 임의의 노드 i가 있을 때, i의 자식 노드들을 특정 구간 안에 속하도록(예를 들어 [l,r]) DFS를 돌리는 것이다. 이를 구현하는 코드는 단 4줄 밖에 되지 않을 정도로 간단하다. 아래 첨부한 소스코드의 renumbering이라는 함수가 그것이다.
ETT를 실행한 뒤에는 각 노드의 번호가 바뀌었으므로 바뀐 후의 자신의 인덱스는 l[i]를 통해서 찾을 수 있다.

소스코드

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int SIZE = 500009;
ll tree[SIZE*8],lazy[SIZE*8];
int arr[SIZE];
pii seg[SIZE];
int startIdx = 1,cur = 0;
vector<int> graph[SIZE];

void propagate(int node,int cl,int cr){
    if(lazy[node] != 0){
        tree[node] += lazy[node] * (cr - cl + 1);
        if(node < startIdx){
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        lazy[node] = 0;
    }
    return;
}

ll getSum(int node,int cl,int cr,int ql,int qr){
    propagate(node,cl,cr);
    if(cl > qr || ql > cr) return 0;
    if(qr >= cr && ql <= cl) return tree[node];
    int mid = (cl+cr)/2;
    return getSum(node*2,cl,mid,ql,qr) + getSum(node*2+1,mid+1,cr,ql,qr);
}

void update(int node,int cl,int cr,int ql,int qr,int x){
    propagate(node,cl,cr);
    if(ql > cr || cl > qr) return;
    if(qr >= cr && ql <= cl){
        lazy[node] += x;
        propagate(node,cl,cr);
        return;
    }

    int mid = (cl+cr)/2;
    update(node*2,cl,mid,ql,qr,x);
    update(node*2+1,mid+1,cr,ql,qr,x);

    tree[node] = tree[node*2] + tree[node*2+1];
    return;
}

void renumbering(int node){
    seg[node].first = ++cur;
    for(int next : graph[node]){
        renumbering(next);
    }
    seg[node].second = cur;
}


int main(){
    int n,q;  scanf("%d %d",&n,&q);
    for(;startIdx < n ; startIdx *= 2);

    scanf("%d",&arr[1]);
    for(int i=2 ; i<=n ; i++){
        int a;    scanf("%d %d",&arr[i],&a);
        graph[a].push_back(i);
    }

    renumbering(1);

    for(int i=1 ; i<=n ; i++){
            int j = seg[i].first;
        update(1,1,startIdx,j,j,arr[i]);
    }


    while(q--){
        char cmd;   scanf(" %c",&cmd);

        if(cmd == 'p'){
            int a,x;    scanf("%d %d",&a,&x);
            int l = seg[a].first,r = seg[a].second;
            update(1,1,startIdx,l+1,r,x);
        }

        else{
            int a;  scanf("%d",&a);
            a = seg[a].first;
            printf("%lld\n",getSum(1,1,startIdx,a,a));
        }
    }

    return 0;
}