「NOI2013」树的计数 解题报告

「NOI2013」树的计数

这什么神题

---

考虑对bfs重新编号为1,2,3...n，然后重新搞一下dfs序

设dfs序为(dfn_i)，dfs序第(i)位对应的节点为(pos_i)

一个暴力是枚举bfs的分层，然后检查合法性。

但是我们注意到一个事情，节点(i)与节点(i-1)是否在同一层，是不是具有独立性呢？

设(s_i)表示(i)与(i+1)是否在同一层，当(s_i=1)时，表示不在同一层。

那么

• (s_1=1)，显然

• 若区间([l,r])是同层的，有(dfn_L<dfn_{L+1}<cdots<dfn_R)

  这个注意一点，遍历边的顺序是一样的，因此bfs先访问的dfs一定也先

  这样可以得到

  若(dfn_i>dfn_{i+1})，则(s_i=1)

  注意只有这两个条件可以强制为(s=1)，这个已经是全部了

  但是我们还需要统计(s=0)强制同一层的情况

• 一个点dfs序后面的一个点，一定是它儿子或者它祖先的儿子，即

  (dep_{pos_{i+1}}le dep_{pos_i}+1)

  设(pos_i=a,pos_{i+1}=b)

  如果(a>b)，那么就是普通的另外开了一颗子树，属于无用条件

  如果(b=a+1)，在条件2已经判断了

  如果(b>a+1)，说明一定产生了一个(1)的断层

  也就是(sum_{j=a}^{b-1}s_i=1)

• 注意到可能有点(s_i)还是没有处理，说明这个无所谓，产生的答案为(0.5)，因此答案为(1+sum s_i)

处理的话前两个都好弄，第三个表示区间至少有一个(1)（区间的(1)已经被2统计了）

可以直接打差分tag，来区分一下位置上是0还是0.5

---

Code:

#include <cstdio>
#include <cctype>
template <class T>
void read(T &x)
{
	x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
const int N=2e5+10;
int n,d[N],b[N],dfn[N],pos[N],s[N];
int main()
{
    read(n);
	for(int x,i=1;i<=n;i++) read(x),d[x]=i;
	for(int i=1;i<=n;i++) read(b[i]);
	for(int i=1;i<=n;i++) dfn[i]=d[b[i]];
	for(int i=1;i<=n;i++) pos[dfn[i]]=i;
	++s[1],--s[2];double ans=1;
	for(int i=2;i<=n;i++)
		if(dfn[i-1]>dfn[i])
			++s[i-1],--s[i],++ans;
	for(int i=2;i<=n;i++)
		if(pos[i-1]+1<pos[i])
			++s[pos[i-1]],--s[pos[i]];
	for(int i=1,j=0;i<n;i++) j+=s[i],ans+=(!j)?0.5:0;
	printf("%.3f
",ans+1);
	return 0;
}

---

2019.4.13