Description:

给定一棵 个节点的树的 序,求所有满足要求的树的平均深度。


Solution:

考虑到 序的性质, 在前的点的深度一定小于等于后面的点。所以我们考虑根据 序计算答案。
首先根据 序给树上的点重编号,按 序的先后编成 ,考虑相邻的点 对答案的贡献,如果它和 必须在不同的层,那么对答案的贡献为 ,如果它和 必须在同一层,那么对答案的贡献为 ,否则为 ,最后只需要把所有的贡献加起来就行了 ()。
必须不在同一层很好判断,考虑一下必须在同一层的情况,如果点i在 序中的位置在点 前面的话,那么就一定在不同层。
否则只剩下在必须在同一层或者都可以。
在同一层和不同层都可以的情况,显然需要满足 序中 两个点必须是连续的。我们画图发现,如果在一棵按 序编号的树中,点 可以变作 的儿子的并且不改变 序的话,只能是 变换后, 所在的那一层只有 一个点并且 应该有共同的父亲,那么这个条件等价于 号点在 序中 的一段和 的一段,也就是说在 序中必须是前面一段最后一段。然后其他情况就是必须在同一层了。
最后记住 上不知道为什么需要输出三行,分别为


Code:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

int N;
int dfs[200010]={0};
int bfs[200010]={0};
int In[200010]={0};
int Max[200010]={0};
int hash[200010]={0};

int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&dfs[i]);
        In[dfs[i]]=i;
    }
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&bfs[i]);
        dfs[In[bfs[i]]]=i;
        bfs[i]=i;
    }
    for(int i=1;i<=N;i++)
        In[dfs[i]]=i;
    Max[1]=dfs[1];
    for(int i=2;i<=N;i++)
        Max[i]=max(Max[i-1],dfs[i]);
    double Ans=2;
    int l=2,r=N+1;
    hash[1]=hash[2]=1;
    for(int i=3;i<=N;i++)
    {
        if(In[i]<In[i-1])
            Ans+=1;
        else if(In[i]==In[i-1]+1)
        {
            if(l+N+1-r==i-1)
                Ans+=0.5;
        }
        hash[In[i]]=1;
        for(;l<r && hash[l+1]==1;l++);
        for(;l<r && hash[r-1]==1;r--);
    }
    printf("%.3lf\n",Ans);
    //In bzoj printf("%.3lf\n%.3lf\n%.3lf\n",Ans-0.001,Ans,Ans+0.001);
 return 0;
}