交互题。有一棵树，需要通过至多(45000)次Ask操作确定这棵树的形态。
(Ask(x,y,P))表示只通过集合(P)中的点(x)和(y)是否连通。
每个点的度数至多为(7)。
(nle 1400)
自己想出的有77分。
先想链咋做。定义过程(work(l,r))，表示确定夹在(l)和(r)中的点。将没有确定点排成一个序列，然后分治找出任意找出一个夹在(l,r)中的点(x)（询问时取一堆点的补集表示判断这堆点是否有(l,r)间的必经点）。然后进入(work(l,x),work(x,r))递归进行。由于每个点只会被找到一次，所以次数是(O(nlg n))的。
尝试扩展到树上。考虑扩展(0)所在的连通块。每次随意选一个块外的点(z)，然后找到块中离(z)最近的点(y)。后面的问题就相当于(work(y,z))。于是每次可以在拉出一条链。拉出这条链的过程是(O(nlg n))。问题是找(y)：我写的是带根点分治，次数大概是(O(nlog_{frac{3}{2}}n))。
满分做法：
也是扩展(0)所在的连通块。找到一个块外的与块直接相连的点(x)，然后搞出块内所有和它直接相连的点：以某个点为根，搞个序，满足每个点的父亲一定在这个点之前出现，dfs序和bfs序都行，然后在这个序上二分，判断是仅保留一段前缀和(x)是否连通。于是就可以找出这个序上最小的和(x)直接相连的点，把它标记删掉，原来的连通块分成几个连通块递归着重复上面的过程。
至于如何找与块直接相连的点(x)：
可以任意找个块外点(z)，用类似上面链的做法拉出一条链。具体而言，就是定义(work(z))，表示将连通块扩展到(z)。先判断块和(z)是否直接相邻。每次二分找到任意一个夹在块和(z)的点(y)，然后依次做(work(y))（此时注意把(z)删除）和(work(z))。
这里的二分是：找一个最短的前缀，使得只经过这个前缀的点可以到达(z)。可以保证这个前缀尾端的那个点一定存在于(z)到这棵树的某一条路径上。这样最终一定可以拉出一条链来。
using namespace std;
#include <bits/stdc++.h>
#include "park.h"
namespace Subtask_all{
const int N=1405;
void answer(int x,int y){
// printf("%d %d
",x,y);
Answer(min(x,y),max(x,y));
}
int ask(int x,int y,int p[]){
return Ask(min(x,y),max(x,y),p);
}
int p[N],p_[N];
int n;
struct EDGE{
int to;
EDGE *las;
} e[N*14];
int ne;
EDGE *last[N];
void link(int u,int v){
e[ne]={v,last[u]};
last[u]=e+ne++;
e[ne]={u,last[v]};
last[v]=e+ne++;
}
int vis[N];
int q[N];
int bz[N],BZ;
int era[N],BZ2;
void divide(int x,int z){
static int q[N];
int head=1,tail=1;
q[1]=x;
bz[x]=++BZ;
while (head<=tail){
int y=q[head++];
for (EDGE *ei=last[y];ei;ei=ei->las)
if (bz[ei->to]!=BZ && era[ei->to]!=BZ2){
bz[ei->to]=BZ;
q[++tail]=ei->to;
}
}
int l=1,r=tail,b=tail;
for (int i=1;i<=tail;++i)
p_[q[i]]=1;
int tmp=ask(x,z,p_);
if (tmp==0){
while (b)
p_[q[b--]]=0;
return;
}
while (l!=r){
int mid=l+r>>1;
for (;b<mid;++b)
p_[q[b+1]]=1;
for (;b>mid;--b)
p_[q[b]]=0;
int tmp=ask(x,z,p_);
if (tmp==1)
r=mid;
else
l=mid+1;
}
int y=q[l];
while (b)
p_[q[b--]]=0;
era[y]=BZ2;
answer(y,z);
for (EDGE *ei=last[y];ei;ei=ei->las)
if (era[ei->to]!=BZ2)
divide(ei->to,z);
link(y,z);
}
void find(int z){
++BZ2;
p_[z]=1;
divide(0,z);
p_[z]=0;
}
// int cnt;
void gt(int x){
static int ls[N];
int k=0;
for (int i=0;i<n;++i)
if (!vis[i] && i!=x)
ls[++k]=i;
else
p_[i]=1;
int tmp=ask(0,x,p_);
if (tmp==1){
memset(p_,0,sizeof(int)*n);
find(x);
vis[x]=1;
return;
}
int b=0,l=1,r=k;
while (l!=r){
int mid=l+r>>1;
for (;b<mid;++b)
p_[ls[b+1]]=1;
for (;b>mid;--b)
p_[ls[b]]=0;
int tmp=ask(0,x,p_);
// cnt++;
if (tmp==0)
l=mid+1;
else
r=mid;
}
for (;b;--b)
p_[ls[b]]=0;
int y=ls[l];
vis[x]=1;
gt(y);
vis[x]=0;
gt(x);
}
void work(int _n){
n=_n;
for (int i=0;i<n;++i)
p[i]=1;
vis[0]=1;
for (int i=0;i<n;++i)
q[i]=i;
srand(time(0)^*new(int));
random_shuffle(q,q+n);
for (int i=0;i<n;++i){
int x=q[i];
if (!vis[x])
gt(x);
}
// printf("%d
",cnt);
}
}
void Detect(int T, int n) {
Subtask_all::work(n);
}