[백준] 14267 회사 문화1

문제링크 : www.acmicpc.net/problem/14267

14267번: 회사 문화 1

1번인 사장을 제외하고 모든 사원은 직속 상사를 1명을 가지기 때문에 회사 구조를 트리 형태라고 할 수 있다.

칭찬은 해당직원을 상사로 갖는 모든 부하로 계속 전파하기 때문에 연결된 모든 하위 트리를 탐색하면 된다.

그것을 구현하기 위해 dfs를 사용하였다.

처음에, M번 쿼리가 발생할 때마다 dfs를 수행하는 비효율적인 방법으로 코드를 짰었다.

이는 단순히, 쿼리에 대해 직원의 cost를 미리 저장 해두고 dfs 수행 시 cost를 중첩해 가면서 진행하면 빠르게 해결 된다.

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

public class Main {
	public static int N,M;
	public static ArrayList<Integer> adj[];
	public static int ans[];
	public static int weight[];
	public static void dfs(int person, int cost) {
		ans[person]+= cost;
		for(int i=0;i<adj[person].size();i++) {
			int next = adj[person].get(i);
			dfs(next,cost + weight[next]);
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		adj = new ArrayList[N+1];
		for(int i=1;i<=N;i++) {
			adj[i] = new ArrayList<Integer>();
		}
		weight = new int[N+1];
		ans = new int[N+1];
		st = new StringTokenizer(br.readLine());
		st.nextElement();
		for(int i=2;i<=N;i++) {
			int num = Integer.parseInt(st.nextToken());
			adj[num].add(i);
		}
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int person = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			weight[person] += cost;
		}
		dfs(1,weight[1]);
		StringBuilder sb = new StringBuilder();
		for(int i=1;i<=N;i++) {
			sb.append(ans[i] + " ");
		}
		System.out.println(sb.toString());
	}

}