时间限制： 1.0 秒

空间限制： 512 MB

题目背景

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

struct BinNode
{
    BinNode *fa;       // 父亲（对于根节点为 NULL）
    BinNode *lc, *rc;  // 左儿子和右儿子
    int size;          // 以当前节点为根的子树节点个数
};

题目描述

你需要实现 void splay_to(BinNode *a, BinNode *x) 函数，传输参数为节点 $a$ 和非空节点 $x$，其中保证 $a$ 为 $x$ 的真祖先，或者为 NULL（空节点）。

在原始的伸展树中，提供了将某一节点伸展至根节点的伸展操作。在该函数中，你需要完成与伸展树相同的伸展操作，但是是将 $x$ 节点伸展至 $a$ 节点的子节点位置。

当 $a$ 为 $x$ 的真祖先时，伸展操作结束后 $a$ 为 $x$ 的父节点。由于伸展操作只使用到左旋和右旋这两个等价变换，因而不会修改原始二叉树的中序遍历序列。因此若中序遍历序列中 $x$ 在 $a$ 前面，则伸展操作结束后 $x$ 为 $a$ 的左子节点，否则 $x$ 为 $a$ 的右子节点。

当 $a$ 为 NULL 时，则与伸展树的伸展操作完全相同，将 $x$ 伸展到树根的位置。

你可以调用函数 void zig(BinNode *) 和 void zag(BinNode *) 函数，二者分别表示以传入的二叉树节点为中心进行右旋或左旋操作。具体效果见下图。

你可以调用函数 bool islc(BinNode *) 和 bool isrc(BinNode *)，分别用于判断传入的二叉树节点是否为其父节点的左子节点/右子节点。当传入节点为空或不存在父亲时，直接返回 false。

交互方式

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

你提交的代码需要包含头文件 splay.h，需要实现的函数以及可调用的函数见【题目描述】。

需要注意的是，由于本题的判题方式需要，交互库中对于 BinNode 节点接口定义会额外增加其他成员或函数，黑盒交互库的额外成员与白盒交互库定义略有不同，因此不能保证访问。但是你可以正常访问【题目背景】中的成员。

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

#include "splay.h"
void splay_to(BinNode *a, BinNode *x)
{
    return;
}

白盒交互库实例

具体见附加文件区的 interactor.cc 和 splay.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 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

交互库首先读入第一行两个正整数 $n,q$，分别表示节点个数和伸展操作次数。

接下来 $n$ 行，每行两个非负整数。第 $i$ 行表示节点 $i$ 的左子节点和右子节点的编号，若为 $0$ 则代表无对应子节点。他们代表了一棵 $n$ 个点，编号为 $1\sim n$ 的二叉树的初始状态，其中保证 $1$ 一定为根。

接下来 $q$ 行，每行两个非负整数 $a,x$，表示需要进行的伸展操作。保证在每次操作之前，$a$ 为 $x$ 的真祖先，或者若 $a$ 为 $0$ 则代表 $a$ 为 NULL 节点。

交互库总计输出 $q+1$ 行，每行一个非负整数，表示初始状态以及每次伸展操作结束之后，所有节点的深度的总和。其中根节点的深度为 $0$。

8 2
2 3
6 4
5 7
0 8
0 0
0 0
0 0
0 0
0 2
2 7

13
15
20

样例 1 解释

两次伸展操作以及三种状态的节点深度总和计算见下方两个图。

第一次伸展操作只需要进行一次单旋操作即可，第二次伸展操作需要看 7-3-1 的祖父-父亲-当前节点关系进行双旋操作（分别左旋 1 和 3），只需要将 7 伸展至 2 的儿子位置即可，因此结束。

子任务

对于所有数据，保证 $n,q\le 10^5$。

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

提示

只要你对伸展操作有较为清晰的认知，稍作修改即可正确地完成本题。

目前白盒/黑盒交互库在复杂度上界上有一些问题，如果正确实现交互库的话应该需要写 Link-Cut-Tree 但是我懒得写了。本题主要只是测 splay_to 实现的正确性，只要你正确实现了该功能，即可在现有评测数据下通过本题。

来源

清华 826 考研初试 2020 - 算法大题（3）