CF718D Andrew and Chemistry

在化学课上，Andrew 学到了饱和烃（烷烃）能够发生自由基氯化反应。Andrew 是个非常好奇的男孩，他想知道对于给定的烷烃，反应可能产生多少种不同的产物。他已经解决了小分子的情况，但对于较大的分子，他遇到了一些困难，并请求你帮忙。 形式化地说，给定一棵有 $n$ 个顶点的树，且每个顶点的度数不超过 $4$。你需要计算，通过向这棵树中加入一个新顶点和一条新边（新图依然是一棵树，且所有顶点度数仍不超过 $4$）可以获得多少种本质不同的、非同构的树。 当存在一个双射 $f(v)$，使得顶点 $u$ 和 $v$ 之间有边，当且仅当顶点 $f(u)$ 和 $f(v)$ 之间有边时，称两棵树是同构的。

第一行包含一个整数 $n$（$1 \leq n \leq 100000$）——树的顶点数。 接下来 $n-1$ 行，每行包含两个整数 $u_{i}$ 和 $v_{i}$（$1 \leq u_{i}, v_{i} \leq n$）——被一条边连接的两个顶点的编号。保证给定的图是一棵树，且每个顶点的度数不超过 $4$。

输出一个整数，表示问题的答案。

在第一个样例中，可以把新顶点添加到任意一个已有顶点上，但将新顶点添加到顶点 $1$、$3$ 和 $4$ 得到的树是同构的，因此答案是 $2$。 在第二个样例中，不能把新顶点添加到第一个顶点上，因为它的度数已经到 $4$。而将新顶点添加到顶点 $2$、$3$、$4$ 和 $5$ 得到的树都是同构的，因此答案是 $1$。 由 ChatGPT 5 翻译