2020-2021:teams:legal_string:jxm2001:静态点分治
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:静态点分治 [2020/05/24 17:57] jxm2001 |
2020-2021:teams:legal_string:jxm2001:静态点分治 [2020/07/26 15:53] (当前版本) jxm2001 ↷ 页面2020-2021:teams:legal_string:静态点分治被移动至2020-2021:teams:legal_string:jxm2001:静态点分治 |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| ===== 算法简介 ===== | ===== 算法简介 ===== | ||
| - | 一种利用分治进行树上路径统计的算法，算法时间复杂度一般为 $O(n\log n)$ | + | 一种利用分治进行树上路径统计的算法，算法时间复杂度一般为 $O(n\log n)$。 |
| ===== 算法思想 ===== | ===== 算法思想 ===== | ||
| - | 所有路径分为两种，一种是过根结点的，一种是完全在根结点的某棵子树中的 | + | 所有路径分为两种，一种是过根结点的，一种是完全在根结点的某棵子树中的。 |
| - | 因此可以考虑分治算法，选取一个点将无根树转换为有根树，然后递归处理每个棵以根节点的儿子为根的子树 | + | 因此可以考虑分治算法，选取一个点将无根树转换为有根树，然后递归处理每个棵以根节点的儿子为根的子树。 |
| - | 如果选取树的重心作为根结点，则每棵子树的结点个数不超过 $\frac n2$ ，可以保证递归深度不超过 $\log n$ | + | 如果选取树的重心作为根结点，则每棵子树的结点个数不超过 $\frac n2$ ，可以保证递归深度不超过 $\log n$。 |
| - | 在这个基础上如果能在 $O\left(n\right)$ 时间维护经过根结点路径相关信息，则算法总时间复杂度为 $O(n\log n)$ | + | 在这个基础上如果能在 $O(n)$ 时间维护经过根结点路径相关信息，则算法总时间复杂度为 $O(n\log n)$。 |
| ===== 代码实现 ===== | ===== 代码实现 ===== | ||
| - | 重心的寻找可以利用树形 dp ，处理出所有结点的 $\text{sz}$ ，所有结点的最大子树 $\text{mson}\left(u\right)=\max\left(\max\left(\text{sz}\left(\text{son}\left(u\right)\right),\text{tot_sz}-\text{sz}\left(u\right)\right)\right)$ | + | 重心的寻找可使用 dfs，处理出所有结点的 $\text{sz}$ ，所有结点的最大子树 $\text{mson}(u)=\max\left(\max\left(\text{sz}\left(\text{son}\left(u\right)\right),\text{tot_sz}-\text{sz}\left(u\right)\right)\right)$。 |
| - | 不断更新 $\text{mson}$ 最小的结点，最后便可以得到重心，时间复杂度 $O(n)$ | + | 不断更新 $\text{mson}$ 最小的结点，最后便可以得到重心，时间复杂度 $O(n)$。 |
| - | 分治过程需要注意标记已经访问的结点，同时更新子树大小 $\text{tot_sz}$ ，具体实现见模板 | + | 分治过程需要注意标记已经访问的结点，同时更新子树大小 $\text{tot_sz}$ ，具体实现见模板。 |
| ===== 代码模板 ===== | ===== 代码模板 ===== | ||
| - | <hidden 查看代码> | + | <hidden 代码> |
| <code cpp> | <code cpp> | ||
| int sz[MAXN],mson[MAXN],tot_sz,root,root_sz; | int sz[MAXN],mson[MAXN],tot_sz,root,root_sz; | ||
| 行 46: | 行 46: | ||
| } | } | ||
| void solve(int u){ | void solve(int u){ | ||
| + | int cur_sz=tot_sz; | ||
| vis[u]=true;query(u); | vis[u]=true;query(u); | ||
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| 行 51: | 行 52: | ||
| if(vis[v]) | if(vis[v]) | ||
| continue; | continue; | ||
| - | tot_sz=sz[v];root_sz=inf; | + | tot_sz=sz[v]>sz[u]?cur_sz-sz[u]:sz[v];root_sz=MAXN; |
| find_root(v,u); | find_root(v,u); | ||
| solve(root); | solve(root); | ||
| 行 64: | 行 65: | ||
| [[https://www.luogu.com.cn/problem/P3806|洛谷p3806]] | [[https://www.luogu.com.cn/problem/P3806|洛谷p3806]] | ||
| - | 题目大意是说给定一棵 $n$ 个结点的正权树，多次查询，每次查询是否存在长度为 $k$ 的路径 | + | 题目大意是说给定一棵 $n$ 个结点的正权树，多次查询，每次查询是否存在长度为 $k$ 的路径。 |
| - | 对根结点，先考虑暴力法，用树形 dp 求出子树上各节点到根结点的距离，然后两两枚举，看看有没有两个结点距离和为 $k$ | + | 对根结点，先考虑暴力法，用树形 dp 求出子树上各节点到根结点的距离，然后两两枚举，看看有没有两个结点距离和为 $k$。 |
| - | 这样每层递归的时间复杂度是 $O\left(n^2\right)$ ，显然会 T | + | 这样每层递归的时间复杂度是 $O(n^2)$，显然会 T。 |
| - | 考虑用中途相遇法，可以将每层递归的时间复杂度优化到 $O(n)$ ，单次查询时间复杂度 $O(n\log n)$ | + | 考虑用中途相遇法，可以将每层递归的时间复杂度优化到 $O(n)$，单次查询时间复杂度 $O(n\log n)$。 |
| - | 但要注意三点 | + | 但要注意三点： |
| - | 一、枚举过根结点的路径时路径两端点显然不能在同一棵子树里，所以要先求出一棵子树所有的 $\text{dist}$ ，全部判断完后再进行标记 | + | 一、枚举过根结点的路径时路径两端点显然不能在同一棵子树里，所以要先求出一棵子树所有的 $\text{dist}$，全部判断完后再进行标记。 |
| - | 二、题目给定 $k\le 10^7$ ，所以不用标记大于 $10^7$ 的 $\text{dist}$ | + | 二、题目给定 $k\le 10^7$，所以不用标记大于 $10^7$ 的 $\text{dist}$。 |
| - | 三、清空标记不能用 $\text{memset}$ ，会 T ，这里开了一个 $\text{vector}$ 来记录之前的标记 | + | 三、清空标记不能用 $\text{memset}$，会 T，这里开了一个 $\text{vector}$ 来记录之前的标记。 |
| 另一个优化是可以离线处理查询，这样只需要分治一次，可以减小常数。 | 另一个优化是可以离线处理查询，这样只需要分治一次，可以减小常数。 | ||
| - | <hidden 查看代码> | + | <hidden 代码> |
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <cctype> | ||
| - | #include <vector> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | using namespace std; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| const int MAXN=1e4+5,inf=1e7+5; | const int MAXN=1e4+5,inf=1e7+5; | ||
| struct Edge{ | struct Edge{ | ||
| 行 139: | 行 129: | ||
| void query(int u){ | void query(int u){ | ||
| sd.clear(); | sd.clear(); | ||
| + | mark[0]=true; | ||
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| d.clear(); | d.clear(); | ||
| 行 162: | 行 153: | ||
| } | } | ||
| void solve(int u){ | void solve(int u){ | ||
| - | vis[u]=mark[0]=true;query(u); | + | int cur_sz=tot_sz; |
| + | vis[u]=true;query(u); | ||
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| int v=edge[i].to; | int v=edge[i].to; | ||
| if(vis[v]) | if(vis[v]) | ||
| continue; | continue; | ||
| - | tot_sz=sz[v];root_sz=inf; | + | tot_sz=sz[v]>sz[u]?cur_sz-sz[u]:sz[v];root_sz=MAXN; |
| find_root(v,u); | find_root(v,u); | ||
| solve(root); | solve(root); | ||
| 行 201: | 行 193: | ||
| [[https://www.luogu.com.cn/problem/P4149|洛谷p4149]] | [[https://www.luogu.com.cn/problem/P4149|洛谷p4149]] | ||
| - | 给一棵树，每条边有权。求一条简单路径，权值和等于 $q$ ，且边的数量最小。 | + | 给一棵树，每条边有权。求一条简单路径，权值和等于 $q$，且边的数量最小。 |
| - | 类似习题1，开个 $\text{mark}$ 数组存一下到根结点距离为 $\text{dist}$ 的路径的最短边数 | + | 类似习题1，开个 $\text{mark}$ 数组存一下到根结点距离为 $\text{dist}$ 的路径的最短边数。 |
| - | $\text{vector}$ 不仅要记录距离，还要记录深度，时间复杂度 $O(n\log n)$ | + | $\text{vector}$ 不仅要记录距离，还要记录深度，时间复杂度 $O(n\log n)$。 |
| - | <hidden 查看代码> | + | <hidden 代码> |
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <cctype> | ||
| - | #include <vector> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | using namespace std; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| const int MAXN=2e5+5,inf=1e6+5; | const int MAXN=2e5+5,inf=1e6+5; | ||
| struct Edge{ | struct Edge{ | ||
| 行 285: | 行 266: | ||
| } | } | ||
| void solve(int u){ | void solve(int u){ | ||
| + | int cur_sz=tot_sz; | ||
| vis[u]=true;query(u); | vis[u]=true;query(u); | ||
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| 行 290: | 行 272: | ||
| if(vis[v]) | if(vis[v]) | ||
| continue; | continue; | ||
| - | tot_sz=sz[v];root_sz=MAXN; | + | tot_sz=sz[v]>sz[u]?cur_sz-sz[u]:sz[v];root_sz=MAXN; |
| find_root(v,u); | find_root(v,u); | ||
| solve(root); | solve(root); | ||
| 行 322: | 行 304: | ||
| [[https://www.luogu.com.cn/problem/P4178|洛谷p4178]] | [[https://www.luogu.com.cn/problem/P4178|洛谷p4178]] | ||
| - | 给定一棵 $n$ 个结点的正权树和一个正数 $k$ ，统计有多少对结点 $(a,b)$ 满足 $\text{dist}(a,b)\le k$ | + | 给定一棵 $n$ 个结点的正权树和一个正数 $k$，统计有多少对结点 $(a,b)$ 满足 $\text{dist}(a,b)\le k$。 |
| - | 把中途相遇法换成树状数组或名次树即可，时间复杂度 $O\left(n\log^2 n\right)$ | + | 把中途相遇法换成树状数组或名次树即可，时间复杂度 $O(n\log^2 n)$。 |
| ==== 习题4 ==== | ==== 习题4 ==== | ||
| 行 330: | 行 312: | ||
| [[https://www.luogu.com.cn/problem/UVA12161|UVA12161]] | [[https://www.luogu.com.cn/problem/UVA12161|UVA12161]] | ||
| - | 给定一棵 $n$ 个结点的树,每条边包含长度 $L$ 和费用 $D (1\le D,L \le 1000)$ 。选择一条总费用不超过 $m$ 的路径，使得路径总长度最大。 | + | 给定一棵 $n$ 个结点的树，每条边包含长度 $L$ 和费用 $D (1\le D,L \le 1000)$ 。选择一条总费用不超过 $m$ 的路径，使得路径总长度最大。 |
| - | 考虑单调队列，时间复杂度 $O\left(n\log^2 n\right)$ 。另外本题存在 $O\left(n\log n\right)$ 解法，有兴趣的可以自己尝试 | + | 考虑过根结点的路径，枚举到结点 $i$ 时，设它到根结点的路径费用为 $c(i)$。 |
| + | |||
| + | 需要在已经枚举的其他子树中的结点中选取费用不超过 $D-c(i)$ 的最长路径。 | ||
| + | |||
| + | 对结点 $v_1$ 和 $v_2$ ，如果 $v_1$ 费用大于 $v_2$ ，长度小于 $v_2$ ，那 $v_1$ 显然不会对后续答案产生贡献。 | ||
| + | |||
| + | 因此可以考虑单调队列维护对答案有贡献的点集，总时间复杂度 $O(n\log^2 n)$。 | ||
| + | |||
| + | 另外本题存在 $O(n\log n)$ 解法，有兴趣的可以自己尝试。 | ||
| ==== 习题5 ==== | ==== 习题5 ==== | ||
| 行 338: | 行 328: | ||
| [[https://www.luogu.com.cn/problem/P2664|洛谷P2664]] | [[https://www.luogu.com.cn/problem/P2664|洛谷P2664]] | ||
| - | 给定一棵 $n$ 个结点的树，树的每个节点有个颜色 | + | 给定一棵 $n$ 个结点的树，树的每个节点有个颜色。 |
| - | 定义 $s(i,j)$ 为 $i$ 到 $j$ 的颜色数量， $sum_i=\sum_{j=1}^n s(i,j)$ ，要求输出所有 $sum_i$ | + | 定义 $s(i,j)$ 为 $i$ 到 $j$ 的颜色数量，$\text{sum}_i=\sum_{j=1}^n s(i,j)$，要求输出所有 $\text{sum}_i$。 |
| - | 这题需要计算贡献，思路较复杂，这里只给出代码供参考，时间复杂度 $O(n\log n)$ ，另外本题存在 $O(n)$ 解法，有兴趣的可以自己尝试 | + | 这题需要计算贡献，先考虑根结点，仅一端为根结点的路径对根结点的答案有贡献。 |
| - | <hidden 查看代码> | + | 考虑 dfs 处理子树，若一条路径上的某种颜色第一次出现，立刻计算它的贡献，贡献为它所在的子树大小。 |
| + | |||
| + | 经过这遍 dfs ，可以得到所有子树到根结点的贡献。 | ||
| + | |||
| + | 再考虑所有经过根结点的路径（包含一端为根结点的路径）对所有子树结点答案的影响。 | ||
| + | |||
| + | 对每棵子树上的结点而言，所有经过根结点的路径可以分为一条从其他子树到根结点的路径（也可以是空路径）和一条从根结点到该结点的路径。 | ||
| + | |||
| + | 可以考虑多次利用之前计算出的所有子树到根结点的贡献。 | ||
| + | |||
| + | 对每棵子树，先消去该子树对根结点的贡献，便可以得到所有其他子树到根结点的路径贡献。 | ||
| + | |||
| + | 再重新对该子树进行遍历，更新该子树上每个点的贡献值。 | ||
| + | |||
| + | 最后把消去子树对根结点的贡献再改回去即可。 | ||
| + | |||
| + | 总时间复杂度 $O(n\log n)$ ，另外本题存在 $O(n)$ 解法，有兴趣的可以自己尝试。 | ||
| + | |||
| + | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <cctype> | ||
| - | #include <vector> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=1e5+5; | const int MAXN=1e5+5; | ||
| struct Edge{ | struct Edge{ | ||
| 行 469: | 行 456: | ||
| } | } | ||
| void solve(int u){ | void solve(int u){ | ||
| + | int cur_sz=tot_sz; | ||
| vis[u]=true;query(u); | vis[u]=true;query(u); | ||
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| 行 474: | 行 462: | ||
| if(vis[v]) | if(vis[v]) | ||
| continue; | continue; | ||
| - | tot_sz=sz[v];root_sz=MAXN; | + | tot_sz=sz[v]>sz[u]?cur_sz-sz[u]:sz[v];root_sz=MAXN; |
| find_root(v,u); | find_root(v,u); | ||
| solve(root); | solve(root); | ||
2020-2021/teams/legal_string/jxm2001/静态点分治.1590314265.txt.gz · 最后更改: 2020/05/24 17:57 由 jxm2001
