问题陈述
通过递归应用以下规则来定义有根树中节点的深度:
- 根节点的深度为0。
- 父节点深度为 $d$ 的子节点的深度为 $d+1$。
设 $S(T, d)$ 为深度为 $d$ 的 $T$ 的节点数。 当且仅当对于所有非负整数 $d$,$S(T, d)$ 等于 $S(T', d)$ 时,两棵有根树 $T$ 和 $T'$ 相似。
给你一个有根树$T$,有$N$个节点。 $T$ 的节点编号从 1 到 $N$。节点1是$T$的根节点。 令$T_i$ 为$T$ 的有根子树,其根为节点$i$。 您的任务是编写一个程序来计算 $(i, j)$ 对的数量,使得 $T_i$ 和 $T_j$ 相似且 $i < j$。
输入
输入由单个测试用例组成。
$N$
$a_1$ $b_1$
…
$a_{N-1}$ $b_{N-1}$
第一行包含一个整数 $N$ ($1 \le N \le 100{,}000$),它是树中的节点数。 下面的$N-1$行给出了分支的信息:其中第$i$行包含$a_i$和$b_i$,这表明节点$a_i$是节点$b_i$的父节点。 ($1 \le a_i, b_i \le N$, $a_i \ne b_i$) 根节点编号为1。 保证给定的图是一棵有根树,即除了节点 1 之外的每个节点都只有一个父节点,并且该图是连通的。
输出
打印节点对 $(x,y)$ 的数量,使得具有根 $x$ 的子树和具有根 $y$ 的子树相似且 $x < y$。
示例输入 1
5 1 2 1 3 1 4 1 5
样本输入 1 的输出
6
示例输入 2
6 1 2 2 3 3 4 1 5 5 6
样本输入 2 的输出
2
示例输入 3
13 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 6 10 7 11 8 12 11 13
样本输入 3 的输出
14