Spliting a tree

Let $\deg(v)$ denote the degree of vertex $v$.

If $\deg(v) \geq 2$, the answer is $0$. Removing only $v$ separates the tree into exactly $\deg(v)$ connected components, one for each direction incident to $v$.

Now suppose that $v$ is a leaf. Let $b$ be the nearest vertex of degree at least $3$, and let $d$ be the distance between $v$ and $b$.

For every $k<d$, the removed vertices form one simple path starting at $v$. Before reaching its endpoint, this path contains no vertex of degree at least $3$, so the remaining graph is connected or empty. It cannot have at least two connected components.

For $k=d$, vertex $b$ is also removed. Even after excluding the direction from $b$ toward $v$, at least two other directions remain incident to $b$. After removing $b$, those directions belong to different connected components. Therefore the answer for the leaf is .

If the tree has no vertex of degree at least $3$, it is a path. Removing any radius around a leaf leaves another path or the empty graph, so the answer is $-1$. The same conclusion applies when $N=1$.

Thus the answers are characterized as follows.

• A vertex of degree at least $2$ has answer $0$.
• A leaf has answer equal to its distance from the nearest vertex of degree at least $3$. If no such vertex exists, its answer is $-1$.
• A vertex of degree $0$ has answer $-1$.

Run a multi-source BFS starting from every vertex of degree at least $3$. This computes the distance from every vertex to its nearest such vertex in one traversal.

The time complexity is $O(N)$, and the memory complexity is $O(N)$.