D. Peculiar apple-tree

Codeforces

IDCF931D

Time1000ms

Memory256MB

Difficulty—

dfs and similargraphstrees

English · Original

Chinese · Translation

Formal · Original

In Arcady's garden there grows a peculiar apple-tree that fruits one time per year. Its peculiarity can be explained in following way: there are _n_ inflorescences, numbered from 1 to _n_. Inflorescence number 1 is situated near base of tree and any other inflorescence with number _i_ (_i_ > 1) is situated at the top of branch, which bottom is _p__i_\-th inflorescence and _p__i_ < _i_. Once tree starts fruiting, there appears exactly one apple in each inflorescence. The same moment as apples appear, they start to roll down along branches to the very base of tree. Each second all apples, except ones in first inflorescence simultaneously roll down one branch closer to tree base, e.g. apple in _a_\-th inflorescence gets to _p__a_\-th inflorescence. Apples that end up in first inflorescence are gathered by Arcady in exactly the same moment. Second peculiarity of this tree is that once two apples are in same inflorescence they **annihilate**. This happens with each pair of apples, e.g. if there are 5 apples in same inflorescence in same time, only one will not be annihilated and if there are 8 apples, all apples will be annihilated. Thus, there can be no more than one apple in each inflorescence in each moment of time. Help Arcady with counting number of apples he will be able to collect from first inflorescence during one harvest. ## Input First line of input contains single integer number _n_ (2 ≤ _n_ ≤ 100 000) — number of inflorescences. Second line of input contains sequence of _n_ - 1 integer numbers _p_2, _p_3, ..., _p__n_ (1 ≤ _p__i_ < _i_), where _p__i_ is number of inflorescence into which the apple from _i_\-th inflorescence rolls down. ## Output Single line of output should contain one integer number: amount of apples that Arcady will be able to collect from first inflorescence during one harvest. [samples] ## Note In first example Arcady will be able to collect only one apple, initially situated in 1st inflorescence. In next second apples from 2nd and 3rd inflorescences will roll down and annihilate, and Arcady won't be able to collect them. In the second example Arcady will be able to collect 3 apples. First one is one initially situated in first inflorescence. In a second apple from 2nd inflorescence will roll down to 1st (Arcady will collect it) and apples from 3rd, 4th, 5th inflorescences will roll down to 2nd. Two of them will annihilate and one not annihilated will roll down from 2\-nd inflorescence to 1st one in the next second and Arcady will collect it.

在 Arcady 的花园里生长着一棵奇特的苹果树，每年只结果一次。其特殊性可如下解释：树上有 #cf_span[n] 个花序，编号从 #cf_span[1] 到 #cf_span[n]。编号为 #cf_span[1] 的花序位于树干基部，而其他任意编号为 #cf_span[i]（#cf_span[i > 1]）的花序位于一根枝条的顶端，该枝条的底部是第 #cf_span[pi] 个花序，且 #cf_span[pi < i]。当树木开始结果时，每个花序中恰好出现一个苹果。就在苹果出现的同时，它们开始沿着枝条向树干基部滚动。每一秒，除了位于第一个花序中的苹果外，所有苹果同时向下滚动一个枝条，例如，位于第 #cf_span[a] 个花序的苹果会移动到第 #cf_span[pa] 个花序。到达第一个花序的苹果会被 Arcady 立即收集。这棵树的另一个特殊之处在于，一旦两个苹果处于同一花序中，它们就会 *湮灭*。这一过程对每一对苹果都适用，例如，如果某一时刻同一花序中有 #cf_span[5] 个苹果，则仅有一个不会被湮灭；如果共有 #cf_span[8] 个苹果，则所有苹果都会被湮灭。因此，在任意时刻，每个花序中最多只能有一个苹果。请帮助 Arcady 计算他在一次收获中能从第一个花序中收集到的苹果数量。输入的第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100 000]）——花序的数量。输入的第二行包含一个包含 #cf_span[n - 1] 个整数的序列 #cf_span[p2, p3, ..., pn]（#cf_span[1 ≤ pi < i]），其中 #cf_span[pi] 表示从第 #cf_span[i] 个花序滚下的苹果将到达的花序编号。输出应为一行，包含一个整数：Arcady 在一次收获中能从第一个花序中收集到的苹果数量。在第一个示例中，Arcady 只能收集最初位于第 #cf_span[1] 个花序中的一个苹果。下一秒，来自第 #cf_span[2] 和 #cf_span[3] 个花序的苹果会滚下并相互湮灭，Arcady 无法收集它们。在第二个示例中，Arcady 将能收集 3 个苹果。第一个是最初位于第一个花序中的苹果。一秒后，来自第 #cf_span[2] 个花序的苹果滚到第 #cf_span[1] 个花序（Arcady 收集它），而来自第 #cf_span[3]、#cf_span[4]、#cf_span[5] 个花序的苹果滚到第 #cf_span[2] 个花序。其中两个相互湮灭，剩下一个未被湮灭的苹果在下一秒从第 #cf_span[2] 个花序滚到第 #cf_span[1] 个花序，Arcady 将收集它。 ## Input 输入的第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100 000]）——花序的数量。第二行包含一个包含 #cf_span[n - 1] 个整数的序列 #cf_span[p2, p3, ..., pn]（#cf_span[1 ≤ pi < i]），其中 #cf_span[pi] 表示从第 #cf_span[i] 个花序滚下的苹果将到达的花序编号。 ## Output 输出应为一行，包含一个整数：Arcady 在一次收获中能从第一个花序中收集到的苹果数量。 [samples] ## Note 在第一个示例中，Arcady 只能收集最初位于第 #cf_span[1] 个花序中的一个苹果。下一秒，来自第 #cf_span[2] 和 #cf_span[3] 个花序的苹果会滚下并相互湮灭，Arcady 无法收集它们。在第二个示例中，Arcady 将能收集 3 个苹果。第一个是最初位于第一个花序中的苹果。一秒后，来自第 #cf_span[2] 个花序的苹果滚到第 #cf_span[1] 个花序（Arcady 收集它），而来自第 #cf_span[3]、#cf_span[4]、#cf_span[5] 个花序的苹果滚到第 #cf_span[2] 个花序。其中两个相互湮灭，剩下一个未被湮灭的苹果在下一秒从第 #cf_span[2] 个花序滚到第 #cf_span[1] 个花序，Arcady 将收集它。

Let $ n $ be the number of inflorescences, numbered $ 1 $ to $ n $, with inflorescence $ 1 $ as the root. For each $ i \in \{2, 3, \dots, n\} $, let $ p_i \in \{1, 2, \dots, i-1\} $ denote the parent of inflorescence $ i $, defining a tree structure rooted at $ 1 $. Each inflorescence initially contains exactly one apple. At each second, every apple not at the root moves to its parent. When multiple apples arrive at the same inflorescence at the same time, they annihilate in pairs: an even number of apples results in zero remaining; an odd number results in one remaining. Let $ d_i $ denote the depth of inflorescence $ i $, i.e., the number of edges from the root (inflorescence $ 1 $) to $ i $. Then, the apple starting at inflorescence $ i $ reaches the root at time $ d_i $. Let $ c_t $ be the number of apples that reach the root at time $ t $. Since apples annihilate in pairs before reaching the root, the number of apples arriving at the root at time $ t $ is equal to the number of inflorescences at depth $ t $, modulo 2. Thus, define: - $ f(t) = \left| \{ i \in \{1, 2, \dots, n\} \mid d_i = t \} \right| $, the number of inflorescences at depth $ t $. - The number of apples collected at time $ t $ is $ f(t) \bmod 2 $. The total number of apples collected is: $$ \sum_{t=0}^{\max(d_i)} (f(t) \bmod 2) $$ Note: $ f(0) = 1 $ (only root at depth 0), and for $ t \geq 1 $, $ f(t) $ is the count of nodes at depth $ t $. **Output:** $ \sum_{t=0}^{D} (f(t) \bmod 2) $, where $ D = \max_i d_i $.

Samples

Input #1

3
1 1

Output #1

Input #2

5
1 2 2 2

Output #2

Input #3

18
1 1 1 4 4 3 2 2 2 10 8 9 9 9 10 10 4

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. Peculiar apple-tree",
    "description": {
      "content": "In Arcady's garden there grows a peculiar apple-tree that fruits one time per year. Its peculiarity can be explained in following way: there are _n_ inflorescences, numbered from 1 to _n_. Inflorescen",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF931D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In Arcady's garden there grows a peculiar apple-tree that fruits one time per year. Its peculiarity can be explained in following way: there are _n_ inflorescences, numbered from 1 to _n_. Inflorescen...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在 Arcady 的花园里生长着一棵奇特的苹果树，每年只结果一次。其特殊性可如下解释：树上有 #cf_span[n] 个花序，编号从 #cf_span[1] 到 #cf_span[n]。编号为 #cf_span[1] 的花序位于树干基部，而其他任意编号为 #cf_span[i]（#cf_span[i > 1]）的花序位于一根枝条的顶端，该枝条的底部是第 #cf_span[pi] 个花序，且 #cf...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n $ be the number of inflorescences, numbered $ 1 $ to $ n $, with inflorescence $ 1 $ as the root.\n\nFor each $ i \\in \\{2, 3, \\dots, n\\} $, let $ p_i \\in \\{1, 2, \\dots, i-1\\} $ denote the parent...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments