神仙题。
题目
题意
求一个错误淀粉质的复杂度。
题解
对于每个点分开考虑。这个点对答案的贡献是期望在多少次递归后被删除。
假设当前考虑的节点是根节点。
如果删除树上一个节点，树会分成若干个连通块。我们要考虑根节点所在的连通块。显然，这个连通块是被删除节点的父节点所处的连通块。也就是说删一个点等价于删除这个点的子树。
这样，题目就转化为：每次删除一个未被删除的节点的子树，求删除根节点的期望次数。
此时，题目就和 Game on tree 一模一样。
考虑每个点的贡献。如果这个点在操作序列中在所有祖先的前面，就对答案有贡献。概率就是祖先的个数的倒数，也就是深度的倒数。
答案就是所有节点的深度的倒数和，也就是所有点到根结点的距离的倒数和。
把每个点作为根节点考虑，把答案加起来，可以发现答案就是任意两个点的距离加 1 的倒数和。
考虑点分治。
求穿过根节点的路径长度加 1 的倒数和。
预处理子树中每个节点的深度，答案就是任意两个不在同一个子树内的点的深度和加 1 的倒数和。可以容斥。答案就是任意两个点的深度和加 1 的倒数和减去每个子树内深度和加 1 的倒数和。
问题转化为：\sum\limits_{i=1}^n\sum\limits_{j=1}^n\frac1{dep_i+dep_j+1}。
统计深度为 i 的点的数量 c_i，答案为：
\sum\limits_{i=1}^m\sum\limits_{j=1}^m\frac1{i+j+1}c_ic_j
枚举 $i+j$，答案为
$\sum\limits_{k=1}^{2m}\frac1{k+1}\sum\limits_{i=1}^kc_ic_{k-i}$。
右边的东西可以直接 FFT。
时间复杂度 $O(n\log^2n)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mods=998244353;
int pows(int a,int b){
if(b==0)return 1;
int res=pows(a,b>>1);
res=res*res%mods;
if(b&1)res=res*a%mods;
return res;
}
const int n1=3,n2=pows(3,mods-2);
int r[1000005];
void fft(int *p,int n,int op){
int bt=1;
while((1<<bt)<n)bt++;
for(int i=0;i<n;i++){
r[i]=(r[i>>1]>>1)|((i&1)<<bt-1);
if(i<r[i])swap(p[i],p[r[i]]);
}
for(int mid=1;mid<n;mid<<=1){
int tmp=pows(op==1?n1:n2,(mods-1)/(mid<<1));
for(int i=0;i<n;i+=mid<<1){
int om=1;
for(int j=0;j<mid;j++,om=om*tmp%mods){
int x=p[i+j],y=p[i+j+mid]*om%mods;
p[i+j]=(x+y)%mods,p[i+j+mid]=(x-y)%mods;
}
}
}
}
int gets(int x){
int res=1;
while((1<<res)<=x)res++;
return 1<<res;
}
double res;
int n,siz[100005],zd[100005],zx,mk[100005],bk[100005],dep[100005],c[100005],cr[100005],md,mdx;
vector<int>p[100005],jl;
void dfs1(int x,int y){
zd[x]=0;
mk[x]=1;siz[x]=1;
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
if(mk[c]||bk[c])continue;
dfs1(c,y);
siz[x]+=siz[c];
zd[x]=max(zd[x],siz[c]);
}
zd[x]=max(zd[x],y-siz[x]);
if(zx==0||zd[zx]>zd[x])zx=x;
mk[x]=0;
}
void dfs2(int x){
mk[x]=1;siz[x]=1;
c[dep[x]]++;cr[dep[x]]++;
md=max(md,dep[x]);
mdx=max(mdx,dep[x]);
jl.push_back(x);
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
if(mk[c]||bk[c])continue;
dep[c]=dep[x]+1;
dfs2(c);
siz[x]+=siz[c];
}
mk[x]=0;
}
void solve(int x){
if(siz[x]==1)return;
bk[x]=1;md=0;siz[x]=1;
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
if(bk[c])continue;
dep[c]=1;mdx=0;
dfs2(c);
int m=gets(2*mdx);
fft(cr,m,1);
for(int i=0;i<=m;i++)cr[i]=cr[i]*cr[i]%mods;
fft(cr,m,-1);
int ny=pows(m,mods-2);
for(int i=0;i<=m;i++)cr[i]=cr[i]*ny%mods,cr[i]=(cr[i]+mods)%mods;
for(int i=1;i<=m;i++)res-=1.0/(i+1)*cr[i];
for(int i=0;i<=m;i++)cr[i]=0;
siz[x]+=siz[c];
}
int m=gets(2*md);
c[0]=1;
fft(c,m,1);
for(int i=0;i<=m;i++)c[i]=c[i]*c[i]%mods;
fft(c,m,-1);
int ny=pows(m,mods-2);
for(int i=0;i<=m;i++)c[i]=c[i]*ny%mods,c[i]=(c[i]+mods)%mods;
for(int i=1;i<=m;i++)res+=1.0/(i+1)*c[i];
for(int i=0;i<=m;i++)c[i]=0;
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
if(bk[c])continue;
zx=0;
dfs1(c,siz[x]);
solve(zx);
}
}
signed main(){
cin>>n;
for(int i=1;i<n;i++){
int x,y;
scanf("%lld%lld",&x,&y);
x++,y++;
p[x].push_back(y);
p[y].push_back(x);
}
solve(1);
printf("%.4lf",res+n);
}
```