0x00 题目翻译

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

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

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

0x01 解题思路

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

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

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

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

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

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

具体的例子：

令根为 11，当前点为 55。

  1. 第一次查询 1→51\rightarrow5，得到这条路上的中点为 44，因为 4≠14\neq1，所以继续。
  2. 第二次查询 4→54\rightarrow5，得到这条路上的中点为 33，因为 3≠43\neq4，所以继续。
  3. 第三次查询 3→53\rightarrow5，得到这条路上的中点为 33，因为 3=33=3，所以确定有边 3↔53\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;
}