【题解】[NOI2013] 树的计数

题目链接：[NOI2013] 树的计数

题意：

给定长度为 $n$ 的排列 $\{d_n\},\{b_n\}$，他们分别是一棵有根树的 $\text{DFS}$ 序和 $\text{BFS}$ 序（儿子有顺序）。
求所有满足上述 $\text{DFS}$ 序和 $\text{BFS}$ 序的树的深度的平均值。
$1\le n\le 2\times 10^5$。

看到 $\text{BFS}$ 序，自然想到按照 $\text{BFS}$ 序来分段。把 $b,d$ 按照 $\text{BFS}$ 序重新编号，即使得 $b_i=i$，$d_i$ 相应变化。

观察一下有了 $\text{DFS}$ 序和 $\text{BFS}$ 序后，每个节点的深度 $\text{dep}_i$ 需要满足什么限制。

• 根据 $\text{BFS}$ 序的限制，$\text{dep}_{b_i}\le \text{dep}_{b_{i+1}}$ 。
• 根据 $\text{DFS}$ 序的限制，$\text{dep}_{d_{i+1}}\le \text{dep}_{d_i}+1$ 。这是因为 $d_{i+1}$ 一定是 $d_i$ 到根之间的链上的某个节点的儿子。

发现需要计算的是深度，而深度恰好等于 $\text{BFS}$ 序中 $\text{dep}$ 相同取值的段数 $+1$。求平均数等价于求合法的树的深度的期望，根据期望的线性性，可以将每个点作为分段点的概率分开考虑。

考虑 $i$ 与 $i+1$ 之间什么时候一定会分段。

首先，$1$ 后面必定会分段（根只有一个）；若 $i,i+1$ 同深度，那么 $\text{DFS}$ 序中 $i$ 在 $i+1$ 前面。因此，$\text{DFS}$ 序中若 $i$ 在 $i+1$ 后面，则 $i$ 后一定要分段。

再考虑什么情况下 $i,i+1$ 之间不能分段。根据 $\text{dep}_{d_{i+1}}\le \text{dep}_{d_i}+1$，我们可以得到：当 $d_i<d_{i+1}$，则 $[d_i,d_{i+1})$ 之间至多一个分段点。

这是因为，当 $d_i<d_{i+1}$，就说明了 $\text{dep}_{d_i}\le \text{dep}_{d_{i+1}}$，又有 $\text{dep}_{d_{i+1}}\le \text{dep}_{d_i}+1$，所以 $\text{dep}_{d_i}\le \text{dep}_{d_{i+1}}\le \text{dep}_{d_i}+1$。

那么若 $[d_i,d_{i+1})$ 之间，有一个必须分段的点，那么区间中剩下的点都不能作为分段点了。

因此，可以通过差分的方法，求出每一个点是否能作为分段点。

• 若一个点必须成为分段点，则对答案的贡献为 $1$。
• 若一个点没有被限制，则可以是分段点，也可以不是。由于每个点是否分段独立，所以贡献是 $0.5$。
• 若一个点不能分段，则贡献为 $0$。

时间复杂度 $\mathcal{O}(n)$。

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

//#define FILE
//#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'

const int MAXN = 2e5 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int n, m;
int d[MAXN], b[MAXN], ib[MAXN], pos[MAXN];
int cut[MAXN], cover[MAXN];
double Ans = 1;

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}

signed main () {
#ifdef FILE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    read(n);
    for(int i = 1; i <= n; ++i) read(d[i]);
    for(int i = 1; i <= n; ++i) read(b[i]), ib[b[i]] = i;
    for(int i = 1; i <= n; ++i) d[i] = ib[d[i]], b[i] = ib[b[i]], pos[d[i]] = i;
    for(int i = 1; i < n; ++i) cut[i] = cut[i - 1] + (pos[i] > pos[i + 1] || i == 1);
    for(int i = 1; i < n; ++i) {
        if(d[i] < d[i + 1] && cut[d[i + 1] - 1] - cut[d[i] - 1] > 0) {
            if(cut[d[i + 1] - 1] - cut[d[i] - 1] > 1) return puts("0.000"), 0;
            cover[d[i]]++, cover[d[i + 1]]--;
        }
        if(cut[d[i + 1] - 1] - cut[d[i] - 1] == 0) assert(d[i + 1] == d[i] + 1);
    }
    for(int i = 1; i < n; ++i) {
        cover[i] += cover[i - 1];
        if(!cover[i]) Ans += 0.5;
        else if(cut[i] - cut[i - 1]) Ans += 1;
    }
    printf("%.3lf\n", Ans);
    return 0;
}