题解 CF696B 【Puzzles】
ouuan
2018-12-11 13:24:57
用 $f[u]$ 表示访问节点 $u$ 的期望时间,$siz[u]$ 表示子树 $u$ 的大小。
令 $v$ 为 $u$ 的一个儿子,那么 $f[v]=f[u]+1+\frac{siz[u]-siz[v]-1}2$ 。
因为 $u$ 除了 $v$ 以外的其它儿子,每个儿子都有 $\frac 1 2$ 的概率在 $v$ 之前被访问、$\frac 1 2$ 的概率在 $v$ 之后被访问,一个儿子 $v'$ 对 $f[v]$ 的贡献就是 $\frac{siz[v']}2$ 。
参考代码:
```cpp
#include <iostream>
#include <cstdio>
using namespace std;
const int N=100010;
void add(int u,int v);
void dfs1(int u);
void dfs2(int u);
int head[N],nxt[N],to[N],cnt;
int n,p[N],siz[N];
double f[N];
int main()
{
int i;
scanf("%d",&n);
for (i=2;i<=n;++i)
{
scanf("%d",p+i);
add(p[i],i);
}
dfs1(1);
f[1]=1;
dfs2(1);
for (i=1;i<=n;++i)
{
printf("%.6lf ",f[i]);
}
return 0;
}
void add(int u,int v)
{
nxt[++cnt]=head[u];
head[u]=cnt;
to[cnt]=v;
}
void dfs1(int u)
{
int i,v;
siz[u]=1;
for (i=head[u];i;i=nxt[i])
{
v=to[i];
dfs1(v);
siz[u]+=siz[v];
}
}
void dfs2(int u)
{
int i,v;
for (i=head[u];i;i=nxt[i])
{
v=to[i];
f[v]=f[u]+1+(siz[u]-1-siz[v])/2.0;
dfs2(v);
}
}
```