思路

  此题直接使用暴力求解，在建树之后，对于每一个点计算它的子节点的个数，并用map表记录下来，对于拥有同一个个数子节点的节点，记数量为m，相互之间的组合数量即为C(m,2)，即m*(m-1)/2

代码

python

T = int(input())
while T > 0:
    T -= 1
    n = int(input())

题目内容

小美对于给定的由$n$个节点构成，根节点为$1$的有根树中，我们定义节点$u$和$v$是“相似节点”，当且仅当节点$u$的子点数量$son_u$与节点$v$的子点数量$son_u$相等。

输出“相似节点”的对数。

输入描述

每个测试文件均含多组测试数据。第一行输入一个整数$T$($1≤T≤10^4$)代表数据组数，每组测试数据描述如下：

第一行输入一个整数$n$($1≤n≤100$)代表节点数量。

此后$n-1$行，第$i$行输入两个整数$u_i$和$v_i$($1≤u_i,v_i≤n；u_i≠v_i$)表示树上第$i$条边连接节点$u_i$和$v_i$。保证树联通，没有重边。

除此之外，保证所有的$n$之和不超过$2×10^5$

输出描述

对于每一组测试数据，在一行上输出一个整数，代表图中”相似节点“的对数。

样例1

输入

1
7
1 2
1 3
3 5
3 7
2 4 
2 6

输出

9