ZZZ's Site

狗蛋儿

26 July 2020

[Codeforces 1375G] Tree Modification

by zzz

Problem Description

Problem Link You are given a tree with n vertices. You are allowed to modify the structure of the tree through the following multi-step operation:

  1. Choose three vertices a, b, and c such that b is adjacent to both a and c.
  2. For every vertex d other than b that is adjacent to a, remove the edge connecting d and a and add the edge connecting d and c.
  3. Delete the edge connecting a and b and add the edge connecting a and c.

Find the minimum number of operations that must be performed to transform the tree into a star. A star is a tree with one vertex of degree n−1, called its center, and n−1 vertices of degree 1.

Solution

Let’s consider a simplified version, the same question on a tree with fixed root and we are turning the tree to a star with root of degree n-1.

  1. First, we need to apply the operation with root as c, a vertex of depth 1 as b, and a vertex of depth 2 as a. There are number of vertices of depth 2 operations in total.
  2. After the operation, the subtree with sub root as a vertex of depth 3, connects to the root. From the subtree, we need to continue to apply the operation. There are number of vertices of depth 4 operations in total.
  3. Therefore, the answer of the simplified problem is number of vertices of even depth - 1(the root).

Vertices of even depth could be vertices of odd depth if we choose the root differently. There are only two possible answers and we can choose the min of them.

Looking back

By applying the methods of transformation to a simple problem, and merging the operations, the problem can be easily solved.

tags: Codeforces - Inductive - Tree

Posts

subscribe via RSS