{"problem":{"name":"A. Hashing Trees","description":{"content":"Sasha is taking part in a programming competition. In one of the problems she should check if some rooted trees are isomorphic or not. She has never seen this problem before, but, being an experienced","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF901A"},"statements":[{"statement_type":"Markdown","content":"Sasha is taking part in a programming competition. In one of the problems she should check if some rooted trees are isomorphic or not. She has never seen this problem before, but, being an experienced participant, she guessed that she should match trees to some sequences and then compare these sequences instead of trees. Sasha wants to match each tree with a sequence _a_0, _a_1, ..., _a__h_, where _h_ is the height of the tree, and _a__i_ equals to the number of vertices that are at distance of _i_ edges from root.\n\nUnfortunately, this time Sasha's intuition was wrong, and there could be several trees matching the same sequence. To show it, you need to write a program that, given the sequence _a__i_, builds two non-isomorphic rooted trees that match that sequence, or determines that there is only one such tree.\n\nTwo rooted trees are isomorphic, if you can reenumerate the vertices of the first one in such a way, that the index of the root becomes equal the index of the root of the second tree, and these two trees become equal.\n\nThe height of a rooted tree is the maximum number of edges on a path from the root to any other vertex.\n\n## Input\n\nThe first line contains a single integer _h_ (2 ≤ _h_ ≤ 105) — the height of the tree.\n\nThe second line contains _h_ + 1 integers — the sequence _a_0, _a_1, ..., _a__h_ (1 ≤ _a__i_ ≤ 2·105). The sum of all _a__i_ does not exceed 2·105. It is guaranteed that there is at least one tree matching this sequence.\n\n## Output\n\nIf there is only one tree matching this sequence, print \"_perfect_\".\n\nOtherwise print \"_ambiguous_\" in the first line. In the second and in the third line print descriptions of two trees in the following format: in one line print integers, the _k_\\-th of them should be the parent of vertex _k_ or be equal to zero, if the _k_\\-th vertex is the root.\n\nThese treese should be non-isomorphic and should match the given sequence.\n\n[samples]\n\n## Note\n\nThe only tree in the first example and the two printed trees from the second example are shown on the picture:\n\n![image](https://espresso.codeforces.com/391ac13640fa692361683e9c23619eb4e8bce1c5.png)","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"Sasha 正参加一场编程竞赛。在其中一个题目中，她需要判断一些有根树是否同构。她以前从未见过这个问题，但作为有经验的选手，她推测应该将树映射到某些序列，然后比较这些序列而不是直接比较树。Sasha 希望将每棵树映射为一个序列 #cf_span[a0, a1, ..., ah]，其中 #cf_span[h] 是树的高度，而 #cf_span[ai] 表示距离根节点恰好有 #cf_span[i] 条边的顶点数量。\\n\\n然而，这次 Sasha 的直觉是错误的，可能存在多个树对应同一个序列。为了说明这一点，你需要编写一个程序：给定序列 #cf_span[ai]，构造两个非同构的有根树，使其匹配该序列，或者判断仅存在唯一一棵这样的树。\\n\\n两个有根树同构，当且仅当你可以重新标记第一棵树的顶点，使得根的编号与第二棵树的根编号相同，并且两棵树完全一致。\\n\\n有根树的高度定义为从根到任意其他顶点的路径中边数的最大值。\\n\\n第一行包含一个整数 #cf_span[h]（#cf_span[2 ≤ h ≤ 105]）——树的高度。\\n\\n第二行包含 #cf_span[h + 1] 个整数——序列 #cf_span[a0, a1, ..., ah]（#cf_span[1 ≤ ai ≤ 2·105]）。所有 #cf_span[ai] 的和不超过 #cf_span[2·105]。保证至少存在一棵树匹配该序列。\\n\\n如果仅存在一棵匹配该序列的树，请输出 \\\"_perfect_\\\"。\\n\\n否则，第一行输出 \\\"_ambiguous_\\\"，并在第二行和第三行分别输出两棵树的描述，格式如下：每行输出 #cf_span[sum_{i=0}^h a_i] 个整数，第 #cf_span[k] 个整数表示顶点 #cf_span[k] 的父节点，若该顶点是根，则为 0。\\n\\n这两棵树必须是非同构的，且均匹配给定的序列。\"}},{\"iden\":\"input\",\"content\":\"第一行包含一个整数 #cf_span[h]（#cf_span[2 ≤ h ≤ 105]）——树的高度。第二行包含 #cf_span[h + 1] 个整数——序列 #cf_span[a0, a1, ..., ah]（#cf_span[1 ≤ ai ≤ 2·105]）。所有 #cf_span[ai] 的和不超过 #cf_span[2·105]。保证至少存在一棵树匹配该序列。\"},{\"iden\":\"output\",\"content\":\"如果仅存在一棵匹配该序列的树，请输出 \\\"_perfect_\\\"。否则，第一行输出 \\\"_ambiguous_\\\"，并在第二行和第三行分别输出两棵树的描述，格式如下：每行输出 #cf_span[sum_{i=0}^h a_i] 个整数，第 #cf_span[k] 个整数表示顶点 #cf_span[k] 的父节点，若该顶点是根，则为 0。这两棵树必须是非同构的，且均匹配给定的序列。\"},{\"iden\":\"examples\",\"content\":\"输入21 1 1输出perfect输入21 2 2输出ambiguous0 1 1 3 30 1 1 3 2\"},{\"iden\":\"note\",\"content\":\"第一个例子中的唯一一棵树，以及第二个例子中输出的两棵树如图所示：\"}]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ h \\in \\mathbb{Z} $ be the height of the tree.  \nLet $ A = (a_0, a_1, \\dots, a_h) $ be a sequence of positive integers, where $ a_i $ denotes the number of vertices at distance $ i $ from the root.  \n\n**Constraints**  \n1. $ 2 \\le h \\le 10^5 $  \n2. $ 1 \\le a_i \\le 2 \\cdot 10^5 $ for all $ i \\in \\{0, 1, \\dots, h\\} $  \n3. $ \\sum_{i=0}^h a_i \\le 2 \\cdot 10^5 $  \n4. There exists at least one rooted tree matching $ A $.  \n\n**Objective**  \nDetermine whether there exists exactly one rooted tree (up to isomorphism) matching $ A $, or at least two non-isomorphic rooted trees matching $ A $.  \n\n- If exactly one such tree exists, output `\"perfect\"`.  \n- Otherwise, output `\"ambiguous\"`, followed by two distinct parent arrays $ P_1, P_2 \\in \\{0, 1, \\dots, N\\}^N $ (where $ N = \\sum_{i=0}^h a_i $), representing two non-isomorphic rooted trees such that:  \n  - The root has parent 0.  \n  - For each $ i \\in \\{1, \\dots, h\\} $, exactly $ a_i $ vertices have parent at distance $ i-1 $ from the root.  \n  - The trees are not isomorphic (i.e., no bijection preserves parent-child structure and root).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF901A","tags":["constructive algorithms","trees"],"sample_group":[["2\n1 1 1","perfect"],["2\n1 2 2","ambiguous\n0 1 1 3 3\n0 1 1 3 2"]],"created_at":"2026-03-03 11:00:39"}}