【题解】[NOI2013] 树的计数

CXY07 · 2021-08-20 22:12:55 · 题解

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

本题解同步发布于 My Blog

题意：

给定长度为 n 的排列 \{d_n\},\{b_n\}，他们分别是一棵有根树的 \text{DFS} 序和 \text{BFS} 序（儿子有顺序）。

求所有满足上述 \text{DFS} 序和 \text{BFS} 序的树的深度的平均值。

看到 \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;
}