Independent Set (Max)

You are given a tree of $N$ nodes (numbered from $1$ to $N$). The edges are numbered from $1$ to $N - 1$; edge $i$ connects node $U\_i$ and $V\_i$.

A non-empty set of nodes is independent if none of the nodes in the set are adjacent to each other. The following illustration provides an example of sets which are independent, and sets which are not. The nodes colored in red are the members of the set.

The score of an independent set can be calculated as the product of:

• the number of nodes in the set, and
• the minimum number of edges such that all nodes in the set are still connected.

The following illustration provides an example for calculating the score of an independent set. There are $2$ nodes in the set. The minimum number of edges to connect all nodes in the set is $3$, as shown by the edges colored in red. The score of this set is $2 \cdot 3 = 6$.

Note that the score of an independent set consisting of only $1$ node is $0$.

Determine the maximum score over all non-empty independent sets within the tree.

The first line consists of an integer $N$ ($2 ≤ N ≤ 100\\, 000$).

Each of the next $N - 1$ lines consists two integers $U\_i$ $V\_i$ ($1 ≤ U\_i , V\_i ≤ N$). The input edges form a tree.

Output a single integer representing the maximum score over all non-empty independent sets within the tree.