【BZOJ3244】【NOI2013】树的计数（神仙题）

题面

这题有点假，(bzoj)上如果要交的话请输出(ans-0.001,ans,ans+0.001)

题解

数的形态和编号没有关系，因此对于(bfs)序重标号，同时修改一下(dfs)序方便做题。
因为(bfs)的层数等于树高，所以我们相当于要把(bfs)划分为若干段，
那么，每一种(bfs)划分显然要么不合法，要么对应一种树的形态。
那么，我们来考虑(bfs)划分的几个限制。
首先有一个很明显的限制：
如果划分了一段([L,R])，那么(dfn[L]<dfn[L+1]<...<dfn[R])
原因很简单，因为一个点的所有儿子对应的出现顺序在(bfs)和(dfs)序中相同
显然所有儿子都是从左往右遍历，因此这一项显然成立。
令(pos)为(dfs)序的反数组，
考虑(dfs)序中相邻的两个元素(x,x+1)。
显然要么是父子关系，要么是兄弟关系，要么(x+1)是(x)祖先的儿子。
所以可以列出不等式(dep[x+1]le dep[x]+1)
当然了，还有一个约束，根节点后面必须断开。

我们构建一个数组(s)，(s[i]=1)的话就表示(i)和(i+1)必须断开

归类一下，约束条件有三项：
1.根节点后面必须断开，而根节点一定是(bfs)序中的(1)
2.同一段([l,r])中的所有点满足(dfs)序递增，即如果(pos[i]>pos[i+1])，那么必须断开，也就是(s[i]=1)
3.如果(dfn[i]<dfn[i+1])，那么，(sum_{j=dfn[i]}^{dfn[i+1]-1} s[i]le 1)，这个式子在计算的时候需要满足(dfn[i]lt dfn[i+1])，而根据推导(dep[i+1]-dep[i]le 1)。

如果知道了(s)，那么(1+sum s[i])就是树高，也就是(bfs)序分开的段数。

考虑一下贡献是怎么产生的。
两个相邻的(bfs)序之间要么不能断开，贡献为(0)
要么必须断开，贡献为(1)
要么随意，贡献为(0.5)
只需要利用所有约束条件确定每个位置的贡献就好啦。
我是看得LCF学长的blog

#include<iostream>
#include<cstdio>
using namespace std;
#define RG register
#define MAX 222222
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
double ans;
int n,a[MAX],d[MAX],s[MAX];
int main()
{
	n=read();ans=1;s[1]=1;s[2]=-1;
	for(int i=1;i<=n;++i)a[d[i]=read()]=i;
	for(int i=1;i<=n;++i)d[a[read()]]=i;
	for(int i=1;i<=n;++i)a[d[i]]=i;
	for(int i=2;i<=n;++i)if(a[i]<a[i-1])s[i-1]++,s[i]--,++ans;
	for(int i=2;i<=n;++i)if(d[i-1]<d[i]-1)s[d[i-1]]++,s[d[i]]--;
	for(int i=1,t=0;i<n;++i)t+=s[i],ans+=(!t)?0.5:0;
	printf("%.3lf
",ans+1);
	return 0;
}