#P18427. The Doubling Game 2
The Doubling Game 2
The Doubling Game 2
The Doubling Game 更像一道谜题。棋盘有 个格子,编号为 ,用 条线段连接,任意两个格子之间都能沿线段到达。因此,棋盘构成一棵树。初始时,每个顶点恰有一枚棋子。
唯一允许的操作是:选择通过一条线段直接相连、且棋子数相同的两个格子;两处的棋子数必须都是正数。把其中一个格子的全部棋子移动到另一个格子。
请计算执行任意次操作(也可以一次都不执行)后,棋盘可能出现多少种不同的棋子分布。如果两个分布至少有一个格子的棋子数不同,就认为它们不同。答案可能很大,只需输出它除以 的余数。
输入格式
第一行包含一个整数 (),表示格子数。
接下来 行,每行包含两个整数 (,),表示这两个格子之间有一条线段。输入所描述的图是一棵树。
输出格式
输出一行一个整数,即不同棋子分布的数量对 取模的结果。
原样例
输入:
5
1 2
1 3
1 4
4 5
输出:
21
样例说明
样例棋盘及其顶点编号如下(原题配图):

下面列出部分可以达到的分布,圆内的黑点表示棋子(原题配图,并非全部 21 种):
