[ BOJ ][JAVA][14267] 회사 문화 1

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

14267번: 회사 문화 1

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	1729	669	508	40.095%

문제

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

모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는다.

직속 상사와 직속 부하관계에 대해 주어지고, 칭찬에 대한 정보가 주어질 때, 각자 얼마의 칭찬을 받았는지 출력하시오,

입력

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

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

다음 m줄에는 직속 상사로부터 칭찬을 받은 직원 번호 i, 칭찬의 수치 w가 주어진다. (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000)

사장은 상사가 없으므로 칭찬을 받지 않는다.

출력

1번부터 n번의 직원까지 칭찬을 받은 정도를 출력하시오.

예제 입력 1

5 3
-1 1 2 3 4
2 2
3 4
5 6

예제 출력 1

0 2 6 6 12

코드

/*
    회사 문화 1
    dfs, 구현
*/
import java.io.*;
import java.util.*;
public class p14267 {
    static int n, m;
    static int[] cost;
    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());
        m = Integer.parseInt(st.nextToken());
        cost = new int[n + 1];
        list = new ArrayList[n + 1];

        for (int i = 0; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        // 직속상사 관계 설정
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            // i의 직속 상사는 num;
            int num = Integer.parseInt(st.nextToken());
            // 직송상사num - 부하 i , 그래프 생성
            if (i != 1) list[num].add(i);
        }

        // 칭찬 리스트
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            // parent가 칭찬을 받았다? -> parent의 직속 상사를 찾아서 해당하는 부하들을 전부 칭찬한다.
            // 부하 p가 칭찬 weight를 받았다.
            cost[p] += weight;
        }

        dfs(1);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(cost[i]).append(" ");
        }
        System.out.println(sb.toString());
    }

    static void dfs(int start) {
        for (int next : list[start]) {
            cost[next] += cost[start];
            dfs(next);
        }
    }
}