本文共 1686 字，大约阅读时间需要 5 分钟。

转：

交互题。

一棵有根树（不知道根）。保证不存在点恰好有一个儿子。需要确定树的形态。

每次可以询问一个长度任意的序列，表示将这些序列中的点顺序加入，记个计数器(cnt)，如果之前没有假如和它互为祖先后代关系的点，则(cnt+1)。返回(cnt)。

(nle 3000)

不超过(45000)次询问。

---

给节点标号，满足：1. 标号相同的点在同一条祖先后代链上。2. 任意点的祖先的标号都小于等于这个点。

用阳间的说法来说：维护个链剖分，同一条链上的标号相同，上面的链标号小于下面的链。

增量造，假设之前加入的点已经标了(1dots k)，标号为(i)的集合为(S_i)，当前加入点(x)。

先(ask(x,S_k,dots,S_1))，如果查出(k+1)，则另开标号。（因为(kdots 1)，相当于是从下往上扫链，于是这些链不会互相影响）。

否则，二分出最小的(c)，(ask(x,S_c,dots,S_1)=c)，于是找到了(x)所在的链。（注意不要找(S_n,dots,S_c)，因为后面的可能是(x)的后代，也能和(x)冲突。只有从前往后第一个与(x)冲突的才是(x)所在的链。）

上面这部分大概用了(k+(n-k)lg n)次。

最终我们得到了所有点的标号。按照标号顺序从大到小还原：之前有标号更大的，但是链顶没有确定父亲的链，将这些链顶和当前标号下每个点查询，通过结果，就可以知道多少个链顶是它的后代。算出之后排序，能知道链的顺序，然后从深到浅，分治找出每个点的儿子。

下面这部分大概用了(n+klg n)次。

---

#include "greedy.h"#include        using namespace std;namespace Subtask5{	const int N=3005;	int vec[N],nv;	vector          q[N];	void ins(vector            &p){		for (int i=0;i             >1;		nv=0,vec[nv++]=x;		for (int i=l;i<=mid;++i)			ins(q[p[i]]);		int tmp=(mid-l+1)-(ask(nv,vec)-1);		if (tmp) lk(x,l,mid,tmp);		if (c-tmp) lk(x,mid+1,r,c-tmp);	}	void work(int _n){		n=_n;		for (int x=1;x<=n;++x){			nv=0,vec[nv++]=x;			for (int i=k;i>=1;--i)				ins(q[i]);			int tmp=ask(nv,vec);			if (tmp==k+1)				q[++k].push_back(x);			else{				int l=1,r=k-1,y=k;				while (l<=r){					int mid=l+r>>1;					nv=0,vec[nv++]=x;					for (int i=mid;i>=1;--i)						ins(q[i]);					tmp=ask(nv,vec);					if (tmp==mid+1)						l=mid+1;					else						r=(y=mid)-1;				}				q[y].push_back(x);			}		}		for (int i=k;i>=1;--i){			tot=0;			nv=1;			for (int j=k;j>i;--j)				if (!bz[j])					ins(q[j]),++tot;			for (int t=0;t       i;--j) if (!bz[j]) p[++cnt]=j; lk(x,1,cnt,w[x]-del); } } } answer(fa+1); }}void solve(int n,int ty){ Subtask5::work(n);}

转：

转载地址：http://fwziz.baihongyu.com/