📄 problem 1097.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0047)http://acm.zju.edu.cn/show_problem.php?pid=1097 -->
<HTML><HEAD><TITLE>Problem 1097</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2900.2769" name=GENERATOR></HEAD>
<BODY>
<CENTER><IMG src="Problem 1097.files/logo.gif" align=center></IMG></CENTER>
<HR>
<CENTER><FONT color=blue size=+2>Code the Tree</FONT></CENTER>
<HR>
<CENTER><FONT color=green>Time limit:</FONT> 1 Seconds <FONT
color=green>Memory limit: </FONT>32768K </FONT><BR><FONT
color=green>Total Submit:</FONT> 764 <FONT color=green>Accepted
Submit:</FONT> 208 </CENTER>
<HR>
<P>A tree (i.e. a connected graph without cycles) with vertices numbered by the
integers <I>1, 2, ..., n</I> 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 <I>n</I>). The
written down sequence of <I>n-1</I> numbers is called the Prufer code of the
tree. <BR>Your task is, given a tree, to compute its Prufer code. The tree is
denoted by a word of the language specified by the following grammar: <PRE>T ::= "(" N S ")"
S ::= " " T S
| empty
N ::= number
</PRE>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
input.
<P>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".
<P><B>Input Specification</B>
<P>The input contains several test cases. Each test case specifies a tree as
described above on one line of the input file. Input is terminated by EOF. You
may assume that <I>1<=n<=50</I>.
<P><B>Output Specification</B>
<P>For each test case generate a single line containing the Prufer code of the
specified tree. Separate numbers by a single space. Do not print any spaces at
the end of the line.
<P>
<TABLE width="100%">
<TBODY>
<TR>
<TD vAlign=top>
<P><B>Sample Input</B>
<P><PRE>(2 (6 (7)) (3) (5 (1) (4)) (8))
(1 (2 (3)))
(6 (1 (4)) (2 (3) (5)))
</PRE>
<P><B>Sample Output</B>
<P><PRE>5 2 5 2 6 2 8
2 3
2 1 6 2 6
</PRE></TD>
<TD vAlign=top><IMG src="Problem 1097.files/showimg.gif">
</TD></TR></TBODY></TABLE>
<HR>
<FONT color=green size=+1>Problem Source: </FONT><I>University of Ulm Local
Contest 2001</I>
<HR>
<CENTER><A href="http://acm.zju.edu.cn/submit.php?pid=1097">Submit</A>
<A href="http://acm.zju.edu.cn/list_problem.php?vol=1">Back</A>
<A
href="http://acm.zju.edu.cn/problem_status.php?pid=1097">Status</A> </CENTER>
<HR>
<CENTER><A href="http://acm.zju.edu.cn/"><FONT color=red>Zhejiang University
Online Judge</FONT></A> <A href="http://acm.zju.edu.cn/"><FONT
color=red>V1.0</FONT></A><BR></CENTER></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -