首页 > ACM题库 > HDU-杭电 > hdu 2220 Encode the tree待解决[解题报告]C++
2014
01-04

hdu 2220 Encode the tree待解决[解题报告]C++

Encode the tree

问题描述 :

Given n labeled vertices, there are nn-2 different trees. The number is too large, but Wiskey want to use a way to encode the tree that make a unique sequence associated with the labeled tree.

Follow this way:
1.Select the vertex u which degree is 1 and the labeled number is the minimum. Example, u = 4.
2.Select the neighbor v of u, exists the edge which u to v. Example, v = 1.
3.Delete the edge from the tree. Example, the edge of 1-4 will be deleting.
4.Repeat the first step, until only two vertices left.
5.We will get the sequence {u1, u2… un-2} and {v1, v2… vn-2}.
Now, give you the v sequence, tell me the u sequence.

输入:

First line will contain one integer mean how many cases will follow by.
N represents the number of vertices, and the label start from 1. (3 <= N <= 100).
The next N-2 numbers mean the v sequence.

输出:

First line will contain one integer mean how many cases will follow by.
N represents the number of vertices, and the label start from 1. (3 <= N <= 100).
The next N-2 numbers mean the v sequence.

样例输入:

1
8
1 2 1 3 3 5

样例输出:

4 6 2 1 7 3


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)