https://www.acmicpc.net/problem/15681
15681번: 트리와 쿼리
트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)
www.acmicpc.net
트리의 부모배열 설정법과, 서브트리 크기를 DP로 알아내는 문제다
DFS와 유사하며, 로직 설명은 해당 문제링크 하단에 자세하게 설명되어 있다
쓸 필요 없지만 굳이 짧게 요약하자면
- parent 배열, size 배열을 쓴다
- size[x] : x 정점에서의 서브트리 속한 정점의 수
- 기본적으로 서브트리 정점의 수는 1이고, 해당 정점 하위에 정점들이 더 있다면, dfs를 통해서 자동적으로 바텀업 형식으로 해당 정점 서브트리의 크기에 더해지는 형식이다
- 이 문제에는 굳이 parent 배열을 쓸필요가 없긴 하다, 그러나 학습을 위해서 썼다
- 굳이 DFS를 두번 돌려서 문제를 풀 필요 없다. size랑 parent는 한번의 dfs로 다 구할 수 있다
문제에서 의도하는 정석 코드
https://github.com/KimximyaFan/Random-Defense/blob/main/C0038.java
최적화 된 코드
https://github.com/KimximyaFan/Random-Defense/blob/main/C0039.java
'PS 짬통 > 골드' 카테고리의 다른 글
| 2213 트리의 독립집합 (1) | 2023.10.19 |
|---|---|
| 2533 사회망 서비스(SNS) (0) | 2023.10.16 |
| 11780 플로이드 2 (0) | 2023.10.11 |
| 11779 최소비용 구하기 2 (1) | 2023.10.10 |
| 9019 DSLR (1) | 2023.10.08 |
