All Star#12970

All Star (Розбір)

Author:

Pavle Martinović

Solved by:

First to solve:

UniBuc_KoalifiedKoalas

Let be the largest degree of a node in the tree. We will prove that the answer is n-1-d.

First, we can immediately notice that if we make a move on outhouses and , we will increase the degree of by and decrease the degree of by . This means that we can increase the maximum degree in the tree by at most in each move. Since a star has maximum degree n-1, we need to make at least n-1-d moves.

Now we actually need to find a sequence of n-1-d moves. Let be a vertex with degree . Suppose that the tree isn’t a star with center . Then there exists a path of length starting at ; say s-x-y. Preforming a move on these vertices disconnects and , and connects to , increasing the degree of by . So, as long as the tree isn’t a star, we can increase the degree of by , and so we can preform n-1-d moves to get to have degree n-1.

We can either simulate the above algorithm, taking to find the move in each step (leading to total time complexity O(N^2)). Alternatively, one can easily notice that running a DFS algorithm from and outputting s-x-y for every edge we encounter not incident to in order will essentially do the same thing as the above paragraph describes in time (this can be proven by induction, say).