깊이별 노드 수
실버 V의견: 0
숲 공원에는 \(N\)개의 나무 전망대가 있고, 이 전망대들은 \(N-1\)개의 다리로 연결되어 나무(트리) 구조를 이룬다.
공원 관리자는 루트 전망대 \(R\)에서 출발해 최소 \(K\)개의 다리를 건너야 도달할 수 있는 전망대, 즉 깊이가 정확히 \(K\)인 전망대의 수가 궁금하다.
루트를 \(R\)로 하는 트리에서 깊이가 \(K\)인 노드의 수를 구하여라. 루트의 깊이는 \(0\)이다.
- \(1 \le N \le 100\,000\)
- \(1 \le R \le N\)
- \(0 \le K \le N-1\)
첫째 줄에 전망대의 수 \(N\), 루트 번호 \(R\), 깊이 \(K\)가 공백으로 구분되어 주어진다.
다음 \(N-1\)개의 줄에 다리로 연결된 두 전망대의 번호가 공백으로 구분되어 주어진다.
깊이가 \(K\)인 전망대의 수를 출력한다.
6 1 2
1 2
1 3
2 4
2 5
3 6
3
루트 \(1\)에서의 깊이: 노드 \(1\)이 \(0\), 노드 \(2\)·\(3\)이 \(1\), 노드 \(4\)·\(5\)·\(6\)이 \(2\)이다. 깊이 \(2\)인 노드는 \(3\)개이다.
4 1 1
1 2
2 3
3 4
1
경로 그래프 \(1\)-\(2\)-\(3\)-\(4\)에서 루트 \(1\) 기준 깊이 \(1\)인 노드는 \(2\) 하나뿐이므로 \(1\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
깊이별 노드 수
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
깊이별 노드 수