【CF696B】Puzzles（树形DP，期望）

题意：n 个节点的树，初始位置为 1 号节点，初始时间为 1。
每次随机地走向任何一个没有走过的子树并且令时间 +1
求问走到每一个点时的时间的期望值

思路：比较少见的一道自顶向下的树形DP

        dp[i]表示走到i点的期望时间

        对于U，考虑它走到儿子V需要时间1，在此之前可能要由1走到U，还要走过若干U的其它子树

        对于每一棵子树它对答案的贡献就是size，因为要走完所有的点才能出来

        任意子树在V前走的概率是0.5，所以计算它对dp[v]的贡献

        dp[v]=dp[u]+1+0.5*(size[u]-size[v]-1) （有U to V的一条边）

var head,vet,next,size:array[1..210000]of longint;
    dp:array[1..110000]of double;
    n,i,x,tot:longint;

procedure add(a,b:longint);
begin
 inc(tot);
 next[tot]:=head[a];
 vet[tot]:=b;
 head[a]:=tot;
end;

procedure dfs1(u,pre:longint);
var e,v:longint;
begin
 size[u]:=1;
 e:=head[u];
 while e<>0 do
 begin
  v:=vet[e];
  if v<>pre then
  begin
   dfs1(v,u);
   size[u]:=size[u]+size[v];
  end;
  e:=next[e];
 end;
end;

procedure dfs2(u,pre:longint);
var e,v:longint;
begin
 e:=head[u];
 while e<>0 do
 begin
  v:=vet[e];
  if v<>pre then
  begin
   dp[v]:=dp[u]+0.5*(size[u]-size[v]-1)+1;
   dfs2(v,u);
  end;
  e:=next[e];
 end;
end;


begin
 //assign(input,'cf696B.in'); reset(input);
 //assign(output,'cf696B.out'); rewrite(output);
 readln(n);
 for i:=2 to n do
 begin
  read(x);
  add(i,x);
  add(x,i);
 end;
 dfs1(1,-1);
 dp[1]:=1;
 dfs2(1,-1);
 for i:=1 to n do write(dp[i]:0:1,' ');
 //close(input);
 //close(output);
end.