洛谷P1232 [NOI2013] 树的计数题解

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

题意：

我们知道一棵有根树可以进行深度优先遍历（DFS）以及广度优先遍历（BFS）来生成这棵树的 DFS 序以及 BFS 序。两棵不同的树的 DFS 序有可能相同，并且它们的 BFS 序也有可能相同，例如下面两棵树的 DFS 序都是 1 2 4 5 3，BFS 序都是 1 2 3 4 5。

现给定一个 DFS 序和 BFS 序，我们想要知道，符合条件的有根树中，树的高度的平均值。即，假如共有 $K$ 棵不同的有根树具有这组 DFS 序和 BFS 序，且他们的高度分别是 $h_1, h_2, \ldots, h_K$，那么请你输出：
$\frac{h_1+h_2+\ldots+h_K}K$
输入格式：

第一行包含 $1$ 个正整数 $n$，表示树的节点个数。

第二行包含 $n$ 个正整数，是一个 $1 \ldots n$ 的排列，表示树的 DFS 序。

第三行包含 $n$ 个正整数，是一个 $1 \ldots n$ 的排列，表示树的 BFS 序。

输入保证至少存在一棵树符合给定的两个序列。

输出格式：

输出 $1$ 个实数，四舍五入保留恰好三位小数，表示树高的平均值。

数据范围：

对于 $100\%$ 的测试数据，满足：$2 \le n \le 2 \times 10^5$。

考虑对 $\mathtt{BFS}$ 序进行分段。

但题目直接给了个 $\mathtt{DFS}$ 序和 $\mathtt{BFS}$ 序着实不太好做，考虑结点按 $\mathtt{BFS}$ 序重新编号。

此时的 $\mathtt{dfn[]}$ 数组就表示 $\mathtt{BFS}$ 序为 $1,2,\cdots,n$ 时的 $\mathtt{DFS}$ 序。

并且显然有 $\mathtt{bfn[i]=i}$ ，因此我们不需要这个 $\mathtt{bfn[]}$ 了。

我们可以用下面的代码来实现这个转换（下文的结点编号默认为转换后的编号。）

for(int i=1,x; i<=n; i++) { cin >> x; dfn[x] = i; } // 这里临时用于标号
for(int i=1,x; i<=n; i++) { cin >> x; id[dfn[x]] = i; }
for(int i=1; i<=n; i++) dfn[id[i]] = i; // 转换完成

考虑 $\mathtt{BFS}$ 序下连续的两点（即 $i,i+1$ ）什么时候一定分段

首先 $1$ 肯定要分段，因为根结点只有一个。

若 $\mathtt{dep[i] = dep[i+1]}$，则

$\mathtt{dfn[i] + 1= dfn[i+1]} \Rightarrow \mathtt{dfn[i] < dfn[i+1]}$

因此若 $\mathtt{dfn[i] > dfn[i+1]}$ ，$i$ 后一定要分段。（ $\mathtt{dfn[i]}$ 不可能等于 $\mathtt{dfn[i+1]}$ ）

注意到 $\mathtt{dep[i]=dep[i+1]}$ 时， $i$ 与 $i+1$ 在 $\mathtt{DFS}$ 序中也是连续的。

接着考虑对 $\mathtt{DFS}$ 序连续的两点进行讨论，考虑他们在 $\mathtt{BFS}$ 序下的关系

设点 $i,j$ 在 $\mathtt{DFS}$ 序下连续，即 $\mathtt{dfn[i] + 1 =dfn[j]}$ 。

当 $i = j-1$ 时，我们无法确定 $i$ 是否需要分层。

因为 $j$ 可能是 $i$ 的儿子，也可能是 $i$ 的后继兄弟。
当 $i > j-1$ 时，$j$ 一定是 $i$ 的某个祖先的后继兄弟
当 $i < j-1$ 时，$j$ 一定是 $i$ 的第一个儿子。

此时，区间 $[i,j-1]$ 一定存在一个分段点

考虑下图（注意 $i+1,j-2$ 这种不一定存在，只是画了一下）

考虑用差分维护每个点能否作为分段点

若一个点必须成为分段点，则对答案的贡献为 $1$ 。
若一个点不能被分段，则对答案的贡献为 $0$ 。
若一个点没有限制，由于每个点是否分段是相互独立的，所以贡献为 $\frac{1}{2}$ 。

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

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5+15))

int n,id[N],dfn[N],sum[N];
void put(int l,int r) { ++sum[l]; --sum[r+1]; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; double ans = 1; put(1,1); // 根节点要分一段
    for(int i=1,x; i<=n; i++) { cin >> x; dfn[x] = i; }
    for(int i=1,x; i<=n; i++) { cin >> x; id[dfn[x]] = i; }
    for(int i=1; i<=n; i++) dfn[id[i]] = i;
    for(int i=1; i<n; i++)
    {
        if(dfn[i] > dfn[i+1]) { ++ans, put(i,i); } // 这里也要标记，去掉0.5的贡献
        if(id[i] < id[i+1] - 1) put(id[i], id[i+1]-1); // 标记，在后面计算0.5的贡献
    }
    for(int i=1; i<n; i++) { ans += (sum[i] += sum[i-1]) ? 0 : 0.5; }
    cout << fixed << setprecision(3) << ans + 1 << '\n';
    return 0;
}