[P3] 백준 14287번 회사 문화 3 C++ 세그먼트 트리, 오일러 경로 테크닉

리뷰

 

오일러 경로 테크닉으로 세그먼트 트리의 노드를 재정의 하고 누적합을 구하는 문제

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

 

전역 변수

• MAX_N : 직원의 최대 개수를 저장할 정수형 상수 변수
• n, m : 직원의 개수를 저장할 정수형 변수 n, 쿼리의 개수를 저장할 정수형 변수 m
• tree : 세그먼트 트리 정보를 담은 정수형 배열, 크기는 MAX_N * 4로 초기화
• lst : 오일러 경로 테크닉에 사용할 인접 리스트, 정수형 벡터 타입으로 크기는 MAX_N으로 초기화
• it : 오일러 경로에서 각 직원의 탐색 시작 시간을 저장할 정수형 배열, 크기는 MAX_N으로 초기화
• ot : 오일러 경로에서 각 직원의 탐색 종료 시간을 저장할 정수형 배열, 크기는 MAX_N으로 초기화
• timer : 오일러 경로에서 탐색 시간으로 사용할 정수형 변수

 

함수

1. dfs

void dfs(int boss)

 

직원을 트리구조로 탐색하여 it와 ot배열을 초기화 하기 위한 함수

1. 매개 변수로 상사의 번호 boss를 입력 받고 boss의 it를 timer + 1로 저장한다.
2. 인접리스트 lst를 참조하여 자식이 있다면 자식 노드를 매개변수로 전달하여 재귀를 진행한다.
3. 인접리스트 순회가 끝났을 경우 boss의 ot를 timer로 저장해 준다.

 

2. update

void update(int node, int s, int e, int idx, int val)

 

세그먼트 트리를 업데이트 해주는 함수

1. 이분 탐색 및 재귀를 통해 idx에 해당하는 노드로 이동하여 val만큼 더해준다.
2. 재귀를 빠져나오며 관련 노드의 값들을 최신화 해준다.

 

3. query

int query(int node, int s, int e, int L, int R)

 

세그먼트 트리에서 누적합을 구해 리턴하는 함수

1. 범위 L과 R을 받아 해당 범위 내에 있는 노드들의 합을 구해 리턴하는 함수

 

문제풀이

1. 1번 직원이 대표이므로 초기로 주어지는 -1은 필요가 없기에 해당 값을 저장할 변수 trash를 초기화 해준다.
2. n, m값을 받고 이후 고정으로 들어올 값인 -1을 trash에 받아준다.
3. 2번 직원부터 n번 직원까지 for문을 순회하며 boss의 번호를 입력 받고 lst의 boss인덱스에 현재 직원을 추가해 준다.
4. dfs함수에 대표의 번호인 1을 매개변수로 전달하여 it, ot배열을 초기화 해준다.
5. m번의 반복문을 수행하며 order와 idx값을 입력 받아준다.
6. 만약 order가 1일 경우 val을 추가로 입력 받아 update함수를 통해 세그먼트 트리의 it[idx] 인덱스에 val을 더해준다.
7. order가 2일 경우 query함수를 통해 it[idx] ~ ot[idx] 구간의 합을 출력해 준다.

 

참고 사항

부하가 상사를 칭찬하면, 그 위로 쭉 사장까지 모두 칭찬을 받는다. 라는 조건 때문에 함정에 빠지기 쉽다. (나도 그랬다.)

문제의 요점은 업데이트는 본인만 진행하고 누적합을 구할땐 자신을 포함한 자식노드의 구간합을 구하면 된다.

따라서 해당 문제에서는 느리게 갱신되는 업데이트는 진행할 필요가 없다.

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;

const int MAX_N = 100001;
int n, m;
int tree[MAX_N * 4];

vector<int> lst[MAX_N];
int it[MAX_N];
int ot[MAX_N];
int timer;

void dfs(int boss) {
	it[boss] = ++timer;
	for (int child : lst[boss]) dfs(child);
	ot[boss] = timer;
}

void update(int node, int s, int e, int idx, int val) {
	if (s == e) tree[node] += val;
	else {
		int mid = (s + e) / 2;
		if (idx <= mid) update(node * 2, s, mid, idx, val);
		else update(node * 2 + 1, mid + 1, e, idx, val);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

int query(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	int left = query(node * 2, s, mid, L, R);
	int right = query(node * 2 + 1, mid + 1, e, L, R);
	return left + right;
}

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

	int trash;
	cin >> n >> m >> trash;
	for (int i = 2; i <= n; i++) {
		int boss; cin >> boss;
		lst[boss].push_back(i);
	}

	dfs(1);

	while (m--) {
		int order, idx; cin >> order >> idx;
		if (order == 1) {
			int val; cin >> val;
			update(1, 1, n, it[idx], val);
		}
		else cout << query(1, 1, n, it[idx], ot[idx]) << "\n";
	}
}