[BOJ] 백준 14287번 회사 문화 3 (Java)

#14287 회사 문화 3

난이도 : 플레 4

유형 : 펜윅 트리

14287번: 회사 문화 3

▸ 문제

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다.

이러한 내리 칭찬은 회사에 가장 큰 장점이 되었고, 사장 영선이는 이 장점을 이용하기 위하여 단 하루만 반대로 하기로 했다. 즉, 부하가 상사를 칭찬하면, 그 위로 쭉 사장까지 모두 칭찬을 받는다.

칭찬에 대한 정보는 실시간으로 주어진다.

입력으로 아래와 같은 쿼리가 주어질 것이다.

• 1 i w: i번째 직원이 직속 부하 중 한 명으로부터 w만큼 칭찬을 받는다. (1 ≤ i ≤ n, 1 ≤ w ≤ 1,000) 부하가 없다면 입력으로 들어오지 않는다.
• 2 i: i번째 직원이 칭찬을 받은 정도를 출력한다.

직속 상사와 직속 부하관계에 대해 주어지고, 쿼리가 주어졌을 때 2번 쿼리에 따라 출력하시오.

▸ 입력

첫째 줄에는 회사의 직원 수 n명, 쿼리의 개수 m이 주어진다. 직원은 1번부터 n번까지 번호가 매겨져 있다. (2 ≤ n, m ≤ 100,000)

둘째 줄에는 직원 n명의 직속 상사의 번호가 주어진다. 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이다. 1번의 경우, 상사가 없으므로 -1이 입력된다.

다음 m줄에는 쿼리가 한 줄에 하나씩 주어진다.

▸ 출력

2번 쿼리가 주어질 때마다, 알맞게 출력하시오.

 

문제 풀이  

자식 노드 방향이 아닌 부모 노드 방향으로 값을 올려주면 된다. 이는 입력값을 뒤집어서 트리를 형성해주면 되기 때문에 이론은 간단하다. 다만 최대 노드의 수는 10만이기 때문에 N^2으로 하는 방식은 안되고 세그먼트 트리를 사용하여 NlogN으로 시간을 줄여줘야 한다. 어떻게 세그먼트 문제로 바꿔나갈 것이냐가 이 문제의 관건이다. (세그먼트에 대해 안다는 가정 하에)

 

이는 이진 트리가 아닌 자식 노드가 몇 개인지 가늠이 안가는 트리 구조를 지니고 있다. 그래서 다음과 같이 인덱스를 다시 정렬해준다. 

• node1 : 1~8, node2: 2~4, node3: 5~8
• node4: 3~3, node5: 4~4, node6: 6~6, node7: 7~7, node8: 8~8

 

인덱스 트리 다시 정렬

 

이렇게 해주면 펜윅트리로 값을 업데이트한 다음에 쿼리를 통해 답을 구하기 쉬워진다. 만약 7번 사원이 1의 칭찬을 주어진 다음 3번 사원의 칭찬 받은 정도를 출력해보면 다음과 같다.

• 1 7 1

7번노드는 7~7이므로 그대로 값을 펜윅트리에 넣어주면 된다.

 

• 2 3

3번노드는 5~8이다. 즉 3번 노드가 칭찬받은 정도를 알려면 5~8번이 칭찬한 정도를 모두 더해주면 된다. 따라서 펜윅트리의 5~8번 노드의 합을 가져오면 된다. sum(8) - sum(4) = 1 - 0 = 1

 

풀이 코드

import java.io.*;
import java.util.*;

public class Main {

	static int cnt = 0;
	static int n;
	static int[] in, out;
	static int[] tree;
	static List<Integer>[] list;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[n+1];
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=n; i++) {
			list[i] = new ArrayList<>();
			int num = Integer.parseInt(st.nextToken());
			if(num != -1) list[num].add(i);
		}
		
		in = new int[n+1];
		out = new int[n+1];
	
		dfs(1);
        
		tree = new int[n+1];
		while(m-->0){
			st = new StringTokenizer(br.readLine());
			int op = Integer.parseInt(st.nextToken());
			if(op==1) {
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				update(in[a], b);
			}else {
				int a = Integer.parseInt(st.nextToken());
				System.out.println(sum(out[a]) - sum(in[a]-1)); 
			}
		}
	}
	
	static void update(int idx, int val) {
		while(idx<=n) {
			tree[idx] += val;
			idx += idx&-idx;
		}
	}
	
	static int sum(int idx) {
		int res = 0;
		while(idx>0) {
			res += tree[idx];
			idx -= idx&-idx;
		}
		return res;
	}
	
	static void dfs(int here) {
		in[here] = ++cnt;
		for(int nxt : list[here]) {
			dfs(nxt);
		}
		out[here] = cnt;
	}
}