9455 - 树哈希
时间限制 : 2 秒
内存限制 : 512 MB
这是一道模板题。
给定一棵以点 1 为根的树，你需要输出这棵树中最多能选出多少个互不同构的子树。
两棵有根树 T_1、 T_2 同构当且仅当他们的大小相等，且存在一个顶点排列 \sigma 使得在 T_1 中 i 是 j 的祖先当且仅当在 T_2 中 \sigma(i) 是 \sigma(j) 的祖先。
输入
第一行一个正整数 n，表示树的点数。
接下来 n-1 行给出树边。每行两个正整数 a,b，表示树上有一条连接点 a 和点 b 的边。
输出
一行一个正整数，表示最多能选出的互不同构的子树个数。
样例
输入
10 1 2 1 3 2 4 2 5 3 6 3 7 3 8 8 9 8 10
输出
4
提示
一种最优的选法是选择 1 号点、 2 号点、 3 号点、 4 号点的子树。
对于所有数据， 1 \le n \le 5 \times 10^5。
来源
UOJ