8053 : 트리 탐색과 서브트리 크기
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
한 회사의 조직도가 루트가 $1$번 노드(사장)인 트리 구조로 주어집니다.
각 직원 $i$ ($2 \le i \le N$)에 대해 그들의 직속 상사 $p_i$가 주어질 때, 각 직원에 대해 그들의 하위 직원(즉, 해당 직원의 서브트리에 속한 자식 및 후손들의 총수)의 수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 200{,}000$
• $1 \le p_i < i$
각 직원 $i$ ($2 \le i \le N$)에 대해 그들의 직속 상사 $p_i$가 주어질 때, 각 직원에 대해 그들의 하위 직원(즉, 해당 직원의 서브트리에 속한 자식 및 후손들의 총수)의 수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 200{,}000$
• $1 \le p_i < i$
입력 설명
첫째 줄에 직원의 수 $N$이 주어집니다. ($1 \le N \le 200{,}000$)
둘째 줄에 $2, 3, \dots, N$번 직원의 직속 상사 $p_2, p_3, \dots, p_N$이 공백으로 구분되어 주어집니다. ($1 \le p_i < i$)
둘째 줄에 $2, 3, \dots, N$번 직원의 직속 상사 $p_2, p_3, \dots, p_N$이 공백으로 구분되어 주어집니다. ($1 \le p_i < i$)
출력 설명
$1$번 직원부터 $N$번 직원까지 각 직원의 하위 직원 수를 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1 1 2 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4 1 1 0 0도움
부모 노드의 번호 $p_i$는 항상 $i$보다 작기 때문에, 노드 번호의 역순($N$부터 $2$까지)으로 탐색하면서 부모 노드에 값을 누적해 나가면 재귀 호출 없이 $O(N)$ 시간 복잡도로 안전하게 해결할 수 있습니다.