先看一个题目
定义树的中心是到树的最远节点简单路径长度最短的点，给出一个树，请输出树的中心。
我们先使用DP尝试解决这个问题：
为求出树的中心，就必须算出树上每个节点到最远节点的长度。
而每个节点距离最远的节点根据计算条件可以被分成性质不同的两种：
（路径的单调是类比函数的单调性，说的是路径的形状）
1.最远节点是这个节点的子孙（用len_down表示路径是单调的，只要考虑儿子）
2.最远节点不是这个节点的子孙（用len_up表示，只要考虑他爹）
下面以节点i为例
对于第一种长度，可以很方便地得出方程
len_down[i] = max{len_down[k]}+ 1 k是i的儿子
对于叶子节点 len = 0
而对于第二种情况，又可以分为两种：
(1).最远节点是这个节点的祖先（路径是单调的）
(2).最远节点不是这个节点的祖先（不单调）
对于第一种长度，可以得出方程：
len_up_1[i] = len_up_1[j] + 1 j是i的父亲，根节点的len_up为0
对于后一种长度，就需要动一些脑筋了。
可以从对情况（2）的描述出发，可以知道，最远节点n一定在节点i的祖先m的某个分支上，但是，简单路径要求节点n一定不能len_down[j]在的路径中
最终，得出一个方程：
len_up_2[i] = len_down[j] + 1 j是i的父亲，i不能len_down[j]的路径里
为了解决加粗条件，引入“次向下长度”，用less_down[i]表示，就是节点i向下的第二长的长度。当发现节点j的向下长度内包含了i，就换用次向下长度。
然后根据树的递归性质和DP的最优子结构性质，可以把两个len_up合并（也是必须的）
len_up[i] = max{len_up_1[i],len_up_2[i]}
最后max_len[i] = max{len_down[i],len_up[i]}
另一种解法：
认为这棵树是无根的，既然说中心是到最远点最近的点，那么，如果把树中度为1点（“叶子”）删掉，构建一个新的树，然后不断重复上面的步骤，最后一定会剩下一个或者两个点，这就是树的中心。
DP方法的理论复杂度是O(n)，后一个方法是O(n^2)，但是从实际测试情况看，两者不相上下。
在点数达到5M时，DP使用了4s，方法2使用5s；当点数在1M一下时都可以在1s内通过，没有明显差别。
No comments:
Post a Comment