时间限制： 1.0 秒

空间限制： 512 MB

题目背景

二叉树接口定义

给定以下二叉树的节点接口定义：

struct BinNode
{
    BinNode *lc, *rc; // 左儿子和右儿子
    BinNode *parent; // 父亲（对于根节点为 NULL）
};

同构的定义

对于两棵均由 $n$ 个节点组成的二叉树 $V$ 和 $U$，若节点分别用 $1$ 到 $n$ 之间的整数编号，我们定义两者的【弱同构】和【强同构】分别满足以下条件：

• 弱同构：每一对编号相等的节点 $v\in V$ 和 $u\in U$，均满足 v->parent 和 u->parent 编号相同或同为 NULL。
• 强同构：在弱同构的基础上，还满足 v->lc 和 u->lc 编号相同或同为 NULL，v->rc 和 u->rc 编号相同或同为 NULL。

左偏树的定义

递归定义二叉树节点的 npl 值：

• 对于空节点，npl(nullptr) = 0
• 对于非空节点，npl(v) = 1 + min(npl(v->lc), npl(v->rc))

若对于二叉树每一个非空节点 v 都有 npl(v) = 1 + npl(v->rc)，则称之为左偏树。

特别地，若左偏树还满足堆的性质，则称之为左式堆。

题目描述

你需要实现 leftify 函数，传入一个规模为 $n$ 的二叉树的根节点 $x$，在时间复杂度 $O(n)$ 内，将二叉树转化为与之弱同构的左偏树。

根据题目对【弱同构】的定义，你至多只能交换每个节点的左右子树，而不能修改他们的父亲。

交互方式

这是一道函数式交互题，不需要选手考虑输入输出，也不要从标准输入读入数据，或将任何内容输出到标准输出，否则会影响判题。

你提交的代码需要包含头文件 leftify.h。

你需要实现一个函数 void leftify(BinNode*)，传入参数为待修改二叉树的树根 $x$。你需要在规定时间内对二叉树完成修改。我们保证使用的二叉树节点接口同题目描述。

以下我们给出一个代码提交实例（不做任何修改即返回，仅作为可以通过编译的示例，不保证能得分）：

#include "leftify.h"
void leftify(BinNode* x)
{
    return;
}

你不需要，也不应该，实现主函数。

白盒交互库实例

具体请见附加文件区的 interactor.cc 和 leftify.h。需要注意的是，该白盒交互库并非实际评测使用的交互库。

如果你本地的实现代码为 main.cc，则将交互库放在同一目录下，在 Linux 系统中输入以下命令行即可运行：

g++ main.cc interactor.cc -Wall -std=c++20 -o foo -lm -O2 -I/include

在 Windows 下会生成 foo.exe，在 Linux 下会生成 foo，你可以输入 .\foo.exe 或者 ./foo 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

判题方式解释

白盒与黑盒（即实际评测使用）交互库在原理上相同。

我们会检查以下内容：

• 二叉树结构是否和原本弱同构，即每个节点仅左右儿子做改动，且其父亲指针存在对应的儿子；
• 调整后的二叉树结构是否满足左偏树性质。

7
1 1 3 3 5 5

OK!

样例 1 解释

该样例遵循白盒交互库的形式。

输入的第一行为节点个数。

第二行开始为 $f_2,\cdots,f_n$，表示 $2\sim n$ 的父亲节点。

默认树上编号满足 1 号节点为根，其他节点保证 $1\le f_i<i$，传入 leftify 函数的参数即为 1 号节点的地址。

我们保证每个 $f_i$ 不会出现超过 $2$ 次（从而满足是二叉树结构）。我们约定 $f_i$ 第一次出现时，表示 $i$ 是 $f_i$ 的左儿子；$f_i$ 第二次出现时，表示 $i$ 是 $f_i$ 的右儿子。

当满足上述要求时，白盒交互库会输出 OK! 并停机。需要注意的是，黑盒交互库不会采用这种方式，直接输出 OK! 并结束程序不会得分。

如果不满足上述情况，会分别返回：

• Invalid structure!：二叉树结构不满足弱同构；
• Invalid leftlist!：最终的二叉树不满足左偏树性质。

子任务

对于所有数据，保证节点个数 $n\le 10^6$，输入的树一定是一个二叉树结构。

本题无数据梯度，需要通过全部数据获得所有分数。

提示

一般来说维护一个二叉树的信息，都是自底向上进行节点信息的维护。你可以在边维护 npl 的同时边决定是否需要交换左右子树。

来源

清华 826 考研初试 2025 - 算法大题（2）