[백준] 14267번 : 회사 문화 1

문제

 

 

접근 방식

내리 칭찬이 있어서 부하는 상사가 받은 칭찬 + 상사한테 받을 칭찬을 받을 수 있다.

 

트리에서 상사는 부모고 부하는 자식이니 루트부터 방문을 하면서

부하에게 현재까지 본인이 받은 칭찬을 넘겨주기만 하면 된다.

 

조심해야할게 한 명의 부하가 여러번 칭찬을 받을 수 있어서

입력을 받을 때

부하 번호 = 부하가 직속 상사로부터 받은 칭찬 이 아니라

부하 번호 += 부하가 직속 상사로부터 받은 칭찬 이 되어야 한다.

 

 

풀이

public class Main {

	private static final ArrayList<ArrayList<Integer>> near = new ArrayList<>();
	private static int[] compliments;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int p;
		compliments = new int[n + 1];

		for (int i = 0; i <= n; i++) {
			near.add(new ArrayList<>());
		}

		st = new StringTokenizer(br.readLine());

		for (int i = 1; i <= n; i++) {
			p = Integer.parseInt(st.nextToken());
			if (p == -1) continue;

			near.get(p).add(i);
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			compliments[Integer.parseInt(st.nextToken())] += Integer.parseInt(st.nextToken());
		}

		dfs(1);

		for (int i = 1; i <= n; i++) {
			sb.append(compliments[i]).append(" ");
		}

		System.out.println(sb);
	}

	private static void dfs(int cur) {
		for (int next : near.get(cur)) {
			compliments[next] += compliments[cur];
			dfs(next);
		}
	}
}