#P2009. 2024.9.7-MT-第3题-相似节点的对数(开发第二题)

2024.9.7-MT-第3题-相似节点的对数(开发第二题)

题目内容

小塔对于给定的由nn个节点构成，根节点为11的有根树中，我们定义节点uu和vv是“相似节点”，当且仅当节点uu的子点数量sonuson_u与节点vv的子点数量sonuson_u相等。

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

输入描述

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

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

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

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

输出描述

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

样例1

输入

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

输出

9

知识点:*****

查看知识点以及同类型题目

Statistics