城市绿化

题目描述

这是一道交互库题。

有一棵 $n$ 个节点的有根树，根为 $1$ 号节点。你不知道这棵树的结构，但可以通过交互库询问任意两个不同节点在树上的距离。

特别地，保证这棵树是一棵二叉树，也就是说每个节点的儿子个数不超过 $2$。

你的任务是在不超过 $m$ 次询问的限制内，还原整棵树。你需要返回每个节点的父亲编号。

---

实现细节

你不需要、也不应该实现 main 函数。你只需要实现下面这个函数：

void findtree(int n, int m, int *p);

其中：

• $n$ 表示节点数；
• $m$ 表示最多允许调用 visit 的次数；
• p 数组初始均为 $0$；
• 在 findtree 结束时，你需要保证：

$$p_i=\text{节点 }i\text{ 的父亲编号}$$

特别地，根节点满足：

$$p_1=0$$

你只能访问和修改 p[1] 到 p[n]。

你可以调用交互库函数：

int visit(int x, int y);

调用要求：

• $1\le x,y\le n$；
• $x\ne y$。

函数返回节点 $x$ 与节点 $y$ 在树上的距离，即两点之间简单路径经过的边数。

如果调用次数超过 $m$，或者调用参数非法，该测试点将判为错误。

---

Hydro OJ 提交说明

本题在 Hydro OJ 中按交互库题配置。提交代码时，请在代码第一行加入：

#include "grader.cpp"

然后在后面实现 findtree 函数。

也就是说，你的提交代码结构应该类似：

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

int visit(int x, int y);

void findtree(int n, int m, int *p) {
    // 在这里写你的算法
}

注意：

• 不要写 main；
• 不要读入；
• 不要输出；
• 不要使用文件输入输出；
• 只能通过 visit(x,y) 获取树上距离；
• 最终答案写入数组 p。

评测时，grader.cpp 会读取隐藏树，提供 visit 函数，统计询问次数，并检查你写入的 p 数组是否正确。

---

本地测试方式

如果你把自己的程序保存为 green.cpp，并且 grader.cpp 与 green.cpp 在同一目录下，可以直接编译：

g++ green.cpp -O2 -std=c++17 -o green

然后运行：

./green < green1_1.in

本地输入格式为：

n m
f1 f2 ... fn

其中 $f_i$ 表示节点 $i$ 的真实父亲，且 $f_1=0$。这部分输入只会被 grader.cpp 读取，选手程序不能直接读入。

如果程序正确，评测库会输出一个用于判定的特殊字符串；Hydro 会根据该字符串判断该测试点是否通过。

---

样例

样例输入

4 6
0 1 4 1

样例输出

0754391330ac01e041a3d3639d4f3af1

样例中的树为：

• $1$ 是根；
• $2$ 的父亲是 $1$；
• $3$ 的父亲是 $4$；
• $4$ 的父亲是 $1$。

一种可能的询问过程为：

visit(1,2) = 1
visit(1,3) = 2
visit(1,4) = 1
visit(3,2) = 3
visit(3,4) = 1

最终应写入：

p[1]=0, p[2]=1, p[3]=4, p[4]=1

---

数据范围与评分

本题共 $6$ 个子任务。每个子任务包含若干测试点，必须通过该子任务所有测试点才能获得该子任务分数。

子任务	分值	$n$	$m$
$1$	$10$	$10^3$	$5\times 10^5$
$2$	$15$	$3\times 10^3$	$6\times 10^5$
$3$	$20$	$10^4$	$10^6$
$4$	$15$	$3\times 10^4$	$2\times 10^6$
$5$		$5\times 10^4$	$3\times 10^6$
$6$	$25$	$10^5$	$5\times 10^6$

对于所有测试点：

$$1\le n\le 10^5,\quad 1\le m\le 5\times 10^6$$

保证输入树合法，根为 $1$，且每个节点的儿子个数不超过 $2$。

---

注意事项

• 本题时限为 2s，空间限制为 512MB。
• 交互库本身会占用一定时间和空间。
• 你的程序不能通过任何方式读取测试数据中的父亲数组。
• 你的程序不能攻击、绕过或修改评测库。
• 本题的树在一次测试中是固定的，不会根据你的询问动态改变。