题解 P1232 【[NOI2013]树的计数】

· · 题解

[NOI2013]树的计数

目前讲的最清楚的solution？（大雾）

Click here for a better reading experience（人话：myblog）

给定树的dfs序和bfs序，显然是通过它们之间的互相约束以得出答案。

为了方便，对编号做修改（不影响答案）。

$bfs$序改为：$dfs$序为$1,2,...,n$时的$bfs$序（设为$b[i]$） 树高$h$如何表示？假设将$bfs$序分成$i$段，$h=i$，每段内的所有点都在同一层 ------------ 而任意点$k$后，分段/不分段，对平均树高$H$的贡献为$1/0

每个k有3种情况：

①只能分段，H+=1

②分不分都行，H+=0.5

③不能分，H+=0

对于②、③，我们用一个差分数组s[i]表示状态。

累计s[i]的前缀和ts，ts=0为②，ts>0为③

至于①，我们可以直接处理掉，下面会讲

注意，对于根节点1，它只能分成单独的一段（一种①）

有个问题，bfs序并不能能随意分段，要受到dfs序的限制（用s[i]表示）

观察发现，假设我们将bfs序中的[l,r]分成一段，必须满足b[l]<b[l+1]<...<b[r]

因为在同一层内，dfs扫点一定是从左到右

所以dfs序一定是从左到右递增的（dfs序已经为1...n）。

于是得出一个约束条件：b[i]>b[i+1]时，i和i+1显然不能分到同一层内，必须断开。（另一种①）

接下来考虑bfs序对dfs序的限制

还是考虑dfs序上两个相邻的点i,i+1

发现它们之间有3种关系（红点为i，蓝点为i+1）

1.i和i+1是兄弟（i没有儿子）

2.i+1是i的祖先的某个儿子（i没有儿子）

3.i+1是i的儿子

发现第3种情况有点东西：

而且切这一段的贡献已经在①中被算过了 于是$d[i]$~$d[i+1]$就不能再贡献啥了，也就是总贡献$=0$，$H+=0

然鹅怎么把第1,2种情况筛掉呢

发现对于第1种，d[i]>d[i+1]

对于第2种，d[i]+1=d[i+1]

（或者第3种的一层只有i，下一层只有i+1。把它筛掉没有影响）

**于是我们又得出了一个约束条件：$d[i]+1<d[i+1]$时，$bfs$序中的$[d[i],d[i+1]]$不会再产生贡献（③）** ------------ **剩下不被约束的点都属于②，**$H+=0.5$，表示取/不取产生贡献的平均值$(0+1)/2

再注意一些小细节（见code）于是就可以搞定这个思维题辣

参考博客：①，②

#include<iostream>
#include<cstdio>
#define rint register int
using namespace std;
#define N 200005
int read(){
    char c=getchar();int x=0;
    while(c<'0'||c>'9') c=getchar();
    while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar();
    return x;
}
int n,s[N],b[N],d[N],a[N],c[N];
double ans;
int main(){
    n=read(); ans=2; ++s[1];--s[2];//ans=2：根节点算1层+最下面的1层=2层
    for(rint i=1;i<=n;++i) a[d[i]=read()]=i;
    for(rint i=1;i<=n;++i) c[b[i]=read()]=i;
    for(rint i=1;i<=n;++i) d[i]=c[d[i]],b[i]=a[b[i]];
    for(rint i=1;i<n;++i) if(b[i]>b[i+1]) ++s[i],--s[i+1],++ans;//ans没有算到最下面的一层，先加上去
    for(rint i=1;i<n;++i) if(d[i]+1<d[i+1]) ++s[d[i]],--s[d[i+1]];
    for(rint i=1,w=0;i<n;++i) w+=s[i],ans+=w?0:0.5;//第n个点后面都是空的给它分段有什么意义吗
//    printf("%.3f\n%.3f\n%.3f",ans-0.001,ans,ans+0.001);
//     bzoj需要输出以上ans-0.001,ans,ans+0.001（大雾）
    printf("%.3f",ans);
    return 0;
}