DWITE '11 R2 #4 - Bear Trees

View as PDF
Submit solution
Points: 10
Time limit: 1.0s
Memory limit: 64M
Problem types
DWITE, November 2011, Problem 4

Gary is a bear. He lives in a system of caves, consisting of N caverns, numbered from 0 through N-1. These caverns are connected by bidirectional tunnels, such that there is exactly one path between each pair of tunnels. (You might also know this kind of structure as a "tree", so you'll know that there are exactly N-1 tunnels.)

Gary would like to explore this system of caves, using the following method:

  • Put cavern 0 (his home) on a "to explore" list.
  • Choose one cavern C from the list.
  • Remove C from the list.
  • Explore C: Add all caverns adjacent to C that have never been on the list.
  • Repeat steps 2 to 4 while the list contains at least one cavern.

There are many ways to explore a system of caves. However, bears are forgetful. You would like to find a way to explore the cave such that the maximum length of the list is minimized. For example, given the following tree:

Here is one possible way to explore the tree, where the maximum length of the list is 4:

  • Explore 0, list = \{1, 2, 3\}
  • Explore 2, list = \{1, 3, 4, 5\}
  • Explore 1, list = \{3, 4, 5\}
  • Explore 3, list = \{4, 5, 6\}
  • Explore 4, list = \{5, 6\}
  • Explore 6, list = \{5\}
  • Explore 5, list = \{\}

However, exploring in a different order, Gary can make it such that he never has to remember more than 3 elements; indeed, it is easy to see that 3 is optimal. Gary has retained you to find this minimum list length, given a system of caves.

Input Specification

The input will contain 5 test cases. Each test case will begin with one line, containing the number of caverns 1 \le N \le 1\,000. N-1 lines will follow, each consisting of two distinct space-separated integers x and y, denoting a tunnel between caverns x and y. Of course, no tunnel will be described more than once, and 0 \le x, y < N.

Output Specification

The output will contain 5 lines of output, the minimum list length for each cave system.

Sample Input

7
0 1
0 2
0 3
2 4
2 5
3 6
4
0 1
1 2
2 3

Sample Output

3
1

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments


  • 0
    maxcruickshanks  commented on Nov. 25, 2022, 2:58 a.m.

    Since the original data were weak, an additional test case was added, and all submissions were rejudged.


    • 0
      maxcruickshanks  commented on Jan. 25, 2023, 1:51 a.m. ← edited

      The additional test case has been modified to the input specifications, and all submissions were rejudged.