Mirror IIOT 2023-2024 Round I | Long Chain

This was the problem page during the contest. Access the current page here.
Time limit: 0.5s Memory limit: 64MB Input: Output:

You are given a tree with NN vertices, numbered from 11 to NN (a tree is an undirected connected graph in which there are no cycles).
You are asked to partition it into edge-disjoint simple paths such that the length of the shortest one is maximized.

In this task, the length of a path is defined as the number of edges it has.

Input data

The first line contains an integer NN. The next N1N - 1 lines contain 22 integers ui,viu_i, v_i, denoting an edge of the tree.

Output data

You need to write a single line with an integer: the maximum length of the shortest path over all partitions of the tree into edge-disjoint simple paths.

Constraints and clarifications

  • 2N100 0002 \leq N \leq 100 \ 000.
  • 1ui,viN1 \leq u_i, v_i \leq N.
  • For tests worth 1010 points, N8N \leq 8.
  • For tests worth 2020 more points, N100N \le 100.
  • For tests worth 2020 more points, N1000N \le 1000.

Example 1

stdin

9
9 8
7 4
7 8
2 1
6 3
5 1
5 8
3 8

stdout

4

Explanation

In the first sample case, an optimal split would be into 22 edge-disjoint paths, each of length 44: 215892-1-5-8-9 and 478364-7-8-3-6.

Example 2

stdin

5
1 2
2 3
3 4
2 5

stdout

2

Explanation

In the second sample case, an optimal split would be into 22 edge-disjoint paths, each of length 22: 1251-2-5 and 2342-3-4.

Example 3

stdin

10
7 6
9 6
8 5
4 2
1 3
5 6
1 10
7 10
2 6

stdout

4

Explanation

In the third sample case, an optimal split would be into 22 edge-disjoint paths, one of length 44: 426584-2-6-5-8 and the other one of length 55: 31107693-1-10-7-6-9.

Example 4

stdin

6
1 2
2 3
3 4
4 5
5 6

stdout

5

Explanation

In the fourth sample case, the whole tree consists of only one path of length 55.

Log in or sign up to be able to send submissions!