LOJ2398. 「JOISC 2017 Day 3」自然公园

交互题。有一棵树，需要通过至多\(45000\)次Ask操作确定这棵树的形态。

\(Ask(x,y,P)\)表示只通过集合\(P\)中的点\(x\)和\(y\)是否连通。

每个点的度数至多为\(7\)。

\(n\le 1400\)

自己想出的有77分。

先想链咋做。定义过程\(work(l,r)\)，表示确定夹在\(l\)和\(r\)中的点。将没有确定点排成一个序列，然后分治找出任意找出一个夹在\(l,r\)中的点\(x\)（询问时取一堆点的补集表示判断这堆点是否有\(l,r\)间的必经点）。然后进入\(work(l,x),work(x,r)\)递归进行。由于每个点只会被找到一次，所以次数是\(O(n\lg n)\)的。

尝试扩展到树上。考虑扩展\(0\)所在的连通块。每次随意选一个块外的点\(z\)，然后找到块中离\(z\)最近的点\(y\)。后面的问题就相当于\(work(y,z)\)。于是每次可以在拉出一条链。拉出这条链的过程是\(O(n\lg n)\)。问题是找\(y\)：我写的是带根点分治，次数大概是\(O(n\log_{\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 
#include "park.h"

namespace Subtask_all{
	const int N=1405;
	void answer(int x,int y){
//		printf("%d %d\n",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 (;bmid;--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>1;
			for (;bmid;--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