不妨令 dfs 所遍历的节点依次为 $0\sim n-1$。

我们把根节点忽略，考虑剩下的部分，通过给 bfs 序分层来确定树的形态，则每层一定顺次对应于上一层各个节点的儿子，因此一定编号递增。

我们考虑把序列按值域上升段分层。显然被分开来的一定属于不同层。

对一个节点，比其小的在后面未出现过的元素中最大的一个必然出现在同一层或上一层。

如果那个元素和自己还不相邻，则说明自己和该层左边的所有元素确实位于同一层，上一层对应元素和右侧元素属于同一层。取出最大最小的限制元素即可判断。

如果相邻，则在不在同一层均可。

这样，最后图上有若干相邻点「必须在同一层」，若干相邻点「必须在不同层」，若干相邻点「可以在同一层或相邻层」。

最小层数和最大层数的平均数，显然就是答案。

参考代码。

然后！最后！注意 bzoj 上要分三行输出 $\tt ans - 0.001$，$\tt ans$，和 $\tt ans + 0.001$。