Дерево (5 уровень)

Условие:
Дерево из N вершин можно представить следующим образом: сначала все вершины нумеруются числами от 1 до N. Затем выкидывается лист с наименьшим номером и выписывается номер его предка. Такая операция повторяется до тех пор, пока не
останется одна вершина. Врезультате получается последовательность из (n-1) числа. Требуется написать программу, которая по последовательности восстанавливает само дерево.

Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 2 секунды на тест.

Входные данные:
Во входном файле на первой строке (N-1) (2<=N<=7500) число.

Выходные данные:
Выходной файл должен содержать N строк. В i-й строке должен быть список вершин, с которыми соеденина i-я вершина в порядке возрастания.

Пример файлов входных и выходных данных:

Идея решения. Анализируя алгоритм получения данной последовательности по дереву, нетрудно понять, что количество раз, которое номер вершины встречается в последовательности равняется степени вершины, уменьшенной на 1, то есть количеству потомков этой вершины. Зная степени вершин, нетрудно составить список всех листьев, и выбрав из них наименьший(то есть имеющий наименьший номер), можно установить к какой вершине он был подвешен. Далее эмулируем удаление этого листа, то есть
уменьшеем степень его предка на 1, если предок становится листом, добавляем его в очередь рассматриваемых листов. Всего эту операцию необходимо и достаточно повторить (n-1) раз, чтобы для каждой вершины (кроме имеющей максимальный номер) определить, к какой вершине она была подвешена.

В нашем случае важно быстро находить лист с наименьшим номером (см. ограничение по времени), поэтому имеет смысл построить приоритетную очередь для листьев. Вывод ответа тоже оптимизирован, чтобы хватило времени.

{$A+,B-,D+,E-,F-,G+,I-,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y+}
{$M 16384,0,655360}

var
  list : array[1..7500] of integer; {Здесь храним исходную последовательность}
  m : array[1..7500] of integer; {Степени вершин, уменьшенные на 1}
  tree : array[1..7500] of integer; {Номера предков для всех вершин}
  heap : array[0..7500] of integer; {Приоритетная очередь для листьев}
  n, i, j : integer;
  v : integer;
  written : boolean;

procedure add(x : integer); {Процедура добавления элемента в очередь}
var
  i, d : integer;
begin
  inc(heap[0]);
  i := heap[0];
  d := i div 2;
  while (d > 0) and (heap[d] > x) do begin
    heap[i] := heap[d];
    i := d;
    d := i div 2;
  end;
  heap[i] := x;
end;

function min(i, j : integer) : integer; {Функция, возвращающая номер минимального элемента из i-го и j-го, j>i!}
begin
  if (j > heap[0]) or (heap[i] < heap[j]) then min := i else min := j;
end;

function getfirst : integer; {Функция, возвращающая первый элемент очереди, и удалающая его из очереди}
var
  i, d : integer;
  x : integer;
begin
  getfirst := heap[1];
  x := heap[heap[0]];
  dec(heap[0]);
  i := 1;
  d := min(2, 3);
  while (d <= heap[0]) and (heap[d] < x) do begin
    heap[i] := heap[d];
    i := d;
    d := min(i*2, i*2+1);
  end;
  heap[i] := x;
end;

begin
  assign(input, 'input.txt');
  reset(input);
  while not seekeof do begin
    inc(n);
    read(list[n]);
    inc(m[list[n]]);
  end;
  inc(n);
  close(input);
  for i := 1 to n do if m[i] = 0 then add(i);
  for i := 1 to (n-1) do begin
    tree[getfirst] := list[i]; {Записать номер предка}
    dec(m[list[i]]); {Уменьшить степень предка}
    if m[list[i]] = 0 then add(list[i]); {Если получили лист, добавить его в очередь}
  end;
  for i := 1 to (n-1) do inc(m[list[i]]); {Опять считаем степени вершин, это нам понадобится для оптимизации вывода ответа}
  assign(output, 'output.txt');
  rewrite(output);
  for i := 1 to n do begin
    v := tree[i];
    if (v > 0) then written := false else written := true;
    j := 0;
    while m[i] > 0 do begin
      inc(j);
      if tree[j] = i then begin
      if (v < j) and (not written) then begin
        write(v, ' ');
        written := true;
      end;
      write(j, ' ');
      dec(m[i]);
    end;
  end;
  if not written then write(v);
  writeln;
  end;
close(output);
end.

Автора задачи вряд-ли удастся установить. Если нужны какие-либо комментарии - пишите.