восстановить дерево по коду прюфера

Чтобы восстановить помеченное дерево по коду Прюфера, используем стандартный алгоритм.

Идея

Для дерева на n вершинах код Прюфера имеет длину n-2 и содержит метки вершин (обычно 1..n).

1. Заводим массив степеней deg[1..n]:

• изначально deg[i]=1 для всех i
• затем для каждого числа x в коде увеличиваем deg[x]++

2. Все вершины со степенью 1 — это листья. Держим их в min-куче (чтобы всегда брать лист с минимальной меткой).

3. Проходим по коду слева направо:

• берём минимальный лист v
• добавляем ребро (v, x) где x — текущий элемент кода
• уменьшаем deg[v]--, deg[x]--
• если deg[x] стало 1, добавляем x в кучу

4. После обработки всего кода в куче останутся две вершины a и b. Добавляем ребро (a, b).

Сложность: O(n log n) из-за кучи.

---

Python (1..n)

python
import heapq

def prufer_to_tree(n, prufer):
    # prufer: list длины n-2, метки 1..n
    deg = [0] * (n + 1)
    for i in range(1, n + 1):
        deg[i] = 1
    for x in prufer:
        deg[x] += 1

    heap = []
    for i in range(1, n + 1):
        if deg[i] == 1:
            heapq.heappush(heap, i)

    edges = []
    for x in prufer:
        v = heapq.heappop(heap)
        edges.append((v, x))
        deg[v] -= 1
        deg[x] -= 1
        if deg[x] == 1:
            heapq.heappush(heap, x)

    a = heapq.heappop(heap)
    b = heapq.heappop(heap)
    edges.append((a, b))
    return edges

# пример использования:
# n = 5
# prufer = [4, 4, 4]  # длина 3 = n-2
# print(prufer_to_tree(n, prufer))

---

C++ (1..n)

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> prufer(n - 2);
    for (int i = 0; i < n - 2; i++) cin >> prufer[i];

    vector<int> deg(n + 1, 1);
    for (int x : prufer) deg[x]++;

    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 1) pq.push(i);

    vector<pair<int,int>> edges;
    edges.reserve(n - 1);

    for (int x : prufer) {
        int v = pq.top(); pq.pop();
        edges.push_back({v, x});
        deg[v]--;
        deg[x]--;
        if (deg[x] == 1) pq.push(x);
    }

    int a = pq.top(); pq.pop();
    int b = pq.top(); pq.pop();
    edges.push_back({a, b});

    for (auto [u, v] : edges) {
        cout << u << " " << v << "\n";
    }
    return 0;
}

---

Если пришлёшь конкретный код Прюфера (и n, если не очевидно), я прямо выпишу все рёбра получившегося дерева.