首先根据题意，要求计算节点的所有k子集（k > 1)的对应的期望值，该期望值定义为子集中元素最大值和次大值调和平均值的1/2。

子集元素的值为其在树中的深度加一。

显然子集共有2ⁿ-n-1个，将元素值按照降序排列（存数列s），枚举最大值和次大值出现的位置，假设其分别为i，j且（0<i<j<n+1)。

考虑这一二元组对应的子集共有2^n-j个，于是该二元组对答案的贡献值为2^n-j/(2ⁿ-n-1) * s[i] * s[j] / (s[i] + s[j])。

考虑到s[i] * s[j] / (s[i] + s[j]) ≤ sqrt(s[i] * s[j]) / 2 < max(s[i], s[j]) < 1e5

当j > 100时，2^n-j/(2ⁿ-n-1) < 2^-100 < 1e-30

显然已经满足结果保留6位有效数字的要求，因此当n较大时只需枚举j < 100的情况即可。

注意一些表示细节。

 

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5  6 using namespace std; 7  8 const int maxn = 1e5 + 10; 9 10 vector
          
            G[maxn];11 int d[maxn];12 int n;13 double ans;14 15 void dfs(int u, int dep){16     int d1 = G[u].size();17     for(int i = 0; i < d1; i++){18         int v = G[u][i];19         d[v] = dep + 1;20         dfs(v, dep + 1);21     }22 }23 24 bool cmp(int a, int b) { return a > b; }25 26 double f(int num){27     if(num > 50) return 0;28     double ans = n + 1;29     while(num--) ans /= 2;30     return ans;31 }32 33 int main(){34     while(~scanf("%d", &n)){35         for(int i = 1; i <= n; i++) G[i].clear();36         for(int i = 1, j; i < n; i++){37             scanf("%d", &j);38             G[j].push_back(i + 1);39         }40         d[1] = 1;41         dfs(1, 1);42         sort(d + 1, d + n + 1, cmp);43         ans = 0;44         int rear = n > 100 ? 100 : n;45         double tem = 2;46         for(int j = 2; j <= rear; j++){47             tem *= 2;48             for(int i = 1; i < j; i++){49                 ans += (double)d[i] * d[j] / (d[i] + d[j]) / (tem - f(n - j));50             }51         }52         printf("%.6f\n", ans);53     }54     return 0;55 }