小 A 最近沉迷 「我的世界」这款游戏,他喜欢在里面搭建各种建筑群。这一次,他要建立一个梦幻般的庄园,庄园总共有 n 个建筑和 n-1 条路,我们可以把建筑看成点,路看成边。形式化地说,这个庄园中的建筑和路形成了一棵 n 个结点的无根树,结点编号为 1,2,.......,n。
现在,小 A 想要对这些路进行改造,他想要在其中一些路上铺上花哨的多彩大理石。小 A 非常喜欢这种大理石路面,所以他想要铺上大理石的路越多越好。同时,小 A 又是艺术的,他不希望出现有两条铺了大理石的路连接同一个建筑,这样会变得不美观。
简单来说,小 A 想要在庄园这棵无根树中,选择最多的边,使得这些边没有公共顶点。
现在,小 A 想要知道能够铺上大理石的最多的路的数量,并且在满足数量最多的前提下,这样的铺法有多少种。
