管道迷宫 题解

题目传送门

（团队题库，不可见，重题见 此处 ）

题外话

本来是去年一个有关树然后有个线上下扫的交互题今年把它实现出来。

结果后来还是算了，搞了一个物理学的东西，是准备用来当考试题的。

鬼晓得这玩意没一个人知道比暴力优的解法，我自己都不知道。

然后想到去年还有个想法，稍微改了一下，发现和网上某题重了。

实在懒得出新题目了重就重吧没人做过就行。

题目分析

题目长度适中偏长，符合 NOIP 题面长度套路，但是是真交互题，CCF 没考过。

简单来说，就是给一个以 $1$ 为根的有根树，然后有两种交互，一种查询两点距离，一种查询一个点的子树。要求用父亲表示法把树还原出来。

你看吧虽然题面很长但简化出来只有一句话，所以还是不符合 CCF 的出题习惯。

测试数据 1

不难看出这个数据就是一个菊花图。

注意了，这个菊花图的花蕊不一定是根节点，事实上数据也不是。只要你够细心就知道还有一种情况是花蕊的海拔是 $-1$，换句话说树高为 $3$。

就算你不知道这个花蕊是不是根节点，分类讨论总会吧。

一个简单的做法，枚举每个点和根节点的距离。如果除了根节点，所有点距离都是 $1$，说明是 $1$ 为花蕊的菊花，否则一定只有一个点距离为 $1$，别的都是 $2$。那个距离为 $1$ 的就是花蕊。

我才不会告诉你这个数据差点卡掉了 100 分的正解。

测试数据 2~5 （ 25 分暴力算法）

我摊牌了表格里我写的小于等于其实所有数据 n 都开到等于了。

所以没有必要讨论玄学骗分算法。

考虑到可询问次数大于 $n^2$，最简单的算法就是暴力枚举两个点，查询一下距离。如果距离是 $1$ 就说明是有边直接连接的。

因此暴力查询距离得到联通关系，相当于是知道这个树的边了，显然再跑一遍 dfs 就可以得出父子关系。

测试数据 6~8

不难得出这两个数据点都是说这个树是一条链。

链是个好东西，为什么？因为一个点只会有一个儿子啊。

询问次数卡到了大约是 $2n$ 的水平，可以考虑在上一组测试数据的基础上优化。

因为每一个深度都只有一个点，我们可以暴力询问每一个点和根节点的距离，这个时候可以发现深度为 $d$ 的点的父亲就是深度为 $d-1$ 的点的父亲（正如前文所述，不要忘记链的情况每个点深度互不相同！）。

知道了这一点就可以随便怎么搞了，我的做法是根据深度小到大排序。这里不必赘述。

测试数据 9~11

从这里开始我们将走向玄学和魔法的道路。

这里的特殊性质在暗示我们这两个点都是完全二叉树，至于完不完美，也不一定，除非你知道数据（数据都取了表格的最大值， $n=2000$ 当然不完美）。

就当它是个完全二叉树做。

前面的 $30$ 分都只用了查询距离的询问，现在来考虑查询子树。

查子树是非常麻烦的，因为一个点的子树大小未知，而查一次就要消耗子树大小那么多个询问次数。

虽然这样子一说显得这个操作很鸡肋，但是万事开头难。我们先舍弃那些询问限制，考虑怎么只查子树还原整个树。

既然这个东西一下子给你整出这么多信息点（既包含子树大小，也知道有哪些点），也一下子扣了那么多查询次数，显然我们要本着尽可能不要浪费信息点的方法来处理。

不妨不管三七二十一把能记录的记下来再说。

假设 $s_i$ 表示 $i$ 号节点的子树大小，然后用一个二维数组存下所有点的祖先（顺序随意），这道题 $n$ 最大也只有 $2333$，空间限制也不卡，显然二维数组不会炸空间。

为什么记祖先不记子树呢，因为根据本人习惯，想到一个节点父亲一定只有一个，儿子就不一定只有一个了，所以记祖先总会方便一些。

这两个信息都可以通过查子树得到，具体怎么处理也不难，大家自行尝试。

因为记录的是祖先节点，所以我们最好是从下往上地处理。显然子树大小为 $1$ 的肯定是叶子节点了。

明确了处理方向，具体怎么处理呢？

现在我们知道了一个叶子节点 $u$，以及他的所有祖先，以及所有点的子树大小。因为上面的点子树大小显然比下面的点大，所以在这个叶子的祖先里搜一遍，找到子树最小的点 $fa$，则 $fa$ 一定是 $u$ 的父亲。

每一个点都可以进行这样的操作，因为 $n$ 很小不会 TLE，所以到这里就可以结束了。

这个算法的复杂度是多少呢？

考虑到时间最坏也是 $n^2$ 打死都 T 不掉，如果事先按照子树大小 $s$ 排个序复杂度可能更低。因此重点来考虑一下询问次数。

因为我们是从下往上处理的，而且下面的节点处理完毕就再也没有管过了，可以假设这些点直接被删掉，那么这个点的祖先的子树大小全部要 $-1$。

如果我们事先按照子树大小排好了序，那么肯定是先把所有的叶子处理掉了。叶子处理掉然后呢？这个时候我们就发现，原本是叶子节点父亲的那些点就变成叶子了。然后再把这些新叶子处理掉，它们的父亲就变成新叶子了……

以此进行的操作是和子树大小的递减有关的。那么抽象地说，如果同一层的节点越多，那么这一层节点的叶子可能会越多（想象一下一个根节点为花蕊的菊花图，然后再想一个 $n$ 很大但是树高特别小的树你就大概理解了），处理的时候反而会越快。

那么理论而言，对于一个完全随机生成的树，他的理论复杂度是 $n\sqrt{n}$ 的；对于一个完全二叉树，大概估测一下他的复杂度是 $n\log n$ 的；因为它基于子树的减少，如果是一条链的情况，子树每次只会减少 $1$，这时会退化成 $n^2$ 的。

不过这个解法的复杂度对于完全二叉树而言还是很友善的，亲测可行。

测试数据 12~19（95 分根号分治算法）

我们来总结一下前面使用过的查询方法：

根据深度判断，这个操作只适用与链；
枚举两点距离。
查询点的子树，从下往上倒推。

先考虑前两个。

假设我首先查询出每个点的深度，可不可以优化“枚举两点距离”呢？

当然可以，如果你不知道它们的深度，枚举的范围总是 $n$ 的规模，但是如果我知道每个点的深度，显然两个深度隔了 $2$ 或以上的点不可能形成父子关系，所以每个点的枚举的范围缩减到了比他深一个单位的点的数量。

考虑第三个查询方法，如果我事先知道每个点的深度，然后还知道某个点的子树，那么这个点的子树中，深度刚好比这点深 $1$ 的点不就是它的儿子吗？

于是我们有两种查询方法：

无论如何，先求每个点和根节点的距离，得到深度，然后：

利用深度缩减枚举范围，枚举两点距离，距离为 $1$ 的形成父子关系。
查询一个点子树，结合深度确定父子关系，深度差刚好为 $1$ 的形成父子关系。

发现两种方法的利弊几乎是互补的：

第一种方法适合某一层的节点较少的情况，这样枚举范围较小；在链的情况下，查询复杂度为 $n$，在完全二叉树上，大概估测一下，几乎退化成 $n^2$，在随机数据上，期望查询为 $n\sqrt{n}$。

第二种方法适合某一层的节点较多的情况，这样期望的可以一步查询到位的点更多。在完全二叉树上，大概估测一下，可以达到 $n\log n$，在一条链上，复杂度几乎为 $n^2$，在随机数据上，期望查询为 $n\sqrt{n}$。

随便算一下，$n\sqrt{n}$，$n\log n$，$n$ 的查询次数的方法可以过。可惜数据不一定是随机生成，不然这两种都能过了。

注意到第一种方法适合一层节点少的情况，第二种方法适合节点多的情况……

不妨就基于骗分的思想，如果这一层节点少，就用第一种，如果比较多，就用第二种。

我们确定一个常数 $S$，如果这一层的点数大于（或大于等于）$S$，考虑第二种，如果这一层点数小于（或小于等于）$S$，考虑第一种。

当然这个 $S$ 不能乱取，不然还是很容易被卡掉 （事实上我貌似想不到怎么去卡）。还是确定一下 $S$ 的值保险。

下文的大于和小于可以取等，影响不大。

假设这一颗树有 $m$ 层，第 $i$ 层有 $a_i$ 个点，当前我们已经知道了第 $i$ 层，准备查找第 $i+1$ 层。进行分类讨论：

• $a_i>S$

显然对于这一层的所有节点，我都查询一次子树，再根据深度判断下一层的点与这一层的父子关系。显然任何一层消耗的总操作量 $\leqslant n$。

而 $a_i>S$ 的情况最多也只会有 $n/S$ 次，每次输出不超过 $n$。因此总次数为（实则一定不超过） $n^2/S$。

• $a_i<S$

此时对于这一层我们使用的是第一种操作，对于每一个这一层的点，需要循环一遍下一层的所有点来查距离，消耗的总操作数是 $a_i \times a_{i+1}$。

因为这次分类讨论我们同时处理的两层的数量关系，所以这种情况出现的次数不是 $n/a_i$，而是 $\dfrac{n}{a_i+a_{i+1}}$ 的。

那么这种情况总的查询数是：$a_i \times a_{i+1} \times \dfrac{n}{a_i+a_{i+1}}$。

显然 $a_i+a_{i+1}>a_{i+1}$，即使真的有 $a_i+a_{i+1}=a_{i+1}$，那么原式就会变为 $a_i \times n$，既然显然这两者不可能相等，那么原式一定会小于 $a_i \times n$。

而如前面所提，$a_i<S$，因此会有：

原式 $< a_i\times n < nS$，因此原式无论如何需要的操作次数都不会比 $nS$ 还要多。

综上，两种情况总结起来，总的查询次数是一定会小于这个值的：

$n^2/S+nS$

这个式子看起来非常的恶心，实际上则不然，如果你还记得均值不等式：

$a+b\geqslant 2\sqrt{ab}$

且当且仅当 $a=b$ 时原式取等号。

那么我们将 $a=n^2/S, b=nS$ 带入原式：

$n^2/S+nS\geqslant 2\sqrt{\frac{n^2}{S}\times nS}$

不等号右侧合并，化为最简根式：

$n^2/S + nS \geqslant 2n\sqrt{n}$

这个式子当且仅当 $n^2/S=nS$ 时，取等号，也就岁复杂度为最小值。

$\frac{n^2}{S}=nS$

$\therefore S^2=n$

$\therefore S=\sqrt{n}$

综上所述，我们得出了一个很厉害的结论：当 $S=\sqrt{n}$ 的时候，有最小的询问次数。因为证明中得到的那个式子两个加数都取不到，所以询问次数一定是小于 $2n\sqrt{n}$ 的。

实际上，大约也就是 $n\sqrt{n}$ 的水平，刚好可以过。

事实上，出题人还算比较仁慈，第 $12$ 个数据点是专门给 $S=n/2$ 设计的，第 $13$ 个数据点是专门给 $S=\log_2 n$ 设计的。毕竟不是所有人考场都能想到 $S=\sqrt{n}$ 最优。

测试数据 20 ( 100 分随机化算法）

因为 $n\leqslant 2333$，只要时间复杂度是 $n^2$ 我们都可以瞎搞（甚至好像还能带个 $\log$）。因此仍然只考虑查询次数是否超限。

考虑前面所提到的：对于两个点 $u,v$，如果 $v$ 在 $u$ 的子树中，且 $u,v$ 深度关系满足 $dep_u+1=dep_v$ （方便起见不使用原题的海拔代表深度，直接从上到下从 $1$ 开始标）。

首先每一个点的 $dep$ 显然还是要做的。如果我们朴素地从上到下递归查询子树，判断深度，复杂度是达到 $n^2$ 级别的，梦回暴力 $25$ 分。

这一步如何优化呢？

考虑如果我知道一个点 $u$，它有一个儿子 $v$，如果我知道 $u$ 的子树，还知道 $u$ 的其他儿子的子树，那么直接相减就得到了 $v$ 节点的子树。

这样子我们对于每一个点至少可以少查一个儿子的子树了。

少查的这个子树给哪个点最好呢？当然是子树最多的那个点。是不是感觉非常想树链剖分找重儿子？如果我们可以保证每次选择的是重儿子，根据树剖和 dsu on tree （树上启发式合并）里的推论，可以估测出查询的数量级略小于 $n\log n$。

那么问题来了，我要求的不久是树的结构吗，连树的结构都不知道怎么剖呢？

这个时候我们开始玄学：随机。

如果一个点的子树最大，那么如果我随机若干个点作为标记点，这个点的子树中就会有期望更多的标记点。这个时候我们令占标记点最多的点为重儿子。

那么应该随机几个呢？最好还是简单为好，为了避免两个点所占的标记点一样多导致冲突，直接只随机一个点就可以了。

这样子的算法非常玄学。但是其复杂度退化的原因就在于我随机的时候并没有找到重儿子。实际测试的时候发现即使我找到的点大部分都是轻儿子，复杂度的退化也并不明显。

再者，如果要卡掉这种随机算法，要从两个方面考虑：一个是加多轻儿子数量，另一个就是让其因为找到轻儿子复杂度退化更加明显。

选择加多轻儿子数量，可以众生平等开完美多叉树，但这样又可以视为每个点都是重儿子，而且如果一个点的儿子个数 $>2$ ，复杂度甚至会比 $\log_2 n $ 还要小。就算开的是完美二叉树，他的复杂度也是 $\log_2 n$ 的。显然轻儿子数量越多，重儿子和轻儿子的子树大小差值也会变小，整体效率还是非常可观的。

那么还有一个方法就是让找到轻儿子复杂度的退化加剧，这样做就只能不断加大重儿子的子树大小，让其拉开和轻儿子子树大小的差距。实际上如果重儿子子树大小和轻儿子差距越大，那么每一次随机点我找到重儿子的概率也会越大。考虑到 $n$ 虽然不大，但是也不是很小，可以估算找到重儿子的次数是非常可观的。

于是我们大概口糊了一下算法的正确性，交上去是可以 AC 的。

现在来感性理解一下随机算法：

假设对于一个点 $u$，我们记 $h_u$ （ heavy son ，重儿子 ）为这个点的重儿子，其他的所有点（ 轻儿子 ）记为 $l_u$ （ light son ）。

如果我们颠倒了一个点的轻重儿子，相当于这一次少查了个重儿子多查了个轻儿子。对于这个点的询问次数，将会乘上一个 $\dfrac{size_{h_u}}{size_{l_u}}$。

假设我们有 $p$ 的概率颠倒，则对于一个点 $u$，设最优情况下他的询问次数为 $t$ ，则他期望的询问次数为：

$t \times [(1-p)+p \times \frac{size_{h_u}}{size_{l_u}}]$

假设 $t$ 后面那一个式子记为 $E$，那么期望次数为：

$Et$

考虑树链剖分还带一个小于 $\log n$ 的处理，总的询问次数就是：

$En\log n$

考虑求 $E$ 的最大值。直接打个表求出近似值：

#include<bits/stdc++.h>
using namespace std;

int x,y,t;

//x表示重子树大小，y表示轻子树大小，t表示随机标记点数 

double f[505][505],ans;
int book[505][505];// f 和 book 是记忆化，虽然是打表但还是要追求效率

double dfs(int nowx,int nowy){ //记忆化搜索求解子树颠倒的概率 
	if (nowx+nowy==t){
		if (nowx<=nowy)return 1.0;
		if (nowx==nowy)return 0.5; 
		return 0.0;
	}
	if (book[nowx][nowy])return f[nowx][nowy];
	double ans=1.0*x/(x+y)*dfs(nowx+1,nowy)+1.0*y/(x+y)*dfs(nowx,nowy+1);
	book[nowx][nowy]=1;
	return f[nowx][nowy]=ans;
}
inline int gcd(register int a,register int b){
	if (b==0)return a;
	return gcd(b,a%b);
}
int main(){
	for (register int i=1;i<=500;i++)
	    for (register int j=1;j<i;j++){//枚举不同重或轻子树大小的比值 
		   if (gcd(i,j)!=1)continue; // 如果可以约分直接省略，因为前面肯定循环过了
		    x=i,y=j,t=1; 
		    memset(book,0,sizeof(book));
		    double now=dfs(0,0);
		    ans=max(ans,1.0-now+now*i/j);//计算E的最大值 
	    }
	printf("%.9lf\n",ans);// 求出的近似值，并不一定精确，但是9位小数已经足够了
	return 0;
}

当然这个代码除了可以求随机一个点的 $max_E$，通过调试不同的 $t$，可以求出随机不同的点的 $max_E$。

$t=1$ 的时候， $E$ 的最大值约为 $1.996007984$。当然如果不嫌麻烦我们再求一下其他情况。

可以发现在实验范围内， $t=9$ 的时候是最优的。进一步探究发现，将 $t$ 为奇数的情况记下来，是递减的；将偶数的情况记下来，也是递减的。

那么前面我们为了方便直接去 $t=1$，复杂度是多少呢？

这样算下来 $E\approx 2$，原复杂度可以视为是 $2n\log n$ 的，这个算法看起来可能会被 T 飞，但是实际上也是比较优秀的。

把打表代码改一下，输出中间值，可以发现，如果轻重儿子子树大小的比值 $\dfrac{size_{h_u}}{size_{l_u}}$ 越大，$E$ 的值也会越大。

但是这样下去树也会越来越不平衡，对于一个不平衡的树，根据 OI wiki，树上启发式合并（ dsu on tree ）的常数减小也会显著。

另外一方面，树越来越不平衡，颠倒轻重儿子的概率 $p$ 也会变小，树链剖分常数也会变小，整体复杂度反而下降了。

因为随机乱搞的算法还是比较恶心，本来是占了 $30$ 分的（即根号分治 $70$ 分，随机化 $100$ 分），改成 $5$ 分了（即根号分治 $95$ 分，随机化 $100$ 分）。