MLE '19 Contest 2 P2 - Meta


Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type

In any tree, the diameter of the tree is the maximum number of nodes of any simple path. Of course, there can only be one maximum. However, there may be multiple simple paths that are the maximum. The metadiameter of the tree is a path consisting of the intersecting nodes of all of these diameter paths. Given a tree of \(N\) nodes, what is the number of nodes in the metadiameter?

Input Specification

The first line will contain the integer \(N\) \((1 \le N \le 10^5)\), the number of nodes.

The next \(N-1\) lines will each contain two integers, \(u, v\) \((1 \le u, v \le N)\), indicating that nodes \(u\) and \(v\) are connected by an edge. It is guaranteed that the edges form a fully connected tree.

Output Specification

Output the number of nodes in the metadiameter of the tree.

Subtasks

Subtask 1 [25%]

\(N \le 20\)

Subtask 2 [75%]

No further constraints.

Sample Input 1 (Subtask 1)

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

Sample Output 1

1

Sample Input 2 (Subtask 2)

22
1 2
2 3
2 4
2 5
2 6
6 7
7 8
8 9
9 10
10 11
10 12
10 13
10 14
9 15
15 16
15 17
15 18
15 19
15 20
7 21
7 22

Sample Output 2

5

Comments

There are no comments at the moment.