题解 - [POJ 2568] [ZOJ 1965] Decode the Tree

发表于 更新于 分类于 ， 本文字数： 468 阅读时长 ≈ 2 分钟

题目链接

原始题面

Description

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:

1
2
3
4
5
6
7
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"

Input

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\leqslant n\leqslant 50\)

Output

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

Sample Input

1
2
3
5 2 5 2 6 2 8
2 3
2 1 6 2 6

Sample Output

1
2
3
(8 (2 (3) (5 (1) (4)) (6 (7))))
(3 (2 (1)))
(6 (1 (4)) (2 (3) (5)))

Source

Ulm Local 2001

题意简述

给出一个无根树对应的 Prufer 序列，随意令一个结点为根，按先序遍历输出该树

解题思路

板子题，没啥好说的

代码参考

Show code

POJ_2568view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <sstream>
#include <string>
using namespace std;
const int N = 505;
struct Edge {
  int to, next;
} e[N];
int head[N], cnt_edge;
void addEdge(int x, int y) {
  e[++cnt_edge] = {y, head[x]};
  head[x] = cnt_edge;
}
int prufer[N], cnt[N];
bool vis[N];
void print(int fa, int now) {
  printf("(%d", now);
  for (int i = head[now], to; i; i = e[i].next) {
    to = e[i].to;
    if (to == fa) continue;
    putchar(' ');
    print(now, to);
  }
  putchar(')');
}
int main() {
  string line;
  while (getline(cin, line)) {
    stringstream ss;
    memset(prufer, 0, sizeof(prufer));
    memset(vis, 0, sizeof(vis));
    memset(head, 0, sizeof(head));
    memset(cnt, 0, sizeof(cnt));
    cnt_edge = 0;
    int n = 0, _;
    ss << line;
    while (ss >> _) ++cnt[prufer[++n] = _];
    ++n;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 1; i <= n; ++i)
      if (!cnt[i]) pq.push(i);
    for (int i = 1; i < n; ++i) {
      int now = pq.top();
      pq.pop();
      addEdge(prufer[i], now);
      addEdge(now, prufer[i]);
      if (!(--cnt[prufer[i]])) pq.push(prufer[i]);
    }
    if (n == 1) {
      puts("(1)");
      continue;
    }
    print(0, prufer[n - 1]);
    puts("");
  }
}