首页 > 代码库 > 【codeforces 696B】 Puzzles
【codeforces 696B】 Puzzles
http://codeforces.com/problemset/problem/696/B (题目链接)
题意
给出一棵树，随机dfs遍历这棵树，求解每个节点的期望dfs序。
Solution
考虑对于节点u，其某个儿子节点v的期望是多少。
首先，节点u的儿子的dfs的顺序是其儿子数son[x]的全排列。考虑在排列中有多少个节点在v的前面，不妨设x排在v的前面，那么满足的排列数为：${P_n^{n-2}}$，于是x对v的期望的贡献为：$${\frac{P_n^{n-2}×size[x]} {P_n^n}=2×size[x]}$$
因为节点u的每一个节点都会对v产生贡献，再算上v自己的贡献，所以v的期望：
$${f_v=\frac{size_u-1-size[v]}{2}+1+f[u]}$$
代码
// codeforces696B#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 1<<30#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=100010;struct edge {int to,next;}e[maxn<<1];int head[maxn],size[maxn],n,cnt;double f[maxn];void link(int u,int v) { e[++cnt]=(edge){v,head[u]};head[u]=cnt;}void dfs(int x) { size[x]=1; for (int i=head[x];i;i=e[i].next) { dfs(e[i].to); size[x]+=size[e[i].to]; }}void dp(int x) { for (int i=head[x];i;i=e[i].next) { f[e[i].to]=(double)(size[x]-1-size[e[i].to])/2+1+f[x]; dp(e[i].to); }}int main() { scanf("%d",&n); for (int x,i=2;i<=n;i++) { scanf("%d",&x); link(x,i); } dfs(1); f[1]=1;dp(1); for (int i=1;i<=n;i++) printf("%.6lf ",f[i]); return 0;}
【codeforces 696B】 Puzzles
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。