[数学记录]P1232 树的计数

题意：

给出一棵树的 dfs 序和 bfs 序，求所有可能的原树的高度平均值

\(n \leq 2 \cdot 10^5\)

首先把 bfs 序变成 \(1 \to n\)，这样就需要把原树上的节点分成若干层。

设 \(pos_{dfn_i}=i\)，\(dfn\) 数组存点性质，\(pos\) 数组存点编号。

注意到每个节点是否分层对答案的贡献独立，单独求出每个节点是否能分层即可。

首先处理分层对 dfs 序的限制：当 \(dfn_x > dfn_{x+1}\) 时，\(x\) 与 \(x+1\) 间必须分层。

现在研究一棵树的 dfs 序应该满足什么条件。

思考做 dfs 的过程，每一步可以回溯或进入一个子节点。

借张图，图源 link

dfs 的每一步可以回溯或往下走到子节点。因为有换层出现，\(3\) 中的换层已经被计算，现在要把 \(3\) 筛选出来。

第一种情况 \(pos_y = pos_x+1\)，第二种情况 \(pos_y < pox_x\)，所以当 \(pos_y>pos_x+1\) 时一定属于第三种情况。

因此获得了两个限制：\(dfn_x > dfn_{x+1}\) 时 \(x\) 必须分层，\(pos_y>pos_x+1\) 时 \(x\) 与 \(y\) 之间不能再分层。

#include <cstdio>
using namespace std;
const int M = 2e5 + 5;
int read(){
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
int n, bfs[M], pos[M], dfs[M], dif[M], dfn[M];
void solve(int l, int r) {++dif[l]; --dif[r+1];}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) dfn[read()] = i;
    for(int i = 1; i <= n; i++) pos[dfn[read()]] = i;
    for(int i = 1; i <= n; i++) dfn[pos[i]] = i;
    solve(1, 1);
    double ans = 1;
    for(int i = 1; i < n; i++) {
        if(pos[i] < pos[i+1] - 1) solve(pos[i], pos[i+1] - 1);
        if(dfn[i] > dfn[i+1]) ++ans, solve(i, i);
    }
    int t = 0;
    for(int i = 1; i < n; i++) {
        t += dif[i];
        ans += t ? 0 : 0.5;
    }
    printf("%.3lf\n", ans+1);
}