hyperopia

Let $\varnothing$ denote the forest with no edges. For a forest $F$ and a vertex $v$, define $F-v$ as the forest obtained by deleting every edge incident to $v$. The vertex itself is not deleted.

The information visible to the Ddas on vertex $v$ is exactly $F-v$. In particular, there is exactly one possible forest in which their degree is $0$: the forest $F-v$.

Let $S(F)$ be the first day on which someone becomes certain in forest $F$, and define $S(\varnothing)=0$. Immediately after Dadas's announcement, the empty forest is eliminated from the possible worlds.

Suppose that the actual forest is $F$ and everyone has declared uncertainty during the previous $d-1$ days. The Ddas on vertex $v$ becomes certain on day $d$ exactly when the degree-$0$ world $F-v$ is inconsistent with the previous declarations. Therefore,

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

This recurrence is exactly the recurrence for the size of a minimum vertex cover.

Let $\tau(F)$ be the size of a minimum vertex cover of $F$. If there are no edges, $\tau(F)=0$. If vertex $v$ is selected, every edge incident to $v$ is covered, and the remaining problem is the minimum vertex cover of . Thus,

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

The two recurrences and their base cases are identical, so $S(F)=\tau(F)$.

It remains to compute the minimum vertex cover size of the given forest. Root every tree at an arbitrary vertex. For the subtree of a vertex $u$, define:

• $\mathrm{dp}_0[u]$: the minimum vertex cover size when $u$ is not selected
• $\mathrm{dp}_1[u]$: the minimum vertex cover size when is selected

For every child $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]).$$

For every connected component with root $r$, add $\min(\mathrm{dp}_0[r],\mathrm{dp}_1[r])$ to the answer.

A recursive DFS may overflow the call stack on a path of length $200\,000$. Build a traversal order iteratively and evaluate the DP in reverse order.

The time complexity is $O(N+M)$, and the space complexity is $O(N+M)$.

Solution written by GPT5.6