BOJ 14287 - 회사 문화 3 링크
(2023.07.21 기준 P3)

문제

사장을 제외한 모든 직원은 직속 상사가 있으며 직속 상사의 번호는 자신의 번호보다 작다.
이런 회사에서 부하가 상사를 칭찬하면, 그 위로 쭉 사장까지 모두 칭찬을 받는다고 했을 때, 다음과 같은 쿼리를 처리

• 1 i w: i번째 직원이 w만큼 칭찬을 받는다.
• 2 i: i번째 직원이 칭찬을 받은 정도를 출력한다.

알고리즘

오일러 경로 테크닉을 이용한 세그먼트 트리

풀이

전위 순회를 하여 각 정점마다 방문 순서와 빠져나가는 순서를 기록해보자.
방문 순서는 in, 빠져나가는 순서를 out이라고 하겠다.

밑 그림을 살펴보자.

만약 3번 직원이 칭찬을 받는다면? in[3] = 3을 포함하는 직원 전부 칭찬을 받게 된다.
3을 포함하는 직원은 1번, 2번, 3번 직원이다.

그리고 1번 직원의 칭찬받은 정도를 출력해야 하면? in[1]의 서브트리의 합. 즉, [in[1], out[1]] 구간의 합을 출력하면 된다.

결국은, in[i]에 w를 점 업데이트하고, [in[i], out[i]] 구간의 합 쿼리로 처리하면 된다.

코드

• C++

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

typedef long long ll;

const int MAXN = 100000, MAXM = 1 << (int)ceil(log2(MAXN) + 1);

int in[MAXN], out[MAXN], idx;
ll tree[MAXM];
vector<int> graph[MAXN];

// 오일러 경로를 위한 전위 순회
void dfs(int i){
    in[i] = ++idx;
    for (auto j: graph[i]) dfs(j);
    out[i] = idx;
}

// 점 업데이트
void update(int nd, int st, int en, int idx, int val){
    if (st == en){
        tree[nd] += val;
        return;
    }
    int mid = (st + en) >> 1;
    if (idx <= mid) update(nd << 1, st, mid, idx, val);
    else update(nd << 1 | 1, mid + 1, en, idx, val);
    tree[nd] = tree[nd << 1] + tree[nd << 1 | 1];
}

// 구간 쿼리
ll query(int nd, int st, int en, int l, int r){
    if (r < st || en < l) return 0;
    if (l <= st && en <= r) return tree[nd];
    int mid = (st + en) >> 1;
    return query(nd << 1, st, mid, l, r) + query(nd << 1 | 1, mid + 1, en, l, r);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    int e[n]; for (int i = 0; i < n; i++) cin >> e[i];

    // 상사 -> 부하 그래프
    for (int i = 1; i < n; i++) graph[e[i] - 1].push_back(i);

    // 오일러 경로
    fill(in, in + n, 0);
    fill(out, out + n, 0);
    idx = -1;
    dfs(0);

    fill(tree, tree + (1 << (int)ceil(log2(n) + 1)), 0);
    int q, i, w;
    while (m--){
        cin >> q;
        if (q == 1){
            cin >> i >> w;
            update(1, 0, n - 1, in[i - 1], w);
        }
        else{ // i번째 직원이 받는 칭찬은 in[i]의 서브트리의 합이다.
            cin >> i;
            cout << query(1, 0, n - 1, in[i - 1], out[i - 1]) << '\n';
        }
    }
}

• Python

import sys; input = sys.stdin.readline
sys.setrecursionlimit(111111)
from math import ceil, log2

# 오일러 경로를 위한 전위 순회
def dfs(i):
    global idx; idx += 1; inn[i] = idx
    for j in graph[i]:
        dfs(j)
    out[i] = idx

# 점 업데이트
def update(nd, st, en, idx, val):
    if st == en:
        tree[nd] += val
        return
    mid = (st + en) >> 1
    if idx <= mid:
        update(nd << 1, st, mid, idx, val)
    else:
        update(nd << 1 | 1, mid + 1, en, idx, val)
    tree[nd] = tree[nd << 1] + tree[nd << 1 | 1]

# 구간 쿼리
def query(nd, st, en, l, r):
    if r < st or en < l:
        return 0
    if l <= st and en <= r:
        return tree[nd]
    mid = (st + en) >> 1
    return query(nd << 1, st, mid, l, r) + query(nd << 1 | 1, mid + 1, en, l, r)

n, m = map(int, input().split())
e = list(map(int, input().split()))

# 상사 -> 부하 그래프
graph = [[] for _ in range(n)]
for i in range(1, n):
    graph[e[i] - 1].append(i)

# 오일러 경로
inn = [0] * n
out = [0] * n
idx = -1
dfs(0)

tree = [0] * (1 << ceil(log2(n) + 1))
for _ in range(m):
    q, *lst = map(int, input().split())
    if q == 1:
        update(1, 0, n - 1, inn[lst[0] - 1], lst[1])
    else: # i번째 직원이 받는 칭찬은 in[i]의 서브트리의 합이다.
        print(inn[lst[0] - 1], out[lst[0] - 1])
        print(query(1, 0, n - 1, inn[lst[0] - 1], out[lst[0] - 1]))