C1794 [模拟赛 #测试-D1]高速公路 (highway)

X 国有 $n$ 座城市，$n - 1$ 条道路，每条道路连接两座城市，且任意两座城市都能通过若干条道路相互到达，显然，城市和道路形成了一棵树。

X 国现在想要将树上的两条链对应的所有道路改造成高速公路，为避免改造工程相互影响，这两条链不存在公共点。注意，链可以退化为一个点。

显然，这样会有很多个改造方案。

为评估改造方案的优劣，X 国给每条道路设定了一个重要值，注意，这里重要值越大并不代表这条路越重要。一条链的重要值为这条链上所有道路的重要值之和，当链退化为一个点时，重要值为 $0$。

对于一个改造方案，它的优秀值为两条链的重要值之积。

你需要选择一个优秀值最大的改造方案，并求出它的优秀值。

样例输入 1

6
1 2 3
2 3 -4
4 2 -3
1 5 2
6 5 -1

样例输出 1

7

样例输入 2

6
1 2 3
2 3 -4
4 2 2
1 5 2
6 5 -1

样例输出 2

4