题意:
给出一棵树的 dfs 序和 bfs 序,求所有可能的原树的高度平均值
\(n \leq 2 \cdot 10^5\)
首先把 bfs 序变成 \(1 \to n\),这样就需要把原树上的节点分成若干层。
设 \(pos_{dfn_i}=i\),\(dfn\) 数组存点性质,\(pos\) 数组存点编号。
注意到每个节点是否分层对答案的贡献独立,单独求出每个节点是否能分层即可。
首先处理分层对 dfs 序的限制:当 \(dfn_x > dfn_{x+1}\) 时,\(x\) 与 \(x+1\) 间必须分层。
现在研究一棵树的 dfs 序应该满足什么条件。
思考做 dfs 的过程,每一步可以回溯或进入一个子节点。
借张图,图源 link
dfs 的每一步可以回溯或往下走到子节点。因为有换层出现,\(3\) 中的换层已经被计算,现在要把 \(3\) 筛选出来。
第一种情况 \(pos_y = pos_x+1\),第二种情况 \(pos_y < pox_x\),所以当 \(pos_y>pos_x+1\) 时一定属于第三种情况。
因此获得了两个限制:\(dfn_x > dfn_{x+1}\) 时 \(x\) 必须分层,\(pos_y>pos_x+1\) 时 \(x\) 与 \(y\) 之间不能再分层。
#include <cstdio>
using namespace std;
const int M = 2e5 + 5;
int read(){
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
return x * f;
}
int n, bfs[M], pos[M], dfs[M], dif[M], dfn[M];
void solve(int l, int r) {++dif[l]; --dif[r+1];}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) dfn[read()] = i;
for(int i = 1; i <= n; i++) pos[dfn[read()]] = i;
for(int i = 1; i <= n; i++) dfn[pos[i]] = i;
solve(1, 1);
double ans = 1;
for(int i = 1; i < n; i++) {
if(pos[i] < pos[i+1] - 1) solve(pos[i], pos[i+1] - 1);
if(dfn[i] > dfn[i+1]) ++ans, solve(i, i);
}
int t = 0;
for(int i = 1; i < n; i++) {
t += dif[i];
ans += t ? 0 : 0.5;
}
printf("%.3lf\n", ans+1);
}
标签:int,pos,dfs,计数,分层,dfn,数学,P1232,节点
From: https://www.cnblogs.com/purplevine/p/16973507.html