题意：给n个点，n-1条边，构成一个以1为根节点的树，从1开始走，问每个点时间戳的期望值。
题解：
cnt[i]为i的时间戳
考虑根节点1，cnt[1]=1
之后每个点x cnt[x]=cnt[fa[x]]+(size[fa[x]]-size[x]-1)/2+1
(size[fa[x]]-size[x]-1)/2 就是这个点的兄弟节点对其时间戳的贡献，感性理解：(每个点的遍历概率相同，所以当x在中间被遍历时是期望值)
1 就是从fa[x]走下来还需要+1
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<cmath> 5 #define mem(a,b) memset(a,b,sizeof(a)) 6 #define dd double 7 using namespace std; 8 const int N=100001; 9 struct son 10 { 11 int v,next; 12 }; 13 son a1[N<<1]; 14 int first[N<<1],e; 15 void addbian(int u,int v) 16 { 17 a1[e].v=v; 18 a1[e].next=first[u]; 19 first[u]=e++; 20 } 21 22 int n; 23 int u,o,p; 24 dd f[N]; 25 26 int size[N]; 27 void dfs(int x) 28 { 29 size[x]=1; 30 for(int i=first[x];i!=-1;i=a1[i].next) 31 { 32 int temp=a1[i].v; 33 dfs(temp); 34 size[x]+=size[temp]; 35 } 36 } 37 38 void dp(int x) 39 { 40 for(int i=first[x];i!=-1;i=a1[i].next) 41 { 42 int temp=a1[i].v; 43 f[temp]=f[x]+(dd)(size[x]-size[temp]-1)/2.0+1.0; 44 dp(temp); 45 } 46 } 47 48 int main(){ 49 mem(first,-1); 50 scanf("%d",&n); 51 for(int i=2;i<=n;++i) 52 { 53 scanf("%d",&u); 54 addbian(u,i); 55 } 56 dfs(1); 57 f[1]=1.0; 58 dp(1); 59 60 for(int i=1;i<=n;++i) 61 printf("%.1lf ",f[i]); 62 63 //while(1); 64 return 0;; 65 }