Independent Set (Max)

Time limit1sMemory limit2048 MB

Summary

Given a tree, find the maximum of (set size) times (minimum edges connecting the set) over all non-empty sets of pairwise non-adjacent nodes.

Level: Hard8 of 10
Topics: Tree, Dynamic programming, DFS
Solved: No attempts yet

Problem

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 no two nodes in the set are adjacent. The following illustration shows sets that are independent and sets that are not. The nodes colored in red are the members of the set.

The score of an independent set is the product of:

the number of nodes in the set, and
the minimum number of edges needed to keep all nodes in the set connected.

The following illustration shows how to calculate the score of an independent set. The set has $2$ nodes. The minimum number of edges needed to connect them is $3$ , shown in red. The score of this set is $2 \cdot 3 = 6$ .

A set with only $1$ node has a score of $0$ .

Find the maximum score over all non-empty independent sets in the tree.

Input

The first line contains an integer $N$ ( $2 \le N \le 100\,000$ ). Each of the next $N - 1$ lines contains two integers $U_i$ and $V_i$ ( $1 \le U_i, V_i \le N$ ). The input edges form a tree.

Output

Print a single integer, the maximum score over all non-empty independent sets in the tree.

Examples2

Example 1
Input
```
5
1 2
1 3
3 4
3 5
```
Expected output
```
12
```
Example 2
Input
```
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
```
Expected output
```
28
```