「LOJ 2665」「NOI2013」树的计数

发表于

我们知道一棵有根树可以进行深度优先遍历（DFS）以及广度优先遍历（BFS）来生成这棵树的 DFS 序以及 BFS 序。两棵不同的树的 DFS 序有可能相同，并且它们的 BFS 序也有可能相同。

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

h1+h2+⋯+hKK\frac{h_1+h_2+\cdots +h_K}{K}

Constraints

2≤n≤2000002 \leq n \leq 200000

Solution

编号对结果没有影响，我们可以将 BFS 序改成 1,2,⋯n1,2,\cdots n 并对应地修改 DFS 序。

然后我们可以观察到一个结论：如果编号为 ii 的节点在 DFS 序中位置大于 i+1i+1 号点，则 ii 与 i+1i+1 一定分层。

因为在 DFS 序中，对于相邻的点对 (x,y)(x,y) ， deepydeep_y 的深度一定不大于 deepx+1deep_x+1 ，所以要限制在 BFS 序中分层的时候，区间 [x,y][x,y] 的分层数不能超过 11 。可以根据 BFS 序中的位置判断 xx 是否是 yy 的父亲，若是，则他们之间一定会强制分层，用差分来限制区间内的点对不可分层。

对于没有限制的点对 (i,i+1)(i,i+1) ，对答案的贡献为 0.50.5 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=2e5+5;
int n,sum,ans=2;
int dfn[N],bfn[N],pos[N];
int f[N],cnt[N];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)dfn[i]=read();
	for(int i=1;i<=n;i++)bfn[i]=read();
	for(int i=1;i<=n;i++)pos[bfn[i]]=i;
	for(int i=1;i<=n;i++)dfn[i]=pos[dfn[i]];
	for(int i=1;i<=n;i++)pos[dfn[i]]=i;
	f[1]=1;
	for(int i=1;i<n;i++)
		if(pos[i]>pos[i+1])f[i]=1;
	for(int i=2;i<=n;i++)f[i]+=f[i-1];
	for(int i=1;i<n;i++)
	{
		int x=dfn[i],y=dfn[i+1];
		if(x>=y)continue;
		y--;if(f[y]-f[x-1])cnt[x]++,cnt[y+1]--;
	}
	for(int i=n;i>=1;i--)f[i]-=f[i-1];
	for(int i=1;i<n;i++)
	{
		sum+=cnt[i];
		if(!sum&&!f[i])f[i]=2;
	}
	for(int i=1;i<=n;i++)
		if(f[i]==1)ans+=2;
		else if(f[i])ans++;
	printf("%.3lf\n",ans/2.0);
	return 0;
}