题解：prufer序列

一、题目分析

本题要求实现prufer序列与无根树之间的相互转化。给定一棵有(n)个节点的无根树，以及该无根树的一个序列（父亲序列或prufer序列），需要求出另一个序列。为方便描述，将无根树描述为以(n)号节点为根的有根树，父亲序列(f_1, f_2, \cdots, f_{n - 1})表示(i)号节点的父节点编号，prufer序列为(p_1, p_2, \cdots, p_{n - 2})。

二、解题思路

（一）无根树转prufer序列（tree2prufer函数）

1. 读取父亲序列并统计度数：遍历(1)到(n - 1)的节点，读取每个节点的父节点编号存入f[i]，并将父节点的度数d[f[i]]加(1)。
2. 构建prufer序列：
   • 从(1)号节点开始，找到第一个度数为(0)的节点(j)，将其父亲节点f[j]存入prufer序列p[i]，然后将f[j]的度数减(1)。
   • 检查是否存在度数变为(0)且编号小于当前(j)的节点，如果存在，将其父亲节点也存入prufer序列，并继续检查，直到不存在这样的节点。
   • 重复上述过程，直到prufer序列构建完成（长度为(n - 2)）。
3. 输出prufer序列：遍历prufer序列并输出。

（二）prufer序列转无根树（prufer2tree函数）

1. 读取prufer序列并统计度数：遍历(1)到(n - 2)，读取prufer序列存入p[i]，并将对应节点的度数d[p[i]]加(1)，同时将p[n - 1]设为(n)（表示根节点）。
2. 构建父亲序列：
   • 从(1)号节点开始，找到第一个度数为(0)的节点(j)，将其父亲节点设为p[i]，即f[j] = p[i]，然后将p[i]的度数减(1)。
   • 检查是否存在度数变为(0)且编号小于当前(j)的节点，如果存在，将其父亲节点设为p[i + 1]，即f[p[i]] = p[i + 1]，并将i加(1)，继续检查，直到不存在这样的节点。
   • 重复上述过程，直到父亲序列构建完成（长度为(n - 1)）。
3. 输出父亲序列：遍历父亲序列并输出。

（三）主函数（main函数）

读取节点数n和给定序列类型m，若m == 1，表示给定父亲序列，调用tree2prufer函数将无根树转换为prufer序列；否则，表示给定prufer序列，调用prufer2tree函数将prufer序列转换为无根树（以父亲序列形式输出）。

三、代码实现细节

（一）头文件与全局变量

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int f[N], d[N], p[N];

• 引入输入输出、标准输入输出、字符串操作和算法相关头文件。
• 定义常量N表示节点数的上限。
• 定义变量n为无根树的节点数，m为给定序列类型。
• 定义数组f存储父亲序列，d存储节点度数，p存储prufer序列。

（二）无根树转prufer序列函数tree2prufer

void tree2prufer()
{
    for (int i = 1; i < n; i ++ )
    {
        scanf("%d", &f[i]);
        d[f[i]] ++ ;
    }

    for (int i = 0, j = 1; i < n - 2; j ++ )
    {
        while (d[j]) j ++ ;
        p[i ++ ] = f[j];
        while (i < n - 2 && -- d[p[i - 1]] == 0 && p[i - 1] < j) p[i ++ ] = f[p[i - 1]];
    }

    for (int i = 0; i < n - 2; i ++ ) printf("%d ", p[i]);
}

• 读取父亲序列并统计父节点度数。
• 找到度数为(0)的节点，构建prufer序列，同时处理因节点度数变化产生的连锁反应。
• 输出prufer序列。

（三）prufer序列转无根树函数prufer2tree

void prufer2tree()
{
    for (int i = 1; i <= n - 2; i ++ )
    {
        scanf("%d", &p[i]);
        d[p[i]] ++ ;
    }
    p[n - 1] = n;

    for (int i = 1, j = 1; i < n; i ++, j ++ )
    {
        while (d[j]) j ++ ;
        f[j] = p[i];
        while (i < n - 1 && -- d[p[i]] == 0 && p[i] < j) f[p[i]] = p[i + 1], i ++ ;
    }

    for (int i = 1; i <= n - 1; i ++ ) printf("%d ", f[i]);
}

• 读取prufer序列并统计节点度数，设置根节点。
• 找到度数为(0)的节点，构建父亲序列，同时处理因节点度数变化产生的连锁反应。
• 输出父亲序列。

（四）main函数

int main()
{
    scanf("%d%d", &n, &m);
    if (m == 1) tree2prufer();
    else prufer2tree();

    return 0;
}

读取节点数和序列类型，根据类型调用相应的转换函数。

四、时间复杂度和空间复杂度

（一）时间复杂度

• 无根树转prufer序列：读取父亲序列时间复杂度为(O(n))，构建prufer序列过程中，每次找度数为(0)的节点和处理连锁反应，时间复杂度近似为(O(n))，所以该函数总时间复杂度为(O(n))。
• prufer序列转无根树：读取prufer序列时间复杂度为(O(n))，构建父亲序列过程中，每次找度数为(0)的节点和处理连锁反应，时间复杂度近似为(O(n))，所以该函数总时间复杂度为(O(n))。
• 主函数中根据条件调用相应函数，整体时间复杂度为(O(n))。

（二）空间复杂度

代码中使用了三个数组f、d、p，大小均为(N)，所以空间复杂度为(O(N))，即(O(n))。