P9075 [WC/CTS2023] 树据结构
题目背景
**这是一道交互题。**
**在提交本题前请务必仔细阅读以下内容。**
本题只支持 C++ 语言提交（建议使用 C++14，请不要使用 C++14 (GCC9)）。
由于洛谷特殊的交互机制，在提交本题时，请去掉代码中的 ```#include "ds.h"``` 语句，并将以下内容粘贴到代码最开头，然后提交：
```cpp
#include
void exchange(int x, int y);
int query(int u);
void answer(std::vector par, std::vector val);
```
如果您在提交本题时出现了任何意外的情况，请咨询管理员。
题目描述
作为一个熟练的 OI 选手，你对数据结构的各种题型早已轻车熟路，比赛中只要碰到数据结构题就能三下五除二轻松搞定。这一天，你翻开 OJ，看到了这道题：
给定 $n$ 个点的有根树，点编号为 $1, 2, \dots, n$，$1$ 为根。每条边上有一个 $1$ 至 $n - 1$ 的**两两不同**的权值。维护一个数据结构，支持交换**权值为 $x$ 和 $y$** 的边的权值，以及询问从根节点到 $u$ 号点的所有的边的权值最大值。
这种简单而经典的树上问题，对你已经是不在话下。厌倦了维护修改，回答询问的你，打算换一个角色。这回，你才是那个提问题的人，你需要构造合适的操作来套取题的数据。
具体地说，现在你并不知道树的结构，也不知道初始时树上每条边的权值，你需要通过如下两种操作得到树的结构和 **初始时** 树上每条边的权值：
1. 给出正整数 $x, y$，其中 $1 \le x, y < n$，$x \neq y$，交换 **权值为 $x, y$** 的两条边的权值。
2. 给出正整数 $u$，其中 $2 \le u \le n$，并得到从 $1$ 号点到 $u$ 号点的路径上所有边中权值的最大值。
**题目保证树的形态和每条边的权值是预先给定的，不会根据你的操作而动态生成。**
**【实现细节】**
你需要引用头文件 `#include "ds.h"`。你可以调用以下函数与交互库进行交互：
```cpp
void exchange(int x, int y);
```
+ 这个函数对应操作 $1$，表示交换**权值为 $x, y$** 的两条边的权值。
+ 你需要保证 $1 \le x, y < n$，$x \neq y$。
```cpp
int query(int u);
```
+ 这个函数对应操作 $2$，返回从 $1$ 号点到 $u$ 号点的路径上所有边的权值的最大值。
+ 你需要保证 $2 \le u \le n$。
```cpp
void answer(std::vector par, std::vector val);
```
- 这个函数用来回答你所得到的答案，格式如下：
- `par` 是一个长度为 $n - 1$ 的数组，其中 `par[i]` 表示树上 $i + 2$ 号节点的父亲编号，其中 $0 \le i \le n - 2$。
- `val` 也是一个长度为 $n - 1$ 的数组，其中 `val[i]` 表示树上 $i + 2$ 号节点到它父亲的边的**初始权值**，其中 $0 \le i \le n - 2$。
- **你需要调用该函数恰好一次！**
你不需要，也不应该实现主函数。在本题中，你只需要实现如下函数：
```cpp
void solve(int n, int lim1, int lim2);
```
- 其中，$n$ 表示树的点数，$lim1$ 表示操作 $1$ 的次数限制，$lim2$ 表示操作 $2$ 的次数限制。
- 最终测试时，对于每个测试点，交互库会调用**恰好一次** `solve` 函数，并根据调用 `answer` 函数的正误来评分。
在题目附件中，我们提供了 `sample.cpp` 供你参考，你可以在此基础上实现你的程序。
**【测试程序方式】**
题目附件中提供了 `grader.cpp` 文件。最终测试的交互库与下发交互库有不同，因此你的实现不应依赖交互库实现。
你需要将你的程序 `ds.cpp` 和 `grader.cpp`、`ds.h` 放置在同一目录下，并在该目录下使用如下编译命令得到可执行程序 `ds(.exe)`：
```bash
g++ -o ds ds.cpp grader.cpp -O2 -std=c++14 -lm
```
**题目附件还提供了 `compile.sh`，其内容为该编译命令。你可以运行它进行编译，也可以复制该文件中的编译命令进行编译。**
可执行程序从标准输入读入以下格式的数据：
- 第一行包含三个正整数 $n, lim1, lim2$，表示树的点数，操作 $1$ 的限制次数和操作 $2$ 的限制次数。交互库保证可以处理 $2 \le n \le 500000$ 的情况，对于 $n > 500000$ 的情况不做正确运行保证。
- 第二行 $n - 1$ 个正整数 $p_2, p_3, \dots, p_n$。其中 $p_i$ 表示 $i$ 号点的父亲的节点编号。**你需要保证 $1 \le p_i \le n$ 且输入给出了合法的树的结构。**
- 第三行 $n - 1$ 个正整数 $v_2, v_3, \dots, v_n$。其中 $v_i$ 表示 $i$ 连向 $p_i$ 的边的权值。**你需要保证 $v_2, v_3, \dots, v_n$ 构成 $1$ 至 $n - 1$ 的一个排列。**
- **在本地测试时，请务必保证你的输入格式符合要求，否则我们不保证交互库会正常运行。**
如果你的输入合法且没有运行错误，下发的交互库将会根据你的调用输出如下信息：
- 如果某次 `exchange` 函数的调用违反了 $1 \le x, y < n$，$x \neq y$ 的限制，输出错误信息：`Invalid call of exchange(x, y)!`。
- 如果 `exchange` 函数调用次数超过 $lim1$，输出错误信息：`Too many exchanges!`。
- 如果某次 `query` 函数的调用违反了 $2 \le u \le n$ 的限制，输出错误信息：`Invalid call of query(u)!`。
- 如果 `query` 函数调用次数超过 $lim2$，输出错误信息：`Too many queries!`。
- 在输出任何以上错误信息后，交互库立即终止。
- 交互库会在你**每次**调用 `answer` 函数时输出提示信息：
- 如果 `par` 或 `val` 的长度不是 $n - 1$，则输出 `Invalid output!`。
- 如果 `par` 数组与树的形态不同，那么它会给出**第一个**错误的位置，并返回如下格式的错误信息：`The answer to p[i] is wrong! The right answer is j, but you output k.`。注意，这里 $2 \le i \le n$，$j = p_i$ 为 $i$ 号点的真正的父亲编号，$k = $ `par[i - 2]` 为你给出的位置编号。
- 如果 `par` 数组正确，但 `val` 数组与**初始时**树上边权值不同，那么它会给出你**第一个**错误的位置，并返回如下格式的错误信息：`The answer to v[i] is wrong! The right answer is j, but you output k.`。类似地，这里 $2 \le i \le n$，$j = v_i$ 为 $i$ 号点到它父亲的边的真正的初始权值，$k =$ `val[i - 2]` 为你给出的权值。
- 如果你给出的 `par` 和 `val` 数组正确，那么交互库会输出你调用 `exchange` 函数和 `query` 函数的次数。输出格式为：`Right output! cnt1 = A, cnt2= B.`，其中 $A$ 表示你调用 `exchange` 函数的次数，$B$ 表示你调用 `query` 函数的次数。
- **使用下发的交互库时你可以通过调用多次 `answer` 函数对你的程序进行测试。但对于你提交的代码，如果调用 `answer` 函数超过 $1$ 次，便只能获得 $0$ 分。**
**你的程序不应该操作标准输入输出，否则视为攻击交互库。**
输入格式
见【测试程序方式】。
输出格式
见【测试程序方式】。
说明/提示
**【样例解释 #1】**
一种可能的输入如下：
+ $2$ 号点的父亲是 $1$，$1$ 到 $2$ 的边初始权值为 $2$。
+ $3$ 号点的父亲是 $2$，$2$ 到 $3$ 的边初始权值为 $1$。
一种可能的交互过程如下：
+ 调用 `query(2)`，返回 $2$。
+ 调用 `exchange(1, 2)`。此时，$1$ 到 $2$ 的边权值为 $1$，$2$ 到 $3$ 的边权值为 $2$。
+ 调用 `query(2)`，返回 $1$。此时，我们可以知道 $1$ 与 $2$ 直接相连。
+ 调用 `query(3)`，返回 $2$。
+ 调用 `exchange(1, 2)`。
+ 调用 `query(3)`，返回 $2$。此时，我们可以推出 $2$ 与 $3$ 直接相连。
+ 调用 `query(2)`，返回 $2$。此时，我们可以推出在两次 `exchange` 操作之后，$1$ 到 $2$ 的边权值为 $2$，$2$ 到 $3$ 的边的权值为 $1$。
+ 调用 `answer([1, 2], [2, 1])`，结束程序。
**【样例解释 #2】**
这个样例满足 $n \le 50$ 和特殊性质 A 的条件。
**【样例解释 #3】**
这个样例满足 $n \le 1000$。
**【样例解释 #4】**
这个样例满足 $n \le 20000$ 和特殊性质 B 的条件。
**【样例解释 #5】**
这个样例满足 $n \le 100000$ 和特殊性质 A 的条件。
**【样例解释 #6】**
这个样例满足 $n \le 100000$。
**【样例解释 #7】**
这个样例满足 $n \le 500000$。
**【数据范围】**
|测试点编号|$n=$|$lim1=$|$lim2=$|特殊性质|
|:-:|:-:|:-:|:-:|:-:|
|$1$|$10$|$1000001$|$1000001$|A|
|$2$|$10$|$1000001$|$1000001$|A|
|$3$|$50$|$1000002$|$1000002$|A|
|$4$|$50$|$1000002$|$1000002$|A|
|$5$|$600$|$3000003$|$3000003$|A|
|$6$|$600$|$3000003$|$3000003$|A|
|$7$|$1000$|$1100004$|$2200004$|A|
|$8$|$1000$|$1100005$|$2200005$||
|$9$|$1000$|$1100005$|$2200005$||
|$10$|$20000$|$3000006$|$3000006$|B|
|$11$|$20000$|$3000006$|$3000006$|B|
|$12$|$20000$|$3000006$|$3000006$|B|
|$13$|$100000$|$3000007$|$3000007$|A|
|$14$|$100000$|$3000007$|$3000007$|A|
|$15$|$100000$|$3000008$|$3000008$||
|$16$|$100000$|$3000008$|$3000008$||
|$17$|$100000$|$3000008$|$3000008$||
|$18$|$500000$|$3500009$|$3500009$|A|
|$19$|$500000$|$3500009$|$3500009$|A|
|$20$|$500000$|$3500010$|$3500010$|B|
|$21$|$500000$|$3500010$|$3500010$|B|
|$22$|$500000$|$3500011$|$3500011$||
|$23$|$500000$|$3500011$|$3500011$||
|$24$|$500000$|$3500011$|$3500011$||
|$25$|$500000$|$3500011$|$3500011$||
特殊性质 A：
+ 每个节点有不超过 $1$ 个儿子，即树的形态是一条链；
+ 链的非根节点标号在所有可能的标号中等概率随机；
+ 边的权值排列在所有 $(n - 1)!$ 种可能的排列中等概率随机。
特殊性质 B：
+ 树形态按如下方式随机生成：
- 先对每个 $2 \le i \le n$，令 $i$ 的父亲在 $[1, i - 1]$ 的整数之间等概率随机选取，
- **再等概率随机打乱非根节点的编号**，得到最终的带标号有根树的结构。
+ 边的权值排列在所有 $(n - 1)!$ 种可能的排列中等概率随机。
你可以根据 $lim1, lim2$ 的值来判断数据所满足的特殊性质。
**【评分方式】**
**本题首先会受到和传统题相同的限制**。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。
在以上条件下，你能够拿到一个测试点的分数当且仅当你每次调用函数的参数格式正确，调用 `exchange` 函数的次数不超过 $lim1$ 次，调用 `query` 函数的次数不超过 $lim2$ 次，且**第一次**调用 `answer` 函数给出的 `par` 数组和 `val` 数组正确。
保证在下发的交互库和最终评测的交互库中，`exchange` 和 `query` 函数的单次最坏复杂度是 $O(\log n)$，在题目限制下使用时间不超过 $4$ 秒，最大空间占用不超过 $256$ MB。
也就是说，你至少有 $4$ 秒的时间和 $768$ MB 的空间可以使用。
**【提示】**
我们再次提醒：**树的形态和每条边的权值是预先给定的，不会根据你的操作而动态生成。**
你需要注意你的程序的时间开销和空间开销。
**通过访问输入输出文件、攻击评测系统或攻击评测库等方式得分属于作弊行为，所得分数无效。**