传送门：D - Puzzles
题意：在一个图中，从1开始dfs，求每一个点到达的期望；
思路：（下面是队长写的）
首先求的是到每一个点的步数的期望.
记fa( u ) = v, son( v )表示v的儿子的集合,
z是son(v)中的点,其中 z != u , sum[z] 为 z 的子树的大小, p( z )表示z比u先访问到的概率;
那么可以发现对于u来说 ans[u] = ans[v] + 1 + x;
现在我要来算这个x, 如果 son(v).size == 1, 那么x为0;
否则能对u造成影响的就是son(v)中不是u的那些点,
以z为例, 如果z先于u访问到,那么到达u的步数就会加上sum[z], 那么 x += sum[z] * p(z);
可以发现这样一个规律对于son(v)任意一种排列a,都可以发现一种对应排列b,满足a和b中只有u和z的位置对换.而且u和v不可能同时被访问或者其中一个不被访问,那么可以得到p(z) = 0.5; 就是 x += sum[z] * 0.5；
那么x就可以算出来了: for(auto it : son[v]) x += sum[it] * 0.5;
时间复杂度O(n);
所以下面的ac代码中，dfs1（）就是求每一个点的sum值，通过类似前缀和的思想；
get1（）就是求ans；
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std; const int maxn = ; int n,sum[maxn];
vector<int>mp[maxn];
double ans[maxn];
void init(){
for(int i=;i<=n;i++)
mp[i].clear();
memset(ans,,sizeof(ans));
memset(sum,,sizeof(sum));
}
void dfs1(int d)
{
sum[d] = ;
for(int t=; t < mp[d].size(); t++)
{
int to = mp[d][t];
dfs1(to);
sum[d] += sum[to];
}
}
void get1(int d)
{
for(int t=; t<mp[d].size(); t++)
{
int to = mp[d][t];
ans[to] = ans[d] + + (sum[d]-sum[to]-) * 0.5;
get1(to);
}
}
int main(){
// freopen("in","r",stdin);
while(~scanf("%d", &n))
{
init();
for(int i=; i<=n; i++)
{
int x;
scanf("%d",&x);
mp[x].push_back(i);
}
dfs1();
ans[] = 1.0;
get1();
for(int i=; i<=n; i++)
{
printf("%.1f%c", ans[i], i==n?'\n':' ');
}
}
return ;
}