#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/2/problems/f

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/2/problems/f

Repovive

Consecutive Subtree - Repovive Premier Round 1 | Repovive | Repovive

Back

Code

Upload

Submissions

Problem

2F. Consecutive Subtree

3000 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Page 1

Root the tree at vertex $1$ .

Consider any valid sequence of operations that deletes all vertices. Each operation deletes a set of currently present vertices whose labels form a consecutive set. So the whole process partitions the labels $1,2,\dots,n$ into consecutive intervals, because every deleted set is consecutive, and deleted sets are disjoint, and their union is all vertices.

Now take any interval $[l,r]$ from such a partition, and look at the induced subgraph on vertices $\{l,l+1,\dots,r\}$ inside the original tree. Because the original graph is a tree, the induced subgraph is a forest, so it consists of some connected components.

Pick one connected component $C$ of this induced subgraph. Let $x = \mathrm{LCA}(C)$ in the rooted tree. Among all components of the interval, choose the component whose $\mathrm{LCA}$ has maximum depth, meaning it is the lowest LCA.

Claim: for this chosen component, $C$ is exactly a subtree of $x$ restricted to the still remaining vertices of the interval, so it can be deleted by one operation by choosing vertex $x$ .

Reason: All vertices of $C$ lie in the subtree of $x$ by definition of LCA. If there were a vertex $y$ in the subtree of $x$ that is inside the interval but not in $C$ , then $y$ would be separated from $C$ only by vertices outside the interval. That would force the induced subgraph to have another component whose LCA is strictly below $x$ , contradicting the choice of $C$ as having the lowest LCA.

So in every interval $[l,r]$ , if its induced subgraph is connected, then it can be deleted in one operation by choosing $v = \mathrm{LCA}([l,r])$ . Therefore the problem is equivalent to partitioning $[1,n]$ into intervals such that each interval induces a connected subgraph.

Root the tree at vertex $1$ .

Claim: for this chosen component, $C$ is exactly a subtree of $x$ restricted to the still remaining vertices of the interval, so it can be deleted by one operation by choosing vertex $x$ .