D. Andrew and Chemistry

Codeforces

IDCF718D

Time2000ms

Memory256MB

Difficulty—

dphashingtrees

English · Original

Chinese · Translation

Formal · Original

_During the chemistry lesson Andrew learned that the saturated hydrocarbons (alkanes) enter into radical chlorination reaction. Andrew is a very curious boy, so he wondered how many different products of the reaction may be forms for a given alkane. He managed to solve the task for small molecules, but for large ones he faced some difficulties and asks you to help._ Formally, you are given a tree consisting of _n_ vertices, such that the degree of each vertex doesn't exceed 4. You have to count the number of distinct non-isomorphic trees that can be obtained by adding to this tree one new vertex and one new edge, such that the graph is still the tree and the degree of each vertex doesn't exceed 4. Two trees are isomorphic if there exists a bijection _f_(_v_) such that vertices _u_ and _v_ are connected by an edge if and only if vertices _f_(_v_) and _f_(_u_) are connected by an edge. ## Input The first line of the input contains an integer _n_ (1 ≤ _n_ ≤ 100 000) — the number of vertices in the tree. Then follow _n_ - 1 lines with edges descriptions. Each edge is given by two integers _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_) — indices of vertices connected by an edge. It's guaranteed that the given graph is a tree and the degree of each vertex doesn't exceed 4. ## Output Print one integer — the answer to the question. [samples] ## Note In the first sample, one can add new vertex to any existing vertex, but the trees we obtain by adding a new vertex to vertices 1, 3 and 4 are isomorphic, thus the answer is 2. In the second sample, one can't add new vertex to the first vertex, as its degree is already equal to four. Trees, obtained by adding a new vertex to vertices 2, 3, 4 and 5 are isomorphic, thus the answer is 1.

在化学课上，Andrew 学习到饱和烃（烷烃）会发生自由基氯代反应。Andrew 是一个非常好奇的男孩，因此他想知道对于给定的烷烃，反应可能生成多少种不同的产物。他成功解决了小分子的问题，但对于大分子他遇到了一些困难，于是向你寻求帮助。形式化地，你被给定一棵由 #cf_span[n] 个顶点组成的树，其中每个顶点的度数不超过 #cf_span[4]。你需要计算通过向这棵树添加一个新顶点和一条新边，使得所得图仍为树且每个顶点的度数仍不超过 #cf_span[4] 的情况下，能获得多少种互不同构的树。两棵树同构，当且仅当存在一个双射 #cf_span[f(v)]，使得顶点 #cf_span[u] 和 #cf_span[v] 之间有边，当且仅当顶点 #cf_span[f(v)] 和 #cf_span[f(u)] 之间有边。输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 树中顶点的数量。接下来是 #cf_span[n - 1] 行，每行描述一条边。每条边由两个整数 #cf_span[ui] 和 #cf_span[vi] (#cf_span[1 ≤ ui, vi ≤ n]) 给出，表示由该边连接的两个顶点的编号。保证给定的图是一棵树，且每个顶点的度数不超过 #cf_span[4]。请输出一个整数 —— 该问题的答案。在第一个样例中，可以将新顶点添加到任意现有顶点上，但通过将新顶点添加到顶点 #cf_span[1]、#cf_span[3] 和 #cf_span[4] 所得到的树是同构的，因此答案是 #cf_span[2]。在第二个样例中，不能将新顶点添加到第一个顶点，因为它的度数已经等于四。通过将新顶点添加到顶点 #cf_span[2]、#cf_span[3]、#cf_span[4] 和 #cf_span[5] 所得到的树是同构的，因此答案是 #cf_span[1]。 ## Input 输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 树中顶点的数量。接下来是 #cf_span[n - 1] 行，每行描述一条边。每条边由两个整数 #cf_span[ui] 和 #cf_span[vi] (#cf_span[1 ≤ ui, vi ≤ n]) 给出，表示由该边连接的两个顶点的编号。保证给定的图是一棵树，且每个顶点的度数不超过 #cf_span[4]。 ## Output 请输出一个整数 —— 该问题的答案。 [samples] ## Note 在第一个样例中，可以将新顶点添加到任意现有顶点上，但通过将新顶点添加到顶点 #cf_span[1]、#cf_span[3] 和 #cf_span[4] 所得到的树是同构的，因此答案是 #cf_span[2]。在第二个样例中，不能将新顶点添加到第一个顶点，因为它的度数已经等于四。通过将新顶点添加到顶点 #cf_span[2]、#cf_span[3]、#cf_span[4] 和 #cf_span[5] 所得到的树是同构的，因此答案是 #cf_span[1]。

Let $ T = (V, E) $ be a tree with $ n $ vertices, where $ \deg(v) \leq 4 $ for all $ v \in V $. Let $ \mathcal{S} $ be the set of all trees obtained by adding one new vertex $ v_{n+1} $ and one new edge $ (v_{n+1}, u) $ for some $ u \in V $ such that $ \deg(u) < 4 $. Define an equivalence relation on $ \mathcal{S} $: two trees $ T_1, T_2 \in \mathcal{S} $ are equivalent (isomorphic) if there exists a graph isomorphism $ f: V(T_1) \to V(T_2) $ preserving adjacency. The goal is to compute the number of distinct isomorphism classes in $ \mathcal{S} $. Let $ D $ be the multiset of degrees of vertices in $ T $: $ D = \{ \deg(v) \mid v \in V \} $. Let $ C $ be the set of vertices $ u \in V $ with $ \deg(u) < 4 $. For each $ u \in C $, let $ T_u $ denote the tree obtained by attaching a new leaf to $ u $. Define an equivalence relation on $ C $: $ u \sim v $ if and only if $ T_u \cong T_v $. The answer is $ |C / \sim| $, the number of equivalence classes under $ \sim $. To compute $ \sim $, define the *type* of a vertex $ u $ as the isomorphism class of the rooted tree obtained by rooting $ T $ at $ u $, where the root has degree $ \deg(u) $, and all other vertices have degree at most 4. Then: $ u \sim v $ if and only if the rooted trees $ (T, u) $ and $ (T, v) $ are isomorphic as rooted trees. Thus, the number of distinct non-isomorphic trees obtainable is equal to the number of distinct isomorphism classes of rooted trees $ (T, u) $ for $ u \in C $. Let $ \mathcal{R} $ be the set of rooted tree isomorphism classes of $ (T, u) $ for $ u \in C $. Then the answer is $ |\mathcal{R}| $.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. Andrew and Chemistry",
    "description": {
      "content": "_During the chemistry lesson Andrew learned that the saturated hydrocarbons (alkanes) enter into radical chlorination reaction. Andrew is a very curious boy, so he wondered how many different products",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF718D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_During the chemistry lesson Andrew learned that the saturated hydrocarbons (alkanes) enter into radical chlorination reaction. Andrew is a very curious boy, so he wondered how many different products...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在化学课上，Andrew 学习到饱和烃（烷烃）会发生自由基氯代反应。Andrew 是一个非常好奇的男孩，因此他想知道对于给定的烷烃，反应可能生成多少种不同的产物。他成功解决了小分子的问题，但对于大分子他遇到了一些困难，于是向你寻求帮助。\n\n形式化地，你被给定一棵由 #cf_span[n] 个顶点组成的树，其中每个顶点的度数不超过 #cf_span[4]。你需要计算通过向这棵树添加一个新顶点和一条新...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ T = (V, E) $ be a tree with $ n $ vertices, where $ \\deg(v) \\leq 4 $ for all $ v \\in V $.\n\nLet $ \\mathcal{S} $ be the set of all trees obtained by adding one new vertex $ v_{n+1} $ and one new e...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments