此题直接使用暴力求解,在建树之后,对于每一个点计算它的子节点的个数,并用map表记录下来,对于拥有同一个个数子节点的节点,记数量为m,相互之间的组合数量即为C(m,2),即m*(m-1)/2
T = int(input())
while T > 0:
T -= 1
小蓝得到一棵以 1 为根的有根树,节点从 1 到 n 编号。定义节点的 枝数 为其直接子节点的个数。若两个节点的枝数相等,则称它们是一对 同枝节点。请你计算整棵树中同枝节点的对数。
树中节点数 n 不超过 100,测试数据组数 T 不超过 104,且所有测试数据的节点总数不超过 2imes105。
第一行输入一个整数 T,表示测试数据组数。对于每组测试数据: 第一行输入一个整数 n,表示树的节点数。 接下来 n−1 行,每行输入两个整数 u 和 v,表示树上的一条无向边。保证输入的边构成一棵以 1 为根的有根树,且不存在重边。节点编号均为 1 到 n 的整数。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册