문제 이해

트리가 주어진다.
한 개 Node가 칭찬을 i만큼 받을 것이다. 이 때 칭찬은 직속 상사(부모 Node)로부터 받을 수 있다.
그렇다면 칭찬을 받은 Node를 Root로 하는 SubTree의 모든 Node들 또한 i만큼 칭찬 받는다.

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

• 단 1번은 사장으로, Root Node이다.

---

문제 풀이

이전 트리와 쿼리 문제와는 달리, 이번 문제는 부모 Node가 자식 Node에 영향을 끼치는 문제이다.
따라서, DFS를 활용해도 되고, BFS를 활용해도 될 것이다.
"한 개의 Node의 칭찬 수치 = 부모 Node의 칭찬 수치 + 자신이 직접 받은 칭찬 수치"만 지켜지면 될 것이다.

이 문제를 풀기 위해서 DFS를 활용했다.

먼저, 트리를 생성한 이후 "ans[칭찬 받은 사람] = 칭찬 받은 수치" 값을 저장했다.
이후 부모 Node를 시작으로 dfs를 수행했다.
dfs는 파라미터로써 현재 검사할 Node의 번호를 넘겨받고, 아래와 같은 알고리즘을 수행한다.

1. ans[자식 Node] = ans[자식 Node] + ans[현재 Node]

   • 트리를 생성한 직후 ans[칭찬 받은 사람] = 칭찬 받은 수치 값을 저장했으므로, 자신이 직접 받은 칭찬이 존재한다면 ans[현재 Node]에 저장이 되어 있을 것이다

2. 1번 알고리즘을 현재 Node의 모든 자식들에 대하여 수행해 준 이후, dfs(자식 Node)를 수행한다.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N, M;
	static ArrayList<Integer>[] edges;
	static int[] ans;
	
	static void dfs(int start) { 
        // start : 부모 Node의 번호
		for(int s:edges[start]) { // s : start Node의 자식 번호
			ans[s] += ans[start];
            // ans[s]에는 0 혹은 가장 먼저 칭찬 받은 직원 수치가 
            // 저장되어 있을 것이다.
            // 따라서, ans[부모 Node]만 더해주면 조건을 충족시킬 것이다.
			dfs(s);
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		edges = new ArrayList[N+1];
		ans = new int[N+1];
		
		for(int i =0;i<N+1;i++) {
			edges[i] = new ArrayList<>();
		}
		
		sc.nextInt();
		for(int i =2;i<N+1;i++) { // 트리 구성
			int tmp = sc.nextInt();
			edges[tmp].add(i); 
            // tmp의 자식은 i
            // edges[부모 Node]에는 자식 Node들이 저장되어 있음
		}
		
		for(int i =0;i<M;i++) {
			ans[sc.nextInt()] += sc.nextInt();
            // 가장 먼저 칭찬 받은 직원들의 수치를 기록한다.
		}
		
		dfs(1); // 1이 Root이므로 dfs(1) 수행
		
		for(int i =1;i<N+1;i++) {
			sb.append(ans[i]).append(" ");
		}
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 4,5번째 줄 시간 초과
  칭찬을 가장 먼저 받은 사람들을 다른 공간에 저장하여 저장된 사람의 배열 값을 계산할 때 사용하는 방식을 사용하였다. 하지만, 반복문을 통해 계속해서 칭찬을 받은 직접적인 사람인지 아닌지를 확인해야했다.
  초기에 ans공간에 값을 직접적으로 입력하여 반복문을 생략함으로써 해결했다.

• 3번째 줄 틀렸습니다 : list[부모 Node]가 자식 Node 값들을 저장하도록 했어야 했는데, list[자식 Node]가 부모 Node 값을 저장하게 설정하여 틀렸다.

• 2번째 줄 틀렸습니다 : 같은 사람이 2번 칭찬 받을 수 있다. 2번 사람이 2만큼 칭찬을 받았는데, 2번 사람이 또 3만큼 칭찬 받을 수 있다. 이 경우 2번 사람은 총 5만큼 칭찬 받은 것이다. 따라서, ans에서 처음 칭찬받은 사람들에 대해 값을 초기화 할 때
  ans[sc.nextInt()] = sc.nextInt()가 아닌 ans[sc.nextInt()] += sc.nextInt()여야 한다.