题目描述

题目译自 JOISC 2019 Day1 T2「ビーバーの会合 / Meetings」

有 $N$ 座住有海狸的岛屿，编号从 $0$ 至 $N - 1$。这些岛由 $N - 1$ 条双向桥梁连接，使得两两互相可达。保证每个岛屿至多连出 $\mathbf{18}$ 座桥。每个岛住有一只海狸。

有时，一些海狸会赶往同一个岛屿进行聚会。当三只海狸进行聚会的时候，它们会按照这一规则选择聚会的岛屿：

• 找到一个岛屿，使得三只海狸到达这个岛屿的距离之和是最小的，可以证明这样的岛屿是唯一的。 这个岛屿可以是其中某一个海狸的家。

你的任务是找出这 $N$ 座岛屿的连接方式。为了获取信息，你可以问海狸这样一个问题：

• 给出三个不同的岛屿 $u, v, w$。
• 询问这三座岛屿上的海狸会赶往聚会的岛屿。

实现细节

你的程序在开头需包含头文件 meetings.h，并实现函数：

void Solve(int N)

该函数每个测试点会被调用一次，参数 N 表示岛屿的数量 $N$。

你的程序可以调用函数：

int Query(int u, int v, int w)

• 表示询问来自岛屿 $u,v,w$ 的海狸聚会的位置岛屿。
• 参数需要满足 $0\le u,v,w \le N - 1$ 且 $u\neq v, u\neq w, v\neq w$，否则会被判定为 Wrong Answer [1]。
• 你的程序运行时调用该函数的次数不能超过 $10^5$ 次，否则会被判定为 Wrong Answer [2]。

void Bridge(int u, int v)

• 表示你确认了 $u,v$ 间有一座桥。
• 参数需满足 $0\le u < v\le N - 1$，否则会被判定为 Wrong Answer [3]。
• 如果事实上 $u,v$ 间不存在桥，会被判定为 Wrong Answer [4]。
• 如果一组 $u,v$ 被调用了多次，会被判定为 Wrong Answer [5]。
• 运行时此函数应被恰被调用 $N - 1$ 次，否则会被判定为 Wrong Answer [6]。

注意事项

• 你可以定义一些其他的函数和全局变量。
• 你的程序中不允许进行标准输入输出，但可以通过错误流进行输出。

编译与运行方法

在下发文件中有一个样例评测程序 grader.cpp，假设你的文件是 meetings.cpp，将 grader.cpp、meetings.h、meetings.cpp 放置在同一个目录下，运行：

g++ -std=gnu++14 -O2 -o grader grader.cpp meetings.cpp

会生成一个可执行文件 grader，他通过标准输入输出流进行输入和输出。

输入格式

指样例评测程序输入格式。

第一行读入一个正整数 $N$。

接下来 $N - 1$ 行，每行两个整数 $A,B$，表示岛屿 $A,B$ 间有一座桥。

输出格式

指样例评测程序输出格式。

如果你的程序满足要求，输出 Accepted: 100。

如果你的程序被判定为答案错误，输出形如 Wrong Answer [1]。

样例

样例输入 1

5
0 1
0 2
1 3
1 4

样例交互

函数调用		返回值
Solve(5)
	Query(0, 1, 2)	0
	Query(0, 3, 4)	1
	Bridge(1, 3)
	Bridge(0, 2)
	Bridge(1, 4)
	Bridge(0, 1)

数据范围与提示

所有数据满足下列条件。$A_i, B_i$ 的含义参照「样例评测程序输入格式」一节。

• $3 \le N \le 2000$
• $0 \le A_i, B_i \le N - 1$
• 保证岛屿之间两两互相可达。
• 保证每个岛屿至多连出 $18$ 座桥。

子任务

• 子任务一（$7\%$） $N\le 7$。
• 子任务二（$10\%$） $N\le 50$。
• 子任务三（$12\%$） $N\le 300$。
• 子任务四（$71\%$） 没有附加限制。设 $X$ 是你在本子任务测试点中进行最多的执行 Query() 的次数。
  • 若 $4\times 10^4 <X \le 10^5$，则获得 $49\%$ 的分数。
  • 若 $X \le 4 \times 10^4$，则获得 $71\%$ 的分数。