문제 87

마지막 잎새

내 상태: 미제출
난이도: 87번 문제 난이도 보기

Silver II
출제자: rlatjwls7882
시간 제한: 1000 ms
메모리 제한: 512 MB

태그 보기

그래프 이론불변량 찾기

세종이는 $1$번부터 $N$번까지 번호가 붙은 정점으로 이루어진 트리를 가지고 있다.

세종이는 각 정점 $i$에 대해 다음 과정을 서로 독립적으로 수행한다.

주어진 트리에서 정점 $i$와 정점 $i$에 연결된 모든 간선을 제거한 뒤 다음 연산을 더 이상 수행할 수 없을 때까지 반복한다.

차수가 $2$인 정점 $v$를 하나 선택한다.
정점 $v$와 $v$에 연결된 두 간선을 제거하고, 그 두 간선의 다른 끝점끼리 잇는 간선을 추가한다.

모든 정점 $i$에 대해 위 과정을 수행한 뒤 남아 있는 잎의 수를 구하라.

입력

첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 200\,000)$

두 번째 줄부터 $N-1$개의 줄에 걸쳐 간선으로 연결된 두 정점의 번호를 의미하는 두 정수 $u$, $v$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N; u \neq v)$

출력

첫 번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에 정점 $i$를 제거한 뒤 연산이 끝났을 때 남아 있는 잎의 수를 출력한다.

예제 입력 1

예제 출력 1

노트

트리는 연결되어 있으며 사이클이 없는 그래프이다.

그래프에서 정점에 연결된 간선의 수를 그 정점의 차수라고 한다.

차수가 $1$인 정점을 잎이라고 한다.

공식 해설 풀이 스포일러 보기 접기

정점을 하나씩 지운 뒤 축약 과정을 직접 반복하면 같은 구조를 여러 번 처리하게 된다. 먼저 차수 $2$인 정점의 축약이 정답인 잎 수에 어떤 영향을 주는지 확인한다.

차수 $2$인 정점을 없애는 과정은 생략할 수 있다

차수 $2$인 정점은 잎이 아니다. 이 정점을 없애고 두 이웃을 연결하면 각 이웃은 간선을 하나 잃고 하나 얻으므로 차수가 그대로이다. 따라서 이 연산은 잎의 수를 바꾸지 않는다.

처음에 정점 $i$를 지운 직후의 잎 수만 계산하면 된다. 원래 잎의 수를 $L$, 정점 $v$의 차수를 $d_v$라 하자.

$i$가 잎이었다면 그 잎 하나가 사라진다. 이웃 중 원래 차수가 $1$이던 정점은 차수 $0$이 되어 잎에서 빠지고, 차수가 $2$이던 정점은 차수 $1$이 되어 새 잎이 된다. 다른 정점의 잎 여부는 바뀌지 않는다.

따라서 답은
\[ L-[d_i=1]-\sum_{v\in\operatorname{adj}(i)}[d_v=1] +\sum_{v\in\operatorname{adj}(i)}[d_v=2] \]
이다. $[P]$는 조건 $P$가 참이면 $1$, 거짓이면 $0$을 뜻한다. 차수 $0$인 정점은 잎이 아니므로 $N=1$일 때도 답은 $0$이다.

트리의 모든 인접 리스트 길이의 합은 $2(N-1)$이다. 각 정점의 이웃을 한 번씩 확인하면 전체 시간복잡도와 공간복잡도는 $O(N)$이다.

구현 · 언어별 풀이

C++ 구현

차수 배열과 vector<vector<int>> 인접 리스트를 만든다. 전체 잎 수를 먼저 센 다음, 각 정점의 이웃 중 차수가 $1$인 수와 $2$인 수를 세어 식에 대입한다. 실제 정점이나 간선을 삭제할 필요는 없다.

C 구현

degree와 인접 배열을 만들고 원래 degree가 1인 정점 수를 센다. 제거 후보의 이웃 중 degree 1과 2인 개수로 답을 갱신한다. 실제로 인접 목록을 삭제·복구하지 않으며 N=1은 차수 0이다.

Python 구현

인접 리스트와 원래 degree 배열을 유지한다. 각 후보의 이웃을 합쳐 한 번씩 검사하면 전체 $O(N)$이다. 후보별로 트리를 복사하거나 leaf를 재계산하지 않는다.

Java 구현

int[] degree와 인접 배열로 후보별 변화를 계산한다. 원래 차수 1이면 잎 하나가 제거되고 이웃 차수 2이면 새 잎이 생긴다. 각 후보 계산 후 degree를 변경하지 않는다.

Rust 구현

차수는 usize로 저장해도 후보 답의 중간 뺄셈은 i32로 계산한다. 원래 degree를 바꾸지 않고 이웃의 1·2 여부만 센다. N=1인 고립점은 degree 1인 잎이 아니다.

JavaScript 구현

차수와 인접 리스트를 만들고 원래 차수 $1$인 정점 수 $L$을 센다. 각 삭제 후보 $i$에서 원래 잎 여부를 빼고, 이웃 차수가 $1$이면 하나 빼며 $2$이면 하나 더한다.

let answer = leaves - (degree[i] === 1 ? 1 : 0);
for (const v of adj[i]) {
    if (degree[v] === 1) answer--;
    if (degree[v] === 2) answer++;
}

차수 배열은 Int32Array에 저장할 수 있다. 후보별로 차수 배열을 변경하지 않아야 다음 후보도 원래 트리를 기준으로 계산한다. 축약 연산을 실제로 수행하거나 트리를 매번 복사하지 않는다. $N=1$이면 잎 수도 이웃 수도 $0$이라 같은 식이 답 $0$을 준다.

제출

언어