题解

本题是一道交互式树构造问题，使用重链剖分 + Treap 维护树的结构。

算法思路：

1. 问题分析：

   • 需要通过 explore(u, v) 交互查询构造一棵树
   • explore(u, v) 返回从 $u$ 到 $v$ 路径上 $u$ 的下一个节点
   • 根据 dataType 选择不同策略（链或一般树）

2. 策略一：链的情况（dataType=3）：

   • 维护链的左端点 nl 和右端点 nr
   • 随机选择未加入的点 $u$
   • 通过 explore(nl, u) 和 explore(nr, u) 判断 $u$ 应该接在哪一端
   • 更新链的端点并继续

3. 策略二：一般树（其他dataType）：

   • 使用重链剖分维护树的结构
   • 将树分解成若干条重链
   • 使用 Treap 维护每条重链上的信息：
     • val[x]：节点 $x$ 对应的贡献值
     • tr[x]：子树 $x$ 的总贡献
     • sz[x]：子树 $x$ 的大小

4. 找树根（GBT函数）：

   • 在当前重链上二分查找重心（贡献值中位数）
   • 通过 explore(g, goal) 查询目标节点的位置
   • 根据返回结果决定是在当前链继续查找还是跳到其他链

5. 动态维护：

   • split：将 Treap 按照 $k$ 分裂成两部分
   • merge：合并两个 Treap
   • upd：更新路径上的权值
   • add：在指定位置增加权值

6. 树的构造过程：

   • 逐个加入节点，通过 GBT 找到插入位置
   • 更新重链剖分和 Treap 结构
   • 维护父子关系、深度等信息

时间复杂度：$O(n \log n)$，每个节点的插入需要 $O(\log n)$ 次查询。

这是一道结合了交互、树结构维护和高级数据结构的综合性问题。

#include "rts.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ls u<<1
#define rs u<<1|1
#define mid ((l+r)>>1)
#define lp ch[x][0]
#define rp ch[x][1]
int n;
const int N=300005;
mt19937 rd(time(0));
namespace pool{
	int tr[4*N];
	void build(int l,int r,int u){
		tr[u]=r-l+1-(l==1);
		if(l==r) return;
		build(l,mid,ls),build(mid+1,r,rs);
	}
	void del(int l,int r,int u,int p){
		if(l==r) {tr[u]=0;return;}
		p<=mid?del(l,mid,ls,p):del(mid+1,r,rs,p);
		tr[u]=tr[ls]+tr[rs];
	}
	int kth(int l,int r,int u,int k){
		if(l==r) return l;
		if(k<=tr[ls]) return kth(l,mid,ls,k);
		return kth(mid+1,r,rs,k-tr[ls]);
	}
	void bk(int u){del(1,n,1,u);}
	int get(){return kth(1,n,1,rd()%tr[1]+1);}
}
namespace ghf{
	int l[N],r[N];
	void lk(int x,int y){r[x]=y,l[y]=x;}
	void solve(){
		int nl=1,nr=1;
		while(pool::tr[1]){
			int u=pool::get(),v;
			if((v=explore(nl,u))==r[nl]){
				while(nr!=u){v=explore(nr,u),lk(nr,v),nr=v,pool::bk(v);}
			}
			else{
				lk(v,nl),nl=v,pool::bk(v);
				while(nl!=u) v=explore(nl,u),lk(v,nl),nl=v,pool::bk(v);
			}
		}
	}
}
namespace thy{
	int fa[N],son[N],top[N],bot[N],goal,dep[N],lst;
	int idx,rt[2*N],tr[N],val[N],sz[N],p[N],ch[N][2];
	void up(int x){
		tr[x]=tr[lp]+tr[rp]+val[x];
		sz[x]=sz[lp]+sz[rp]+1;
	}
	int merge(int x,int y){
		if(!x||!y) return x+y;
		if(p[x]<p[y]) return rp=merge(rp,y),up(x),x;
		return ch[y][0]=merge(x,ch[y][0]),up(y),y;
	}
	void split(int x,int &l,int &r,int k){
		if(!x){l=r=0;return;}
		if(sz[lp]+1<=k) l=x,split(rp,rp,r,k-sz[lp]-1);
		else r=x,split(lp,l,lp,k);
		up(x);
	}
	void add(int x,int k,int w){
		if(sz[lp]+1<k) add(rp,k-sz[lp]-1,w);
		else if(k<=sz[lp]) add(lp,k,w);
		else val[x]+=w;
		up(x);
	}
	int findrt(int x,int k){
		if(k>tr[lp]+val[x]) return findrt(rp,k-(tr[lp]+val[x]));
		if(k<=tr[lp]) return findrt(lp,k);
		return x;
	}
	int GBT(int u,int up,int dn){
		int g=findrt(rt[u],(tr[rt[u]]+1)/2),to=explore(g,goal),res;
		if(top[to]==u){
			if(dep[to]>dep[g]){
				split(rt[u],rt[++idx],rt[u],dep[g]-dep[up]+1);
				res=GBT(u,son[g],dn),rt[u]=merge(rt[idx--],rt[u]);
			}
			else{
				split(rt[u],rt[u],rt[++idx],dep[g]-dep[up]);
				res=GBT(u,up,fa[g]),rt[u]=merge(rt[u],rt[idx--]);
			}
		}
		else res=to,lst=g;
		return res;
	}
	void upd(int x,int w){
		while(x){
			add(rt[top[x]],dep[x]-dep[top[x]]+1,w);
			x=fa[top[x]];
		}
	}
	void solve(){
		rt[top[1]=bot[1]=1]=1,idx=n;
		p[1]=rand(),sz[1]=val[1]=tr[1]=1;
		while(pool::tr[1]){
			goal=pool::get();int nw=1;
			while(nw=GBT(nw,nw,bot[nw]),top[nw]);
			fa[nw]=lst,dep[nw]=dep[lst]+1;
			val[nw]=tr[nw]=sz[nw]=1,p[nw]=rand(),rt[nw]=nw;
			if(top[lst]==bot[top[lst]]){
				top[nw]=top[lst],bot[top[nw]]=nw,son[lst]=nw;
				rt[top[nw]]=merge(rt[top[nw]],rt[nw]);
			}
			else top[nw]=bot[nw]=nw;
			pool::bk(nw);
			int w=1;
			while(nw!=goal){
				lst=nw,nw=explore(nw,goal),w++,pool::bk(nw);
				dep[nw]=dep[lst]+1,fa[nw]=lst,son[lst]=nw,top[nw]=top[lst],bot[top[nw]]=nw;
				val[nw]=tr[nw]=sz[nw]=1,p[nw]=rand(),rt[nw]=nw;
				rt[top[nw]]=merge(rt[top[nw]],rt[nw]);
			}
			upd(fa[top[nw]],w);
		}
	}
}
void play(int num, int T, int dataType) {
	srand(time(0));
	n=num,pool::build(1,n,1);
	if(dataType==3) ghf::solve();
	else thy::solve();
}