简介
点分治主要解决树上路径问题,其主要思想是把一颗有根树以根为分治点分为一个森林(其实就是各个子树),解决经过当前根的路径后在子树里继续分治,从而将问题“分而治之”。
这里面,根的选择非常重要。为了保证复杂度,我们的分治点应该尽可能的“居中”,所以分治点一般选择正在处理的树的重心。
套路
- 找到当前树的重心作为根
- 解决通过这个根的路径的答案(一般有两种方法,一种是通过与子树容斥,一种是直接计算子树贡献)
- 递归解决子树
实现
求重心
1 | //root = 0, mxson[0] = INF, sum = n; |
size[]是子树大小,mxson[]是最大子树大小,root是重心,sum是当前整颗树的大小
注意每次 findRoot() 前要初始化 root 和 sum
分治计算
1 | void solve(int x){ |
vis[]标记此点是否计算过,cal()计算以x为根、经过根的路径的答案
注意事项
不要再分治时用memset O(n) 地进行初始化,否则点分治好不容易保证的复杂度就被毁了。
练习
poj1741 tree
题意
给一棵树,边有边权,问两点之间的距离小于等于K的点对有多少个。
题解
点分治时用容斥做:计算以x为根的子树时直接将求得的dis排序后O(n)求答案,然后再减去每个子树中被统计了的不合法答案
Code
1 |
|
luogu3806 【模板】点分治1
题意
给定一棵有n个点的树,多次询问树上距离为k的点对是否存在。
题解
和上一题差不多,也是容斥,只不过我们把所有k的答案一次性求出来,每次询问O(1)回答。
Code
1 |
|
[国家集训队] 聪聪可可
题意
求边权和是3的倍数的点对个数
题解
思路和上面两道题大同小异,而且更简单了:不用对dis排序,只需记录下距当前根dis为0,1,2的点的个数(cnt),则答案就是cnt[0]∗cnt[0]+cnt[1]∗cnt[2]∗2
当然这样做也要容斥
Code
1 |
|
[IOI]Race
题意
给一棵树,每条边有权。求一条简单路径,权值和等于 K ,且边的数量最小。输出最小边数
题解
发现这道不能容斥…所以我们想办法通过子树信息直接计算经过分治点的路径的答案
记tmp[i]为当前子树中,路径长为i的最小边数,于是对于当前根x,我们每次遍历它的子树,先用tmp[]和正在遍历的子树更新答案(代码中的 updAns() 函数),再用正在遍历的这颗子树更新tmp[](代码中的 updTmp() 函数),这样就保证了不会把不合法的路径算进来
Code
1 |
|
—— 完 ——