loj#2665. 「NOI2013」树的计数

---

目录

• [TOC]

题目链接

loj#2665. 「NOI2013」树的计数

题解

求树高的期望

对bfs序分层

考虑同时符合dfs和bfs序的树满足什么条件

第一个点要强制分层

对于bfs序连续的a,b两点,若a的bfs序小于b的bfs序,且a的dfs序大于b的,那么它们之间肯定要分层,对答案贡献为1

对于dfs序连续的a,b两点,若a的dfs序小于b的,且a的bfs序也小于b,那么它们的深度差不超过1，也就是说它们在的bfs序上之间最多分一层

先把前两个条件都判一下，然后把第2个条件判一下(如果它们之间已经分层了，那么就强制其他的不分层)

最后剩下的可分层可不分的点，贡献是0.5

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#define gc getchar()

#define pc putchar

inline int read() {

	int x = 0,f = 1;

	char c = getchar();

	while(c < '0' || c > '9') c = gc;

	while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc;

	return x * f;

}

void print(int x) {

 	if(x < 0) {

 		pc('-');

 		x = -x;

 	}

 	if(x >= 10) print(x / 10);

 	pc(x % 10 + '0');

 }

const int maxn = 200007;

 int n,top = 0,q[maxn];

 double ans = 0;

 int P[maxn],D[maxn],B[maxn];

 int x[maxn],y[maxn];

inline void mark(int a,int b) {

	++ y[a], -- y[b];

}

 int main() {

 	n = read();

 	for(int j,i = 1;i <= n;++ i) P[j = read()] = i;  //dfs中第j个点排在第i位

 	for(int j,i = 1;i <= n;++ i) D[B[i] = P[j = read()]] = i;

 	//B:bfs序中排在第i的点在dfs序中排B[i]

 	//D:dfs序中排在第i的点在bfs序中排D[i]

 	for(int i = 1;i < n;++ i) {

 		x[i] = x[i - 1];

 		if(i == 1 || B[i] > B[i + 1]) //lev[i] < lev[i + 1]

 			ans += 2.0,

 			++ x[i],

 			mark(i,i + 1);

 	}

 	for(int i = 1;i < n;++ i) {

 		if(D[i] < D[i + 1]) {

 			if(x[D[i + 1] - 1] > x[D[i] - 1]) //层数小

 					mark(D[i],D[i + 1]);

 			else q[++ top] = D[i]; //

 		}

	}

	for(int i = 1;i <= n;++ i) y[i] = y[i] + y[i - 1];

 	for(int i = 1;i <= top;++ i) ans += (y[q[i]] == 0);

 	printf("%.3lf\n%.3lf\n%.3lf\n",ans / 2 + 1 - 0.001,ans / 2 + 1,ans / 2 + 1 + 0.001);

 	return 0;

 }