Nested Rubber Bands
Time limit1sMemory limit1024 MB
Given a tree of n vertices, find the largest set of pairwise non-adjacent vertices that can be nested as rubber bands.
- Level
Medium5 of 10
- Topics
- Tree, Dynamic programming
- Solved
- No attempts yet
Problem
You have a tree of vertices. You are going to convert this tree into rubber bands on an infinitely large plane. The conversion follows these rules:
- For every pair of vertices and , rubber bands and intersect if and only if there is an edge between and in the tree.
- Each rubber band has the shape of a simple loop. In other words, a rubber band is a loop that does not intersect itself.
We define the following terms:
- Rubber band includes rubber band if and only if rubber band lies inside the area of rubber band and the two do not intersect.
- A sequence of rubber bands () is nested if and only if for every (), includes .

This is an example of a conversion. Rubber bands and are nested.
It can be proved that a conversion and a nested sequence of rubber bands satisfying the constraints always exist.
What is the maximum length of a nested sequence of rubber bands that can be obtained from the given tree? Find it and print it.
Input
The first line contains an integer (), the number of vertices in the tree.
The -th of the next lines contains two integers and (), meaning there is an edge between and . The given graph is guaranteed to be a tree on vertices.
Output
Print the answer.
Hint
In the first input, you can obtain a nested sequence of rubber bands (, , , and ) with the conversion shown below. Other conversions also produce a nested sequence of rubber bands. However, no nested sequence of or more rubber bands can be made from this tree.

One possible conversion for the second input is shown below.
