这题妙蛙
首先考虑构造出一个合法的树.先重新编号,把bfs序整成\(1,2,3...n\),然后bfs序就是按照从上到下从左往右的遍历顺序,所以可以考虑对bfs序分层,可以知道分层方式只会对应一棵树.按照\(2\to n\)的顺序枚举,如果这个点在dfs序中的位置小于上一个,那么这个点必须放在下一层.这样构造是正确的(如果有合法的树),并且构造出来的树高度最小
然后考虑能不能构造其他的树.手玩可以发现,如果某个点\(i\)满足以下条件,那么就可以把它以及这一层后面的点的父亲改成\(i-1\)
这个点不是其父亲第一个儿子,并且这个点在这一层后面的点父亲都和他相同
这个点在这一层前面所有点都没有儿子
如果一个点操作了,那么树高会\(+1\).现在要求平均值,可以发现如果有\(m\)个这样的点,平均值就是最小深度\(+0.5m\),然后找出所有这样的点即可得解
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define il inline
using namespace std;
const int N=2e5+10;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,a[N],b[N],p[N],q[N][2],sn[N],fa[N],de=1,ans;
int main()
{
n=rd();
for(int i=1;i<=n;++i) a[i]=rd();
for(int i=1;i<=n;++i) b[rd()]=i;
for(int i=1;i<=n;++i) a[i]=b[a[i]],p[a[i]]=i;
p[1]=n+3,q[1][0]=q[1][1]=1;
for(int i=2,j=0;i<=n;++i)
{
if(p[i]<p[i-1]) j=q[de][0],++de,q[de][0]=i;
b[i]=de,q[de][1]=i;
while(j<q[de-1][1]&&p[j+1]<p[i]) ++j;
fa[i]=j,++sn[j];
}
ans=de<<1;
for(int i=2;i<=de;++i)
{
int l=q[i][1],r=q[i][1],cn=0;
while(l>q[i][0]&&fa[l-1]==fa[r]) --l;
++l;
for(int j=q[i][0];j<l;++j) cn+=sn[j];
while(!cn&&l<=r)
{
++ans;
cn+=sn[l],++l;
}
}
printf("%d.%d00\n",ans>>1,5*(ans&1));
return 0;
}