> 好题！
> 
> 起初打算用LCA来蒙分，后来一想，O(N^2)的复杂度不如直接搞暴力（N个dfs，可以加剪枝）
> 当然，如果只有一组测试数据，如果机器跑的超级快（比baidu*的机器再快几倍才好），
> 用裸暴力可以创造奇迹。不过，还是要面对现实，毕竟oj上只有ac一说。
> 
> 剩下的只有treeDP和分治了。先看treeDP
> f(i)：以i为根的子树中路径的个数。g(i,j)：以i为根的子树中，离i的距离为j的路径数。
> 不过，此题的k的范围貌似比较大。如果K<=10，那么就这么搞了。
> 
> 于是，唯一的希望寄托在分治上。第一种朴素的想法：
> 切断一条边，把图分治成两个子图。
> 用一次dfs来计算最好的切断边（两个子图尽量接近），
> 两次dfs+Merge来计算所有通过这条边的路径数，然后递归求解。期望复杂度Ω（nlogn）
> 
> 由于刚做过一个类似的题（树中求一个长度不超过K的路径，使权值和最大），
> 所以直接默写了代码。竟然TLE了？
> 为什么？
> 那个做过的题的节点数可以达到30000，依然闪电出解。
> 不过，那个题出的数据比较弱（暴搜跑的比标程快），
> 所以没有暴露出这种分治的弱点。
> 如果某个树，无论如何切断边，两个子图依然非常悬殊，那么算法复杂度退化为O(n*n).
> 从直觉上说，这样的数据应该不多。但看这个：
> 10000 10000
> 1 2 1
> 1 3 1
> 1 4 1
> ......
> 1 10000 1
> 无论如何选边，都会被恶心的。于是，我贡献了两次TLE(第2次用上了RadixSort)
> 
> 那怎么办呢？
> 
> 回到treeDP，之所以会状态数暴掉，是以为记录了太多无用的信息。
> 其实，每个g(i,j)中j的取值是非常有限的。不妨只把它想成一个数列。
> 这样，得到了一个删除点分治的策略。
> dfs(T)
>     dfs T's all subtrees
>     get the distance lists
>     merge them
> 实现的难点主要有两个：如何选根，如何合并。（所以我比较偏爱切断边分治）
> 如果合并用枚举子树对，那么也会被上面的那个数据恶心。一种想法:
> 每次找两个数列，把他们合并，同时计数。直到所有的数列都搞定。
> 有点像归并排序。
> 如何选可以合并的数列呢？这不是...最优编码树？
> 是的，每次找出最短的两个数列，合并之。这样，永远不会被恶心得太惨。
> 
> 由于我的代码实现能力过分弱智，没写出来。于是，用一种委屈求全的方法：
> 把每个数列的长度都想象成1.对于N各数列，合并左边N/2个，右边N-N/2个，
> 再一块合并。更像归并排序了。事实证明，即使这样也不会被恶心太惨。
> 
> 下面的一个问题是：如何选根？
> 
> 一个朴素的设想：我们把合并都搞到O(nlogn)那么强大了，
> 就让一次多合并几个子树吧。每次找子树最多的当根。
> 不过，依然tle。看下面这组数据：
> 10000 10000
> 1 2 1
> 2 3 1
> 3 4 1
> ......
> 9999 10000 1
> 很可能，一次选的根为1，2，3...10000。于是，被恶心到了。
> 
> 除了****出数据的人，还可以怎么办呢？
> 
> 一种办法：每次找一个节点，使得删除它后，最大的子树尽量小。
> 好像很难找出恶心的数据了。
> 事实证明：AC了！
> 
> 代码实现的细节很多...有人逼被疯了，搞面向对象技术（A+B写了4k的代码的那种）；
> 有人，像我，偷偷看了看别人的题解，然后自己翻译、揣摩。
> 最终，找到了简洁实用的方法，逃出了调试噩梦。
> 
> 推荐一个网址：
> http://hi.baidu.com/gugugupan/blog/item/33f250c757f1131c9d163d21.html
> 
>