贪心、数学

发现 $1 \leq n \leq 10^5$，而没有什么手段能压缩树的形态从而支持状态转移，那么答案大概率是可以直接计算的。

首先写一个暴力代码，交一发测测它对不对。

#include<bits/stdc++.h>
using namespace std;
vector<int> sta,v[25];
bitset<25> son[25];
double ans;
int n;
void load(int x,int las){
    son[x].set();
    sta.push_back(x);
    for(int i:sta) son[i][x]=0;
    for(int i:v[x]) if(i!=las) load(i,x);
    sta.pop_back();
}
void dfs(bitset<25> x,int dep,double sum){
    if(x.none()) return ans+=dep*sum,void();
    int m=x.count();
    for(int i=x._Find_first();i<25;i=x._Find_next(i)) dfs(x&son[i],dep+1,sum/m);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++){
        static int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    load(1,0);
    bitset<25> S;
    for(int i=1;i<=n;i++) S[i]=1;
    dfs(S,0,1.0);
    printf("%.8lf\n",ans);
    return 0;
}

结果是 RE on test 4，那应该是对了。现在构造一些树然后看看答案形态。

5
1 4
1 5
2 3
2 4

答案是 $2.58333333$，现在给 $2$ 多挂几个儿子看看答案会如何变化。

7
1 4
1 5
2 3
2 4
2 6
2 7

答案是 $3.08333333$，有点神秘，它恰好增加了 $0.5$，怎么回事呢？

灵光一闪发现实际上这个值是 $\sum\limits_{i=1}^{n} \dfrac{1}{d_i}$，有点牛。

交一发看看。过了。

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
vector<int> v[100'005];
double ans;
int n;
void dfs(int x,int las,int dep){
    ans+=1.0/dep;
    for(int i:v[x]) if(i!=las) dfs(i,x,dep+1);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++){
        static int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0,1);
    printf("%.8lf\n",ans);
    return 0;
}

接下来分析为什么这样是对的。

令 $f_i$ 为点 $i$ 被选中的次数，则答案为 $E \left( \sum\limits_{i=1}^{n} f_i \right) = \sum\limits_{i=1}^{n} E(f_i)$，问题转化为计算所有 $E(f_i)$ 的值。

刻画操作过程，随机生成一个排列 $p$，每次找到 $p$ 中第一个未被染色的节点 $i$，然后对其子树内所有节点染色。

可得 $i$ 被选中当且仅当 $i$ 的所有祖先在 $p$ 中的位置都比 $i$ 大，对于 $p$ 中由 $i$ 与其 $d_i - 1$ 个祖先构成的长度为 $d_i$ 的子序列，$i$ 为首个元素的概率为 $\dfrac{1}{d_i}$，于是 $E(f_i) = \dfrac{1}{d_i}$。