树上处理的问题总结

树的直径

也就是树的最长路径的长度

做法

求2次DFS,第一次DFS找到当前距离根节点最远的点(叶节点),然后以这个点出发再做一次DFS,找到最远的点。可以证明这个距离即是树上的最长路径。

树的重心

为了防止出现一个顶点下链接了一条大长链会导致一些在树上的分治处理可能出现的问题,我们需改变根节点的位置(例如此时把根节点放在中间就比较好)

树的重心有下面几条常见性质:

定义1:找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心。
定义2:以这个点为根,那么所有的子树(不算整个树自身)的大小都不超过整个树大小的一半。
性质1:树中所有点到某个点的距离和中,到重心的距离和是最小的;如果有两个重心,那么他们的距离和一样。
性质2:把两个树通过一条边相连得到一个新的树,那么新的树的重心在连接原来两个树的重心的路径上。
性质3:把一个树添加或删除一个叶子,那么它的重心最多只移动一条边的距离。

做法
做一次DFS(两次也可以),求出所有顶点有多少子节点(包括自己),同时计算每个点的balance,是所有子树i中son[i]的最大值或者是父节点的那个森林的点数(也就是n-son[k]),从中取一个最大的。
最终的重心就是所有节点中的bal最小的那个节点。

poj1655:
定义树的balance为删去顶点i之后的森林中顶点个数最大的值。求这个点(重心)与它的balance值.

点分治

树的点的分治:首先选取一个点将无根树转为有根树,再递归处理每一颗以根结点的儿子为根的子树。

《树上处理的问题总结》

树的点的分治:首先选取一个点将无根树转为有根树,再递归处理每一颗以根结点的儿子为根的子树。

首先我们考虑如何选取点。对于基于点的分治,我们选取一个点,要求将其删去后,结点最多的树的结点个数最小,这个点就是树的重心。

在基于点的分治中每次我们都会将树的结点个数减少一半,因此递归深度最坏是 O(NlogN) 的,在树是一条链的时候达到上界。

poj1741:
楼教主男人八题中的一题,实现起来比看上去感觉要麻烦些。
求树上小于等于K的点对有多少。

每个点对都可以看做是在某个根节点的“领导下”。然后为了退化,我们每次做某个根的时候,都需要找到树的重心进行分治。把所有点到根节点的距离存到一个数组里并进行排序,然后运用经典的O(n)相向搜索进行处理,不过要减去没有经过根节点的,因为这个之后在另一个根节点也计算了。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注