洛谷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;
}