相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4543
神犇题解Ⅰ：http://blog.csdn.net/u010600261/article/details/53576251
神犇题解Ⅱ：http://blog.csdn.net/neither_nor/article/details/51278993
解题报告
设$f[i][j]$为到点$i$距离为$j$的点的个数
设$g[i][j]$表示一堆点到点$i$，各自距离均为$j$的对数
这样的话，我们就可以愉快地DP了，时间复杂度$O(n^2)$
现在将这颗树树链剖分，将重儿子重定义为子树深度最深的点
明显一个点的重儿子到这个点的转移可以直接将数组平移，这个用指针实现是$O(1)$的
现在考虑轻儿子，用轻儿子的数组去更新父亲节点的信息
这样看起来是$O(n^2)$的，但实际上这是$O(n)$的
考虑内存使用了多少：每一条重链的空间等于重链长度，所以空间复杂度为$O(n)$的
考虑每一个申请的空间，只会被用来更新所在重链的最上面那个点的父亲
也就是说每一个数组的单位，只会被访问一次，所以时间复杂度也是$O(n)$的啦！
另外值得一提的是，这种优化方式的普适性较强
除了这道题之外，我还在四道题里见到过这样的优化
比如：UOJ 284
I would like to thnkx for the efforts you have put in writing this blog. I am hoping the same high-grade blog post from you in the upcoming as well. In fact your creative writing abilities has inspired me to get my own blog now. Really the blogging is spreading its wings quickly. Your write up is a good example of it.
We’re a group of volunteers and starting a new scheme in our community. Your site offered us with valuable information to work on. You’ve done a formidable job and our entire community will be grateful to you.