Tree Conundrum

时间限制:10s      空间限制:128MB

题目描述

给定一棵N个节点的无根树,现要求有多少种合法的分块方案。
 所谓合法的分块方案,就是将树分为若干个连通块,满足每个连通块内点数相同。


输入格式

第一行一个正整数N,表示这棵树的结点总数,接下来N-1行,每行两个数字X,Y表示编号为X的结点与编号为Y的结点相连。结点编号的范围为1-N且编号两两不同。
注意该题程序以及输入输出文件名。


输出格式

 
一行一个整数Ans,表示所求的方案数。


样例输入

6
1 2
2 3
2 4
4 5
5 6

样例输出

3
【数据规模和约定】
10%的数据满足N<=16,
30%的数据满足N<=100,
50%的数据满足N<=50000,
100%的数据满足N<=1000000。

提示

没有写明提示


题目来源

没有写明来源