http://codeforces.com/problemset/problem/696/B
题目大意：
这是一颗有n个点的树，你从根开始游走，每当你第一次到达一个点时，把这个点的权记为(你已经到过不同的点的数量+1)
每一次只有当子树中所有的点都已经游走过了再会向父亲走，走到每个儿子上的概率是相同的
对于每个点，求他的权的期望
(1 ≤ n ≤ 10^5)
题解：
首先我们发现，所有子树中所有的点的编号都一定比父亲要大
而且子树中的大小关系和我们访问它的顺序有关
如果对于一个节点u它的儿子为v(不只一个),那么我们知道访问顺序构成了一个全排列
所以，我们知道:对于点v1,它在v2之前的概率是0.5(因为是全排列)、
然后我们重新考虑这道题目：
我们考虑一下，如果访问的时候v1先于v2被访问，那么对v2的编号的影响是什么？
v2中的所有的编号都增加了v1.siz()，而这出现的概率是0.5
那么我们就知道了,若v1先于v2被访问，那么E(v2) += 0.5*v1.siz();
所以我们就有
E(v) = E(u) + 1 + sigma{v1.siz()*0.5}
= E(u) + 1 + 0.5(siz[u] - 1 siz[v])
直接dfs可以O(n)解决!
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=*x+ch-'',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = ;
struct Edge{
int to,next;
}G[maxn];
int head[maxn],cnt;
void add(int u,int v){
G[++cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt;
}
int siz[maxn];
#define v G[i].to
void dfss(int u){
siz[u] = ;
for(int i=head[u];i;i=G[i].next){
dfss(v);siz[u] += siz[v];
}return;
}double f[maxn];
void dfs(int u){
for(int i=head[u];i;i=G[i].next){
f[v] = f[u] + 1.0 + (double)(siz[u] - - siz[v])/2.0;
dfs(v);
}return;
}
#undef v
int main(){
int n;read(n);
for(int i=,x;i<=n;++i){
read(x);add(x,i);
}dfss();f[] = 1.0;dfs();
for(int i=;i<=n;++i) printf("%.1lf ",f[i]);puts("");
getchar();getchar();
return ;
}