{"problem":{"name":"E. Nikita and game","description":{"content":"Nikita plays a new computer game. There are _m_ levels in this game. In the beginning of each level a new class appears in the game; this class is a child-class of the class _y__i_ (and _y__i_ is call","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF842E"},"statements":[{"statement_type":"Markdown","content":"Nikita plays a new computer game. There are _m_ levels in this game. In the beginning of each level a new class appears in the game; this class is a child-class of the class _y__i_ (and _y__i_ is called parent-class for this new class). Thus, the classes form a tree. Initially there is only one class with index 1.\n\nChanging the class to its neighbour (child-class or parent-class) in the tree costs 1 coin. You can not change the class back. The cost of changing the class _a_ to the class _b_ is equal to the total cost of class changes on the path from _a_ to _b_ in the class tree.\n\nSuppose that at _i_ -th level the maximum cost of changing one class to another is _x_. For each level output the number of classes such that for each of these classes there exists some other class _y_, and the distance from this class to _y_ is exactly _x_.\n\n## Input\n\nFirst line contains one integer number _m_ — number of queries (1 ≤ _m_ ≤ 3·105).\n\nNext _m_ lines contain description of queries. _i_ -th line (1 ≤ _i_ ≤ _m_) describes the _i_ -th level and contains an integer _y__i_ — the index of the parent-class of class with index _i_ + 1 (1 ≤ _y__i_ ≤ _i_).\n\n## Output\n\nSuppose that at _i_ -th level the maximum cost of changing one class to another is _x_. For each level output the number of classes such that for each of these classes there exists some other class _y_, and the distance from this class to _y_ is exactly _x_.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Nikita 正在玩一款新电脑游戏。游戏中共有 $m$ 个关卡。在每个关卡开始时，游戏中会出现一个新的职业；这个新职业是职业 $y_i$ 的子职业（而 $y_i$ 被称为该新职业的父职业）。因此，这些职业构成了一棵树。初始时只有一个编号为 $1$ 的职业。\n\n在树中将职业切换到其邻居（子职业或父职业）需要花费 $1$ 枚金币。你不能切换回之前的职业。将职业 $a$ 切换到职业 $b$ 的代价等于在职业树中从 $a$ 到 $b$ 的路径上所有切换操作的总代价。\n\n假设在第 $i$ 个关卡时，任意两个职业之间切换的最大代价为 $x$。对于每个关卡，请输出满足以下条件的职业数量：对于每个这样的职业，都存在另一个职业 $y$，使得该职业到 $y$ 的距离恰好为 $x$。\n\n## Input\n\n第一行包含一个整数 $m$ —— 查询的数量（$1 ≤ m ≤ 3·10^5$）。接下来 $m$ 行描述每个查询。第 $i$ 行（$1 ≤ i ≤ m$）描述第 $i$ 个关卡，包含一个整数 $y_i$ —— 编号为 $i+1$ 的职业的父职业的编号（$1 ≤ y_i ≤ i$）。\n\n## Output\n\n假设在第 $i$ 个关卡时，任意两个职业之间切换的最大代价为 $x$。对于每个关卡，请输出满足以下条件的职业数量：对于每个这样的职业，都存在另一个职业 $y$，使得该职业到 $y$ 的距离恰好为 $x$。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ m \\in \\mathbb{Z}^+ $ be the number of levels.  \nLet $ T = (V, E) $ be a tree evolving over levels, where:  \n- $ V = \\{1, 2, \\dots, m+1\\} $ is the set of class indices.  \n- Initially, $ V = \\{1\\} $, and for each level $ i \\in \\{1, \\dots, m\\} $, a new node $ i+1 $ is added with parent $ y_i \\in \\{1, \\dots, i\\} $, so $ E = \\{ (y_i, i+1) \\mid i \\in \\{1, \\dots, m\\} \\} $.  \n\nLet $ d(u, v) $ denote the shortest path distance (number of edges) between nodes $ u $ and $ v $ in $ T $.  \n\nLet $ D_i $ be the diameter of the tree at level $ i $ (i.e., the maximum distance between any two nodes in the tree after $ i $ levels have been added).  \nLet $ C_i $ be the number of nodes $ u $ in the tree at level $ i $ such that there exists a node $ v \\ne u $ with $ d(u, v) = D_i $.\n\n**Constraints**  \n1. $ 1 \\le m \\le 3 \\cdot 10^5 $  \n2. For each $ i \\in \\{1, \\dots, m\\} $, $ 1 \\le y_i \\le i $\n\n**Objective**  \nFor each level $ i \\in \\{1, \\dots, m\\} $, output $ C_i $, the count of nodes that achieve the diameter $ D_i $ as an endpoint.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF842E","tags":["binary search","dfs and similar","divide and conquer","graphs","trees"],"sample_group":[["4\n1\n1\n2\n1","2\n2\n2\n3"],["4\n1\n1\n2\n3","2\n2\n2\n2"]],"created_at":"2026-03-03 11:00:39"}}