[BZOJ3244][Noi2013]树的计数（乱搞？？？）

In Luogu ，好像是第一道会做的黑题。

Address

https://www.lydsy.com/JudgeOnline/problem.php?id=3244

Solution

首先， 1$1$ 号节点当然是根节点。
BFS 实际上是树的按层遍历。
考虑对 BFS 序列进行分层。
对于 BFS 序相邻的两个点 u,v$u,v$ ，如果 u$u$ 的 DFS 序大于 v$v$ 的 DFS 序，那么它们之间一定要分层。
按照这样的方式分层，就能得到最小深度 Dmin$D_{min}$ 。
但这样就能唯一确定一棵树吗？答案是否定的。
就样例来说：

这里的 4$4$ 和 5$5$ 可以分层，也可以不分层。
而对于 BFS 序里的一段区间（这段区间对应的 DFS 序递增），如果它们在 DFS 序列中满足这样的排列方法：

绿色为已经讨论过（深度比当前讨论的 BFS 序区间要小）的点，红色为当前讨论的点，灰色为知道现在还未讨论的点。
稍微分析一下， DFS 序递增的 BFS 区间内部可以分层的条件是：
有 m 个子树（上图的非绿子段），前 m-1 个子树都被填满，如果最后一个子树（上图的最后 6 格），如果前 k 个红色格子连续排列（上图中的倒数第 4 、 3个红色格子），那么这个 BFS 区间最少分 1 层，最多分 k 层。
分 k$k$ 层的情况就是指这 k$k$ 个红色格子对应的节点一个点分一层。
于是，树的最大深度 Dmax$D_{max}$ 也求出了。
根据上面的推导，我们得出树深度的分布是比较均匀的。
所以答案是：

Dmin+Dmax2$$\frac{D_{min}+D_{max}}{2}$$

Code

丧病的 BZOJ 要求输出 ans-0.001 、 ans 、 ans+0.001 三个数。
下面给出标准的、只输出最后结果的程序代码；

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
using namespace std;
const int N = 2e5 + 5; int n, dfs[N], bfs[N], pos[N]; double ans; bool vis[N];
int main() {
    int i, orz = 2; cin >> n; For (i, 1, n) scanf("%d", &dfs[i]), pos[dfs[i]] = i;
    For (i, 1, n) scanf("%d", &bfs[i]); vis[1] = 1; while (orz <= n) {
        int lst = orz, tmp = orz;
        while (orz < n && pos[bfs[orz]] < pos[bfs[orz + 1]]) {
            orz++; if (pos[bfs[orz - 1]] + 1 != pos[bfs[orz]] &&
                vis[pos[bfs[orz]] - 1]) lst = orz;
        }
        orz = tmp; bool able = 1; while (orz < lst) {
            orz++; if (pos[bfs[orz - 1]] + 1 != pos[bfs[orz]] &&
                !vis[pos[bfs[orz - 1]] + 1]) able = 0;
        }
        if (!able) ans += 1; else {
            orz = lst; int cnt = 1; if (pos[bfs[orz]] + 1 == pos[bfs[orz + 1]])
            while (orz < n && pos[bfs[orz]] < pos[bfs[orz + 1]]) {
                orz++; if (pos[bfs[orz - 1]] + 1 != pos[bfs[orz]])
                    break; cnt++;
            }
            ans += (1.0 * cnt + 1.0) / 2;
        }
        orz = tmp; vis[pos[bfs[orz]]] = 1;
        while (orz < n && pos[bfs[orz]] < pos[bfs[orz + 1]])
            orz++, vis[pos[bfs[orz]]] = 1; orz++;
    }
    printf("%.3lf\n", ans + 1); return 0;
}