← 23주차 · 트리 DP와 문자열 매칭
보통트리DFS트리 DP

서브트리의 크기

정점 개수 n과 무방향 간선 목록 edges로 이루어진 트리가 주어져요. 정점은 0번부터 n-1번까지이고, 0번을 루트로 봐요.

각 정점 v의 서브트리 크기(자기 자신과 모든 자손을 합한 정점 수)를 담은 배열을 반환해요.

자식의 답을 모아 부모의 답을 만드는 순서로 풀어요. 루트에서 DFS로 내려갔다가 돌아오면서 각 정점의 크기를 '1 + 자식들의 크기 합'으로 정해요. 트리 DP의 가장 기본 형태예요.

예시

예시 1
입력
n = 5, edges = [[0, 1], [0, 2], [1, 3], [1, 4]]
출력
[5, 3, 1, 1, 1]
설명
0의 서브트리는 전체(5), 1은 자신과 3·4로 3, 잎(2·3·4)은 각각 1이에요.
예시 2
입력
n = 1, edges = []
출력
[1]

제한 사항

  • 1 ≤ n ≤ 50,000
  • edges.length는 n - 1이고, 그래프는 트리예요(사이클 없이 모두 연결).
  • 0 ≤ a, b < n
간선으로 인접 리스트를 만들고, 크기 배열을 1로 시작해요. dfs(v, parent)에서 부모가 아닌 이웃(=자식)마다 재귀로 내려간 뒤 그 자식의 크기를 v의 크기에 더해요. 0번에서 DFS를 시작하면 돼요.
javascript
function subtreeSizes(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const size = new Array(n).fill(1);
  function dfs(v, parent) {
    for (const next of adj[v]) {
      if (next === parent) continue;
      dfs(next, v);
      size[v] += size[next];
    }
  }
  dfs(0, -1);
  return size;
}
이전 문제도시 연결하기 (프림)
다음 문제트리의 지름
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.