当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

2568:Decode the Tree

Special Judge 特殊评判
题目描述
A tree (i.e. a connected graph without cycles) with vertices numbered by the integers 1, 2, ..., n is given. The "Prufer" code of such a tree is built as follows: the leaf (a vertex that is incident to only one edge) with the minimal number is taken. This leaf, together with its incident edge is removed from the graph, while the number of the vertex that was adjacent to the leaf is written down. In the obtained graph, this procedure is repeated, until there is only one vertex left (which, by the way, always has number n). The written down sequence of n-1 numbers is called the Prufer code of the tree.
Your task is, to reconstruct a tree, given its Prufer code. The tree should be denoted by a word of the language specified by the following grammar:

T ::= "(" N S ")"
S ::= " " T S
| empty
N ::= number

That is, trees have parentheses around them, and a number denoting the identifier of the root vertex, followed by arbitrarily many (maybe none) subtrees separated by a single space character. As an example, take a look at the tree in the figure below which is denoted in the first line of the sample output. To generate further sample input, you may use your solution to Problem 2567.
Note that, according to the definition given above, the root of a tree may be a leaf as well. It is only for the ease of denotation that we designate some vertex to be the root. Usually, what we are dealing here with is called an "unrooted tree".
输入解释
The input contains several test cases. Each test case specifies the Prufer code of a tree on one line. You will find n-1 numbers separated by a single space. Input is terminated by EOF. You may assume that 1<=n<=50.
输出解释
For each test case generate a single line containing the corresponding tree, denoted as described above. Note that, in general, there are many ways to denote such a tree: choose your favourite one.
输入样例
5 2 5 2 6 2 8
2 3
2 1 6 2 6
输出样例
(8 (2 (3) (5 (1) (4)) (6 (7))))
(3 (2 (1)))
(6 (1 (4)) (2 (3) (5)))

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 Ulm Local 2001

源链接: POJ-2568

最后修改于 2020-10-29T06:36:01+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 65536