CodeForces

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=0;char ch;bool flag = false;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    while(x=10*x+ch-'0',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 = 100010;
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] = 1;
    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] - 1 - siz[v])/2.0;
        dfs(v);
    }return;
}
#undef v
int main(){
    int n;read(n);
    for(int i=2,x;i<=n;++i){
        read(x);add(x,i);
    }dfss(1);f[1] = 1.0;dfs(1);
    for(int i=1;i<=n;++i) printf("%.1lf ",f[i]);puts("");
    getchar();getchar();
    return 0;
}