题目：https://www.luogu.com.cn/problem/P1232

思路

根据树的bfs序的性质，可以通过将bfs序分段的方式，每一段代表着这个深度包含的节点，那么所分的段数就是这棵树的深度。

接下来考虑每一个位置是否可分段，共三种情况：

1.必须分。那么这个点对树高的贡献为1。

2.可分可不分，那么这个点对树高的贡献值为0.5（取1和0中间值）。

3.不能分。那么这个点对树高的贡献为0.

分层方法(orz)

1.根据bfs的性质，dfs序中对同一深度中的点的遍历顺序与bfs中顺序相同。所以当两个相邻点dfn[i]>dfn[i+1]，那么i点符合上述条件1；

2.根据dfs的性质(dfs寻找下一个点时要么深度+1要么深度不变要么深度-不知道多少),所以当dfn[i+1]>dfn[i]+1时，i点与i+1点之间的点必须全部符合条件3；

（explanation：设i与i+1点满足这三种条件：1.i和i+1是兄弟（ii没有儿子）;2.i+1是i的祖先的某个儿子（i没有儿子）;3.i+1是i的儿子;第1种达成d[i]>d[i+1],筛掉；第2种达成d[i]+1=d[i+1]，那么这两个点关系是父子还是兄弟都无所谓，筛掉;第3种bfs序上d[i]到d[i+1]之间最多只能切一次段，因为根据dfs性质，i和i+1之间只差一层，而且切这一段的贡献已经在分层时中被算过了，于是d[i]到d[i+1]中所有的点的总贡献必须为0）

3.不被上述2条约束的所有点都是可分可不分，按照贡献为0.5处理。

4.根节点（1号点）必须满足条件1.

最后把所有点的贡献值加起来就ok辣

#include<cstdio>
using namespace std;
long long n,bfs[200001],dfs[200001],bfn[200001],dfn[200001],num[200001];
double ans;
signed main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&dfs[i]);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&bfs[i]);
		bfn[bfs[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		dfs[i]=bfn[dfs[i]];
		dfn[dfs[i]]=i;
	}
	for(int i=2;i<=n-1;i++)
	{
		if(dfn[i]>dfn[i+1])
		{
			ans++;
			num[i]++;
			num[i+1]--;
		}
		if(dfs[i]+1<dfs[i+1])
		{
			num[dfs[i]]++;
			num[dfs[i+1]]--;
		}
	}
	for(int i=3;i<=n;i++) num[i]+=num[i-1];
	for(int i=2;i<=n-1;i++) if(!num[i]) ans+=0.5;
	printf("%.3lf\n",ans+2);
	return 0;
}