题意：给一棵有根树，从根节点深搜，每次随机走，问每个点的dfs序的期望是多少
分析：对于每一个点，它的所有祖先节点dfs序肯定在它之前，它所在的子树的节点一定在它后面，
剩下的是既不是子树又不是祖先的节点，可能在它之前，也可能在以后，这里面每个点在它之前的概率为0.5
也就是针对当前点，课变序列式呈对称态势的，所以最终期望是在中间
即：ret[u]=(n-son[u]-ancestor[u])/2+depth[u];这里的son[u]包括u
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1e5+;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9+;
typedef pair<int ,int >pii;
struct Edge{
int v,next;
}edge[N<<];
int head[N],tot,n,dep[N],son[N];
void add(int u,int v){
edge[tot].v=v;
edge[tot].next=head[u];
head[u]=tot++;
}
double ret[N];
void dfs(int u,int f){
son[u]=;dep[u]=dep[f]+;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].v;
dfs(v,u);
son[u]+=son[v];
}
ret[u]=1.0*(n-dep[u]+-son[u])/2.0+dep[u];
}
int main(){
scanf("%d",&n);
memset(head,-,sizeof(head));
for(int i=;i<=n;++i){
int u;scanf("%d",&u);
add(u,i);
}
dfs(,);
for(int i=;i<n;++i)
printf("%.1f ",ret[i]);
printf("%.1f\n",ret[n]);
return ;
}