hyperopia

간선이 없는 포레스트를 $\varnothing$로 쓰자. 포레스트 $F$와 정점 $v$에 대하여 $F-v$를 $v$에 인접한 모든 간선을 삭제한 포레스트로 정의한다. 정점 자체는 삭제하지 않는다.

정점 $v$에 있는 따스가 보는 정보는 $F-v$와 정확히 같다. 특히 자신의 차수가 $0$인 가능성을 생각하면, 그 가능성에 해당하는 포레스트는 유일하게 $F-v$이다.

$S(F)$를 포레스트 $F$에서 누군가가 처음으로 확신하는 날짜로 정의하고, $S(\varnothing)=0$으로 둔다. 다다스의 선언 직후에는 빈 포레스트가 가능한 세계에서 제외된다.

실제 포레스트가 $F$이고 이전 $d-1$일 동안 모두가 알 수 없다고 선언했다고 하자. 정점 $v$의 따스가 $d$일에 확신하려면, 자신의 차수가 $0$인 세계 $F-v$가 이전 선언들과 모순이어야 한다. 따라서 다음 점화식이 성립한다.

$$S(F)=1+\min_{v:\deg_F(v)>0} S(F-v)$$

이 점화식은 최소 정점 커버의 크기와 같다.

포레스트 $F$의 최소 정점 커버 크기를 $\tau(F)$라고 하자. 간선이 없으면 $\tau(F)=0$이다. 정점 $v$를 정점 커버에 넣으면 $v$에 인접한 모든 간선이 덮이고, 남은 문제는 의 최소 정점 커버이다. 따라서

$$\tau(F)=1+\min_{v:\deg_F(v)>0} \tau(F-v)$$

가 성립한다. 위 두 점화식과 초기값이 같으므로 $S(F)=\tau(F)$이다.

이제 주어진 포레스트의 최소 정점 커버 크기를 구하면 된다. 각 트리를 임의의 정점에서 루트가 있는 트리로 만든다. 정점 $u$의 서브트리에 대하여 다음 DP를 정의한다.

• $\mathrm{dp}_0[u]$: $u$를 선택하지 않을 때 서브트리의 최소 정점 커버 크기
• $\mathrm{dp}_1[u]$: 를 선택할 때 서브트리의 최소 정점 커버 크기

자식 $w$에 대해 다음 전이가 성립한다.

$$\mathrm{dp}_0[u]=\sum_w \mathrm{dp}_1[w]$$ $$\mathrm{dp}_1[u]=1+\sum_w \min(\mathrm{dp}_0[w],\mathrm{dp}_1[w])$$

각 연결 요소의 루트 $r$에서 $\min(\mathrm{dp}_0[r],\mathrm{dp}_1[r])$를 더하면 답을 얻는다.

재귀 DFS는 길이 $200\,000$인 경로에서 호출 스택이 넘칠 수 있다. 반복 DFS로 정점 순서를 만든 뒤 역순으로 DP를 계산하는 것이 안전하다.

시간 복잡도는 $O(N+M)$이고, 공간 복잡도는 $O(N+M)$이다.

Solution written by GPT5.6