## Editorial for Yet Another Contest 6 P2 - No More Telemarketers

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

We can rephrase this problem in terms of graph theory, whereby we need to transform a rooted tree by disconnecting and reconnecting the tree. Refer to the initial tree as , and the desired tree as . Clearly, the root of the tree cannot change, so if and have different roots, then no solution exists. Otherwise, a solution exists, which can be proved through the following construction.

Each move updates the parent of at most one node, which lower bounds the answer at the number of mismatches between and . In fact, the following construction shows that this lower bound is actually achievable.

We process nodes by the DFS ordering of . When we process a node , we update its parent to if necessary. This works because when we process node , then all of the ancestors of node in will already be in the correct position in the current tree. Actually, a BFS ordering of works for the same reason. In fact, if we consider edges in to be directed away from the root, then any topological ordering of suffices.

As a final note, note that reversing the order of the moves yields a valid reorganisation of the tree from to . This implies that we could instead direct the edges in *towards* the root, and process the nodes in any topological ordering.

**Time complexity:**

## Comments