CF2001C Guess The Tree 题解

0x00 题目翻译

一棵有 $n$ 个节点的秘密树，索引从 $1$ 到 $n$ ，并要求你使用以下类型的查询来猜测它：

• “? a b” - Misuki 会告诉你哪个节点 $x$ 使 $|d(a,x) - d(b,x)|$ 最小，其中 $d(x,y)$ 是节点 $x$ 和 $y$ 之间的距离。如果存在多个这样的节点，那么 Misuki 会告诉你哪个节点能使 $d(a,x)$ 最小化。

用最多 $15n$ 次查询找出秘密树的结构！

0x01 解题思路

由距离差最小值，想到中点，由 $15n$ 次查询，想到 $O(n\log n)$，于是自然想到类似二分的思想。

什么时候可以确定一条边呢？当我们查询到两个相邻节点（中间有边）时，答案必定是这两个节点中的一个。反推，如果查询到答案是传入的两个点中的一个，这两个点中间有一条边。

这是只需要以 $(n-1)\times\log n$ 次查询，确定 $n-1$ 条边，即完成此题。

首先钦定一个根节点，因为是树，所以任何一个点都可以作为根节点，于是直接令 $1$ 节点为根，如图为例。

容易想到可以尝试遍历除根节点之外的所有点，对于每个点，$\log n$ 次操作确定它和它父亲之间的边。

每次查询得到起点到当前点路上的中点，开始时以根为起点，之后每次以上一次查询的结果为起点，最终当答案为这一次查询的起点时，即可确定当前点与这个点之间有边。（上文中语义可能有点不清，当前点指的是当前遍历到的点）。

具体的例子：

令根为 $1$，当前点为 $5$。

1. 第一次查询 $1\rightarrow5$，得到这条路上的中点为 $4$，因为 $4\neq1$，所以继续。
2. 第二次查询 $4\rightarrow5$，得到这条路上的中点为 $3$，因为 $3\neq4$，所以继续。
3. 第三次查询 $3\rightarrow5$，得到这条路上的中点为 $3$，因为 $3=3$，所以确定有边 $3\leftrightarrow5$。

这实际上就是二分查询，易证复杂度。

0x02 AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int edu[1001],edv[1001],eds;
void solve(){
	eds=0;
	cin>>n;
	for(int i=2;i<=n;i++){
		cout<<"? "<<1<<" "<<i<<endl;
		cin>>ans;
		int u=1,v=i;
		while(ans!=u&&ans!=v){
			u=ans;
			cout<<"? "<<u<<" "<<v<<endl;
			cin>>ans;
		}
		eds++;
		edu[eds]=u;
		edv[eds]=v;
	}
	cout<<"! ";
	for(int i=1;i<n;i++){
		cout<<edu[i]<<" "<<edv[i]<<" ";
	}
	cout<<endl;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}