分治算法在树的路径问题中的应用
一、树的分治算法
树的分治算法是分治思想在树型结构上的体现。
任一个具有n个节点的连通路，它的任何一棵树的树枝数为n-1
分治：除去树中的某些对象，使原树被分解成若干互不相交的部分。
分治算法分为两种：一种是点的分治，一种是边的分治
1.基于点的分治
1.选取一个点将无根树转为有根树
2.递归处理每一颗以根结点的儿子为根的子树
2.基于边的分治
1.在树中选取一条边
2. 将原有的树分成两棵不相交的树，递归处理。
可以证明在基于点的分治中，如果每次都选取树的重心，那么至多递归
O(LogN)次。
基于边的分治最坏情况下递归次数为O(N)。
二、树的重心
我们选取一个点，要求将其删去后，结点最多的树的结点个数最小，这个点被称作”树的重心”
下面给出一个定理：
存在一个点使得分出的子树的结点个数均不大于N/2
证明：(反证法证明)
假设U是树的重心，记Size(X)表示以X为根的子树的结点个数。记V为U的儿子中Size值最大的点。
假设Size(V)>N/2，那么我们考虑V作为根结点的情况，记Size’(X)表示此时以X为根的子树的结点个数。
如图。
对于A部分，显然Size’(Ti)<Size(V)
对于B部分，Size’(U) = N-Size(V)<Size(V)
这与树的重心定义矛盾。
定理得证。
//日后将会给出一些例题去运用以上的结论
转载请注明：http://www.cnblogs.com/ECJTUACM-873284962/