相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3451
神犇题解：http://wyfcyx.is-programmer.com/posts/74735.html
解题报告
考虑一个点$u$，如果点分到点$v$的时候会产生贡献
那么点分$v$的时候，$v \to u$这个路径上还没有其他点被点分
换一句话来讲，点$v$应该是$v \to u$这条路径上第一个被点分的点
因为每一个点被选的概率一样，所以贡献的概率是$\frac{1}{dis_{u \to v} + 1}$
于是最后答案就是$\sum\limits_{u,v \in [1,n]}{\frac{1}{dis_{u \to v}+1}}$
然后这个东西我们可以使用点分治加上FFT来解决
具体来讲就是在点分的时候统计$dis_{u \to v}=x$的方案数，然后计入答案
时间复杂度：$O(n \log^2 n)$
—————————— UPD 2017.4.11 ————————————
找到这题的序列版了：http://www.lydsy.com/JudgeOnline/problem.php?id=2769
在具体的做法方面，用分个块，然后块内暴力，块间FFT即可
It’s hard to find knowledgeable people on this topic, but you sound like you know what you’re talking about! Thanks
This is very interesting, You’re an overly skilled blogger. I have joined your feed and look ahead to looking for more of your fantastic post. Also, I have shared your site in my social networks!