Description

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



现给定一个DFS序和BFS序，我们想要知道，符合条件的有根树中，树的高度的平均值。即，假如共有K棵不同的有根树具有这组DFS序和BFS序，且他们的高度分别是h1,h2,...,hk，那么请你输出

(h1+h2..+hk)/k

Solution

用期望的线性性拆成点对的贡献

我们发现如果点对 \((x,y)\) 必须处在不同层,那么期望 \(+1\),必须在相同层则没有贡献

如果不确定是否在同层,则为 \(0.5\)

现在只需要把点分类即可:

1.如果两个点在 \(bfs\) 序中相邻, \(bfs[a]<bfs[b]\),且满足 \(dfs[a]>dfs[b]\),那么就必须不同层

2.如果两个点在 \(dfs\) 序中相邻, \(dfs[a]<dfs[b]\),且满足 \(bfs[a]<bfs[b]\),代表这两个点的深度差不超过 \(1\),就意味着 \(bfs\) 序中,\(a\) 到 \(b\) 之间的点必须同层

考虑怎么满足这些约束:

条件 \(1\) 比较好判断,对于条件 \(2\) ,当一个点对确定深度差不超过一时,在 \(bfs\) 序中这两个点的中间一段必须同层,贡献已经确定是 \(0\),我们把中间的点打上一个标记,表示已经确定了贡献,可以用差分实现

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10;

int n,a[N],w[N],p[N],s[N],c[N],t[N],b[N];

int main(){

  int x;

  scanf("%d",&n);

  for(int i=1;i<=n;i++)scanf("%d",&x),p[x]=i;

  for(int i=1;i<=n;i++)scanf("%d",&x),a[p[x]]=i,b[i]=p[x];

  t[1]++;c[1]++;c[2]--;

  for(int i=2;i<=n;i++)if(b[i]>b[i+1])t[i]++,c[i]++,c[i+1]--;

  for(int i=1;i<=n;i++)s[i]=s[i-1]+t[i];

  for(int i=1;i<=n;i++)if(a[i]<a[i+1] && s[a[i+1]-1]-s[a[i]-1])c[a[i]]++,c[a[i+1]]--;

  double ans=0;

  for(int i=1;i<=n;i++){

      c[i]+=c[i-1];

      if(c[i])ans+=t[i];

      else ans+=0.5;

  }

  printf("%.3lf\n",ans);

  return 0;

}