【APIO2020】有趣的旅途
构造
题目大意：
交互题。
有一棵 $n$ 个结点的三度树。要求找到一个结点的排列 $p_1,p_2,\ldots,p_n$，使得 $\forall i\in[1,n-2]$，$\mathrm{dist}(p_i,p_{i+1})\geq\mathrm{dist}(p_{i+1},p_{i+2})$。
可以向交互库进行询问，有两种询问：
- 查询两点在树上的距离。
- 给定 $u,v$，查询在以 $u$ 为根时，$v$ 子树的大小。
要求使用不超过 $4\times 10^5$ 次操作找到合法解。$n\leq 10^5$。
题解：
这是一棵三度树，一个点最多连三个点。
考虑找到树的重心、每个点到根的距离以及每个点分别在哪棵子树中。
我们先钦定一个点作为临时树根。对于一个点，如果它是树的重心，则它所在的子树的大小必须大于等于 $\lfloor\frac{n+1}2\rfloor$。而树的重心，一定是满足条件的结点中，子树大小最小的那个。
于是可以用 $n-1$ 次询问子树大小的操作找到重心。
然后用 $n-1$ 次询问到根距离的操作查询每个点的深度，以及找到重心的儿子。
然后对每个点，我们分别用 $2$ 次操作询问它到重心的其中两个儿子的距离，然后根据它们到重心以及两个儿子的距离就可以判断出这个点在哪棵子树内。
所以总询问数不超过 $4n$，是合法的。
接下来考虑用已知的信息构造答案。
如果重心只有 $2$ 个儿子，则直接每次在两边选深度最大的点就好了。
如果重心有 $3$ 个儿子，则我们从深度最大的结点开始，每次找另外两棵子树中深度大的那个，并走过去。直到满足某两棵子树之和等于第三棵子树的时候，就可以将小的两棵子树合并，然后做 $2$ 个儿子时的问题了。
设三棵子树的大小为 $a,b,c$ 且满足 $a\geq b\geq c$。
若开始时 $a\geq b+c$，则必然满足 $a=b+c+1$，此时可以直接合并 $b$ 和 $c$ 然后做 $2$ 个儿子的问题。
那么 $a<b+c$。
我们每次对 $a$ 操作后，伴随着必然是对 $b$ 或 $c$ 的操作，因此 $(b+c)-a$ 不可能一直变大。
而对 $b$ 或 $c$ 操作后，是可以对另外一者操作的，这会使 $(b+c)-a$ 的值变小。
因此小的两者的和与大的子树会越来越接近，一定会在某时刻和大的子树的大小相等。
另外要注意，如果合并 $b$ 和 $c$ 的时候，最后选的点在 $b$，而 $c$ 最深的点比 $b$ 更深的话，需要从 $b$ 先跳到 $c$ 再合并，否则路径长度会变大，不符合题意。
时间复杂度 $O(n\log n)$（排序）。
Code：
#include"fun.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef vector<int>VI;
int n,rt,sz[N],dep[N];
VI sons,id[3],ans;
inline bool cmp(int a,int b){return dep[a]<dep[b];}
void solve_2(VI a,VI b,int cur){
if(cur)a.swap(b);
while(!a.empty()){
ans.push_back(a.back());
a.pop_back();
a.swap(b);
}
ans.push_back(rt);
}
void solve_3(vector<VI>V){
if((int)V[0].size()==n/2){
for(int i=0;i<(int)V[2].size();++i)
V[1].push_back(V[2][i]);
sort(V[1].begin(),V[1].end(),cmp);
solve_2(V[0],V[1],0);
return;
}
if((int)V[1].size()==n/2){
for(int i=0;i<(int)V[2].size();++i)
V[0].push_back(V[2][i]);
sort(V[0].begin(),V[0].end(),cmp);
solve_2(V[1],V[0],0);
return;
}
if((int)V[2].size()==n/2){
for(int i=0;i<(int)V[1].size();++i)
V[0].push_back(V[1][i]);
sort(V[0].begin(),V[0].end(),cmp);
solve_2(V[2],V[0],0);
return;
}
int sum=V[0].size()+V[1].size()+V[2].size(),pr=-1;
while(1){
int nx=-1;
for(int i=0;i<3;++i)if(pr!=i&&!V[i].empty()){
if(nx==-1)nx=i;
else if(cmp(V[nx].back(),V[i].back()))nx=i;
}
assert(nx>-1&&!V[nx].empty());
ans.push_back(V[nx].back());
V[nx].pop_back();
--sum;
size_t mx=max(max(V[0].size(),V[1].size()),V[2].size());
if(sum==2*(int)mx){
int id=(V[0].size()==mx)?0:((V[1].size()==mx)?1:2);
VI a=V[id],b;
if(nx!=id){
int oth=0;
while(oth==nx||oth==id)++oth;
if(cmp(ans.back(),V[oth].back())){
ans.push_back(V[oth].back());
V[oth].pop_back();
}
}
for(int i=0;i<3;++i)if(i!=id)
for(int j=0;j<(int)V[i].size();++j)
b.push_back(V[i][j]);
sort(b.begin(),b.end(),cmp);
solve_2(a,b,nx==id);
return;
}
pr=nx;
}
}
VI createFunTour(int nn,int){
n=nn;
if(n==2)return VI({0,1});
for(int i=1;i<n;++i)sz[i]=attractionsBehind(0,i);
sz[0]=n;
for(int i=1;i<n;++i)
if(sz[i]<sz[rt]&&sz[i]>=(n+1)/2)rt=i;
for(int i=0;i<n;++i)if(i!=rt){
dep[i]=hoursRequired(rt,i);
if(dep[i]==1)sons.push_back(i);
}
assert((int)sons.size()>1);
for(int i=0;i<(int)sons.size();++i)id[i].push_back(sons[i]);
for(int i=0;i<n;++i)if(dep[i]>1){
int d1=hoursRequired(sons[0],i),d2=hoursRequired(sons[1],i);
if(d1+1==dep[i])id[0].push_back(i);
else if(d2+1==dep[i])id[1].push_back(i);
else id[2].push_back(i);
}
sort(id[0].begin(),id[0].end(),cmp);
sort(id[1].begin(),id[1].end(),cmp);
if(!id[2].empty())sort(id[2].begin(),id[2].end(),cmp);
if((int)sons.size()==2)solve_2(id[0],id[1],id[0].size()<id[1].size());
else solve_3(vector<VI>({id[0],id[1],id[2]}));
return ans;
}