description
厉害题。
给定一棵树，按照题面要求求一个错误点分治的期望执行次数。（不想描述题面了qwq）
solution
考虑拆开计算每个点期望几层点分治后被删除。这个期望值显然就是它对答案的贡献。
我们不妨以这个点为根，那么相当于要求每次删除一个未被删除的点的子树，求删完的期望次数。这个题就是经典的 Game on tree。结论就是所有点的深度加一的倒数和。
放在这个题我们就要求 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^n \dfrac{1}{dis(i,j)+1}\)。一个显然的做法是 \(O(n^2)\) 扫一遍，但是会 T。我们可以考虑计算每个路径 \((i,j)\) 的贡献。这就变成了点分治可以处理的问题。
设当前根为 \(p\)，子树下的 \(i\) 节点深度为 \(d_i\)。那么我们要求 \(\sum\limits_{i\in subtree(p)}\sum\limits_{j\in subtree(p)} \dfrac{1}{d_i+d_j+1}[lca(i,j) = p]\)。
不妨先算 \(\sum\limits_{i\in subtree(p)}\sum\limits_{j\in subtree(p)} \dfrac{1}{d_i+d_j+1}\)。对于两点在同一个子树内的容斥一下。
设深度为 \(k\) 的点有 \(cnt_k\) 个，把式子改写成 $\sum\limits_{i=1} \dfrac{1}{i}\sum\limits_{j=0} cnt_j cnt_{i+1-j} $ 后面是个卷积形式，可以 FFT。
设 \(maxd=\max\limits_{i\in subtree(p)}\{d_i*2+1\}\) 则单层的时间复杂度为 \(O(maxd\log maxd)\)。
由于每层的 \(maxd\) 不超过这层的总点数，所以时间复杂度 \(O(n\log^2 n)\)。
第一遍淀粉质还写挂了