建设专业网站,vs能建设网站吗,盘锦网站建设价位,关键词组合工具传送门
题意#xff1a;给定一棵nnn个点的树的DFS和BFS序#xff0c;求树高期望。 n≤2e5n \leq 2e5n≤2e5
首先根据BFS序将树点分层#xff0c;一定切记先自己把树点分层#xff0c;这样实际上是在排除一部分情况。
将每一层第一个点打标记#xff0c;答案就是期望标记…传送门
题意给定一棵nnn个点的树的DFS和BFS序求树高期望。
n≤2e5n \leq 2e5n≤2e5
首先根据BFS序将树点分层一定切记先自己把树点分层这样实际上是在排除一部分情况。
将每一层第一个点打标记答案就是期望标记个数。
首先BFS序第一个和第二个一定有标记。
对于之后BFS序相邻的两个如果后面的DFS序小于前面的说明这里分了层给后面打上标记。
还有一个限制DFS序相邻的两个点后面最多比前面深一层。所以用前面的标记算出层数如果后面大于前面用差分实现区间修改为-1表示一定没有标记。
而剩下的点可分可不分贡献0.50.50.5
复杂度O(n)O(n)O(n)
#include iostream
#include cstdio
#include cstring
#include cctype
#define MAXN 200005
using namespace std;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
int dfs[MAXN],bfs[MAXN],dfn[MAXN],bfn[MAXN];
int mark[MAXN],dep[MAXN],s[MAXN];
int main()
{int nread();for (int i1;in;i) dfn[dfs[i]read()]i;for (int i1;in;i) bfn[bfs[i]read()]i;dep[bfs[1]]dep[bfs[2]]mark[bfs[1]]mark[bfs[2]]1;for (int i2;in;i)if (dfn[bfs[i1]]dfn[bfs[i]])dep[bfs[i1]]mark[bfs[i1]]1;for (int i1;in;i) cerrmark[i]endl; for (int i1;in;i) dep[bfs[i]]dep[bfs[i-1]];for (int i1;in;i)if (dep[dfs[i]]dep[dfs[i1]])s[bfn[dfs[i]]1],--s[bfn[dfs[i1]]1];for (int i1;in;i) cerrs[i]endl;for (int i1;in;i)if ((s[i]s[i-1])0!mark[bfs[i]])mark[bfs[i]]-1;for (int i1;in;i) cerrmark[i]endl;double ans0;for (int i1;in;i)if (mark[i]1) ans1;else if (mark[i]0) ans0.5;printf(%.3f,ans);return 0;
}
