[APIO2020] 有趣的旅途

由于官方数据包过大，本题仅评测部分数据。 本题仅支持 C++ 系列语言，提交时**不需要**包含 `fun.h` 头文件，但需要在程序开头声明 `int hoursRequired(int,int)` 以及 `int attractionsBehind(int,int)`。如果您不明白这是什么意思，也可以直接将 `fun.h` 中的内容粘贴到程序的开头。 交互库在程序非正常结束时可能会返回一些奇怪的信息。 如果交互库存在其他问题，请私信 mrsrz。

雅加达最大的主题公园中有 $N$ 个景点，它们从 $0$ 到 $N -1$ 编号。这些景点由 $N-1$ 条双向道路连接，任意两个景点间经由这些道路将存在唯一一条简单路径。道路从 $0$ 到 $N - 2$ 编号。第 $i$ 条道路连接第 $A[i]$ 个景点与第 $B[i]$ 个景点，经过这条道路需要花费一个小时。为了避免拥塞，每个景点将至多与三条道路相连。 你想寻找一条游玩路线并使得每个景点都被参观一次。你认为从一个景点走到下一个景点时经过太多道路是十分无聊的。为了寻找一条有趣的路线，你打算安排景点的参观顺序，使得参观下一个景点所花费的时间不超过参观之前景点所花费的时间。换句话说，你想找到一个序列 $P[0], P[1],\dots, P[N - 1]$ 使其包含 $0$ 到 $N - 1$ 中的所有整数恰好一次，并且从第 $P[i]$ 个景点到达第 $P[i + 1]$ 个景点所需的时间不超过从第 $P[i - 1]$ 个景点到达第 $P[i]$ 个景点所需的时间，其中 $0 < i < N - 1$。 你手上没有景点的完整地图，因此你必须向信息中心进行若干次询问才能找到一条有趣路线。你最多能进行 $Q$ 次询问，每次询问需要提供两个参数 $X$ 和 $Y$ ，其中 $0 \leq X, Y < N$。每次询问是以下任意一种： - 从第 $X$ 个景点到第 $Y$ 个景点需要花费多少个小时。特别地，若 $X = Y$ 则回答将是 $0$。 - 有多少个景点 $Z$ 满足，当你想从第 $X$ 个景点到达第 $Z$ 个景点时一定会经过第 $Y$ 个景点。第 $Y$ 个景点将会被计算在内，特别地，若 $X = Y$ 则回答将是 $N$。 你必须实现 `createFunTour` 函数： - `createFunTour(N, Q)` - 该函数将被评测库恰好调用一次。 - $N$：一个整数表示景点的数量。 - $Q$：一个整数表示询问次数的最大值。 - 该函数可以调用以下两个交互函数： - `hoursRequired(X, Y)` - $X$：一个整数表示第一个景点的编号。 - $Y$：一个整数表示第二个景点的编号。 - 该函数将返回一个整数表示从第 $X$ 个景点到第 $Y$ 个景点需要花费的小时数。 - 如果 $X$ 或 $Y$ 的值不在 $0$ 到 $N - 1$ 的范围内，该测试点将视为答案错误。 - `attractionsBehind(X, Y)` - $X$：一个整数表示第一个景点的编号。 - $Y$：一个整数表示第二个景点的编号。 - 该函数将返回一个整数表示有多少个景点 $Z$ 满足，当你想从第 $X$ 个景点到达第 $Z$ 个景点时一定会经过第 $Y$ 个景点。 - 如果 $X$ 或 $Y$ 的值不在 $0$ 到 $N - 1$ 的范围内，该测试点将视为答案错误。 - 该函数必须返回一个长为 $N$ 的整数序列，表示你找到的景点参观顺序。

样例评测库将读入以下格式的数据： ``` N Q A[0] B[0] A[1] B[1] . . . A[N-2] B[N-2] ```

如果 `createFunTour` 正确返回了一个满足题意的序列，并且 `hoursRequired` 和 `attractionsBehind` 的调用次数总和不超过 $Q$，那么样例评测库将会输出 `createFunTour` 得到的序列。其他情况下样例评测库将会输出错误信息

7 400000
0 1
0 5
0 6
1 2
1 4
2 3

3 6 4 5 2 0 1

在下图的例子中 $N = 7$，$Q = 400 000$，$A = [0, 0, 0, 1, 1, 2]$，$B = [1, 5, 6, 2, 4, 3]$。  评测库将调用 `createFunTour(7, 400000)`。 - 如果你询问 `hoursRequired(3, 5)`，函数将返回 $4$。 - 如果你询问 `hoursRequired(5, 4)`，函数将返回 $3$。 - 如果你询问 `attractionsBehind(5, 1)`，函数将返回 $4$。从第五个景点到第一、二、三、四个景点将一定会经过第一个景点。 - 如果你询问 `attractionsBehind(1, 5)`，函数将返回 $1$。 - 一个符合要求的返回序列为 $[3, 6, 4, 5, 2, 0, 1]$，到达下一个参观景点所需的时间按顺序分别为 $[4, 3, 3, 3, 2, 1]$。 【条件限制】 - $2 \leq N \leq 100 000$。 - $Q = 400 000$。 - 任意两个景点间可以通过双向道路互相到达。 - 每个景点至多连接着三条道路。 【子任务 $1$（$10$ 分）】 - $N \leq 17$。 【子任务 $2$（$16$ 分）】 - $N \leq 500$。 【子任务 $3$（$21$ 分）】 - 对所有的 $1 \leq i < N$，有一条连接着第 $i$ 个景点与第 $\lfloor \dfrac{i-1}{2} \rfloor$ 个景点的双向道路。 【子任务 $4$（$19$ 分）】 存在至少一个景点 $T$ 使得对于所有 $0 \leq i < N$，`hoursRequired(T, i)` $<30$ 并且存在一个整数区间 $[L[i], R[i]](0 \leq L[i] \leq i \leq R[i] < N)$ 满足下列条件： - 从第 $T$ 个景点到达第 $j$ 个景点必须经过第 $i$ 个景点当且仅当 $L[i] \leq j \leq R[i]$。 - 若 $L[i] < i$，则恰有一个景点 $X$ 满足： - $L[i] \leq X < i$。 - 有一条连接第 $i$ 个景点与第 $X$ 个景点的道路。 - 若 $i < R[i]$，则恰有一个景点 $Y$ 满足： - $i < Y \leq R[i]$。 - 有一条连接第 $i$ 个景点与第 $Y$ 个景点的道路。 【子任务 $5$（$34$ 分）】 - 无附加限制。