树上路径

题目描述 给你一棵�个点的树，你想找到四个不同的节点�, �, �, �满足从�到�的简单路径与从 �到�的简单路径不相交(不存在公共的点)。记从�到�的简单路径的上节点的个数为 � �, � 。

想知道有序的二元组 � �, � , � �, � 有多少种不同的取值。

输入格式 第一行，一个整数�。

接下来� − 1 行，每行两个整数�, �表示一条树边。

输出格式 一行一个整数，表示答案。

样例输入 1 5 1 2 2 3 3 4 3 5

样例输出 1 10

样例解释 下面是所有可能的二元组： 1,1 , 1,2 , 1,3 , 1,4 , 2,1 , 2,2 , 2,3 , 3,1 , 3,2 , 4,1 。

样例输入输出 2 见下发文件。

数据规模 共 10 组数据。

测试点 1,2 满足 1 ≤ � ≤ 100。

测试点 3,4,5 满足 1 ≤ � ≤ 103 。

测试点 6,7 满足 1 ≤ � ≤ 105 。

对于 100% 的数据，满足 1 ≤ � ≤ 5 × 105 。