SP6717 Two Paths

题目描述

在 Flatland,有 $N$ 个城市通过 $N - 1$ 条双向道路相连,城市编号从 $1$ 到 $N$。你可以通过这些道路从一个城市到达另一个城市。 Two Paths 公司中标了在 Flatland 修复两条道路的项目。一条道路是由不同城市按顺序连接而成的路径。公司可以自行选择修复哪两条路径,但必须确保这两条路径没有共同的城市。 已知 Two Paths 公司通过修复道路获得的利润等于这两条路径长度的乘积。每条道路的长度为 $1$,因此路径的长度就是其包含的道路数量。需要计算出公司能获得的最大利润。

输入格式

第一行是一个整数 $N$($2 \le N \le 100000$),表示 Flatland 中的城市数量。接下来的 $N - 1$ 行描述了这些城市之间的道路连接情况,每行给出两个城市编号 $a$ 和 $b$($1 \le a, b \le N$),表示这两个城市之间有一条道路相连。

输出格式

输出最大的可能利润。