商城网站建设自助建站平台,腾讯云官网入口,高端装修公司展厅布置,天元建设集团有限公司刘士龙// luogu-judger-enable-o2
/*
考虑将bfs序按层分段#xff0c; 每分一段就会使深度1#xff0c;所以分的段数1就是深度
由于每种分段方式至多只能对应一种dfs序#xff0c; 所以我们的目标就是求出可行的bfs序
然后我们发现#xff0c; 如果在bfs序中第i个比第i 1个后出现…// luogu-judger-enable-o2
/*
考虑将bfs序按层分段 每分一段就会使深度1所以分的段数1就是深度
由于每种分段方式至多只能对应一种dfs序 所以我们的目标就是求出可行的bfs序
然后我们发现 如果在bfs序中第i个比第i 1个后出现在dfs序中 那么这里一定分段然后我们考虑dfs序对于bfs序的限制 假设a[i] a[i 1]的话意味着a[i 1]和a[i]同层或者在下一层那么\sum_{i a[i]} ^ {a[i 1] - 1} 分层 1这样的话得到了一些限制以及确定位置 没有限制的位置因为任意分都可以 那么统计0.5答案即可*/
#includecstdio
#includealgorithm
#includeiostream
#includecstring
#includequeue
#define mmp make_pair
#define ll long long
#define M 200010
using namespace std;
int read() {int nm 0, f 1;char c getchar();for(; !isdigit(c); c getchar()) if(c -) f -1;for(; isdigit(c); c getchar()) nm nm * 10 c - 0;return nm * f;
}
double note[M], s[M];
int t[M], a[M], pos[M], f[M], sta[M], n, tp;
int main() {double ans 1;n read();for(int i 1; i n; i) t[read()] i;for(int i 1; i n; i) {int x read();a[t[x]] i, pos[i] t[x];}note[1] 1;for(int i 1; i n; i) {if(pos[i] pos[i 1]) note[i] 1;if(note[i] 1) {f[i];f[i 1]--;}s[i] s[i - 1] note[i];}for(int i 1; i n; i) {if(a[i] a[i 1]) {if(s[a[i 1] - 1] - s[a[i] - 1] 0) {f[a[i]];f[a[i 1]]--;} else sta[tp] a[i];}}for(int i 1; i n; i) f[i] f[i - 1];for(int i 1; i tp; i) {if(f[sta[i]] 0) note[sta[i]] 0.5;}for(int i 1; i n; i) ans note[i];printf(%.3lf\n, ans);return 0;
} 转载于:https://www.cnblogs.com/luoyibujue/p/10903784.html
