BZOJ3244: [Noi2013]树的计数

这题其实我还不是很懂为什么满足了这两个性质就一定合法qaq

先将所有点按其bfs序重新标号
我们令dfn[i]表示i的dfs序，bfn[i]表示dfs序为i的点的bfs序
考虑怎么计算答案，我们令dep[i]表示点i所在树中的层数，那么对dep[i]做个差分，a[i]=a[i]-a[i-1]，a[1]=a[2]=1，那么$\sum a_i\ \ $的期望就是树的期望高度

对于bfs序相邻的点i,i+1，
若dfn[i]>dfn[i+1]，他们之间肯定换层了，$a[i+1]=1$
若dfn[i]< dfn[i+1]，他们可以换层也可以不换，$a[i+1]=\frac 12$
对于dfs序相邻的点bfn[i],bfn[i+1]
因为显然有dep[bfn[i+1]]<=dep[bfn[i]]+1，所以若bfn[i]< bfn[i+1]，有限制$\sum_{i=bfn[i]+1}^{bfn[i+1]}a[i]<=1$

注意那个1/2的期望要满足限制
画一下图可以发现如果一个有限制的区间里面没有强制为1的$a[i]$，那就也不会有期望1/2的$a[i]$，所以维护一个前缀和用来打标记，O(n)扫一下就行了

输出很坑…坑在哪里见代码…

code：

#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int maxn = 210000;

int a[maxn],to[maxn];
int s[maxn],pre[maxn],fl[maxn];
int n;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        int x; scanf("%d",&x);
        to[x]=i;
    }
    for(int i=1;i<=n;i++) a[i]=to[a[i]];
    for(int i=1;i<=n;i++) to[a[i]]=i;

    s[1]=s[2]=2;
    for(int i=3;i<=n;i++)
        if(to[i]<to[i-1]) s[i]=2;
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+s[i];

    for(int i=2;i<n;i++) if(a[i]<a[i+1]&&pre[a[i+1]]-pre[a[i]])
        fl[a[i]+1]++,fl[a[i+1]+1]--;

    int cc=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        cc+=fl[i];
        if(!cc&&!s[i]) s[i]=1;
        ans+=s[i];
    }
    double re=ans/2.0;
    printf("%.3lf\n%.3lf\n%.3lf\n",re-0.001,re,re+0.001);

    return 0;
}