题目大概意思就是求每个点标号的平均期望……
我也是看了好多解法才稍微有点理解的……
网上大神推出来的方程ans[v]=ans[i]+1+(num[i] - num[v] - 1) / 2 说实话 我推不出来……-_-||
用两次dfs来求解……
1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<math.h> 5 #include<string.h> 6 #include<string> 7 #include<map> 8 #include<vector> 9 #include<queue> 10 #define M(a,b) memset(a,b,sizeof(a)) 11 using namespace std; 12 const int maxn=100005; 13 int n,val; 14 int num[maxn]; 15 double ans[maxn]; 16 vector<int>vec[maxn]; 17 void dfs1(int x){ 18 int len=vec[x].size(); 19 num[x]=len; 20 for(int i=0;i<len;i++){ 21 int v=vec[x][i]; 22 dfs1(v); 23 num[x]+=num[v]; 24 } 25 } 26 void dfs2(int x){ 27 int len=vec[x].size(); 28 for(int i=0;i<len;i++){ 29 int v=vec[x][i]; 30 ans[v]=ans[x]+1+(num[x]-num[v]-1)/2.0; 31 dfs2(v); 32 } 33 } 34 int main(){ 35 scanf("%d",&n); 36 for(int i=0;i<=n;i++){ 37 vec[i].clear(); 38 num[i]=0; 39 } 40 for(int i=2;i<=n;i++){ 41 scanf("%d",&val); 42 vec[val].push_back(i); 43 } 44 dfs1(1); 45 ans[1]=1; 46 dfs2(1); 47 for(int i=1;i<=n;i++) 48 printf("%lf%c",ans[i],i==n?' ':' '); 49 return 0; 50 }