• [1340] Gain of Two Paths

  • 时间限制: 1000 ms　内存限制: 65535 K
  • 问题描述
  • MatRush的好朋友小X住在Byteland。Byteland有n个城市，通过n-1条双向的道路相连。通过这些道路，你能从任意一个城市到达别的所有城市。小X是个工程师，他被公司派遣去负责修理Byteland的两条路径。一条路径由一系列不重复的城市组成，相邻的城市通过一条道路相连。小X可以自己选择需要修理的两条路径，唯一的限制是这两条路径不能相交(即不能包含共同的城市)。而小X将获得的报酬是两条路径的长度的乘积。假设每条道路的长度为1，而一条路径的长度是路径中所有道路的长度的和。请帮助小X计算出他能获得的最大报酬。
  • 输入
  • 输入包含多组数据，第一行是一个整数T，表示共有T组数据。 每组数据的第一行是一个整数n(2≤n≤500)，表示城市的个数。接下来n-1行是两个整数ui和vi(1≤i≤n-1, 1≤ui, vi≤n)，由空格 隔开，表示城市ui和vi之间有一条道路。
  • 输出
  • 输出T行，每行是一个整数，即对应数据下小X能获得的最大报酬。
  • 样例输入
  • 2
4
1 2
1 3
1 4
6
1 2
2 3
2 4
5 4
4 6
  • 样例输出
  • 0
4
  • 提示
  • 无
  • 来源
  • Matrush@ZJUT
  • 操作

显示春菜