好题！

起初打算用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

• 你这不是树的分治，而是归并吧，不过也挺快的，顶~ (1749) RectaFlex 2010-04-23 18:42:47
• 楼主写题解全是“雁过留声”，很亲切啊…… (0) applepi 2010-10-29 20:30:29