technique:centroid_decomposition
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
technique:centroid_decomposition [2020/06/05 23:22] jxm2001 例 5 大概过程 |
technique:centroid_decomposition [2020/06/11 21:45] (当前版本) admin finish |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | **格式**：大部分已修改 | ||
| - | - 注意句号 | ||
| - | - ''\left(\right)'' 通常用于括号内部内容较多的情况 | ||
| - | - sum 建议用 ''\text'' 包裹 | ||
| - | |||
| - | **内容**： | ||
| - | - 例 4 中至少要大致描述一下单调队列维护的东西，不能太简略 | ||
| - | - 例 5 中不能只给代码，无论如何都要讲一下大致做法。 | ||
| - | - 方便的话完善一下例 4、5 中更好的解法。 | ||
| - | |||
| ====== 静态点分治 ====== | ====== 静态点分治 ====== | ||
| 行 23: | 行 13: | ||
| 如果选取树的重心作为根结点，则每棵子树的结点个数不超过 $\frac n2$ ，可以保证递归深度不超过 $\log n$。 | 如果选取树的重心作为根结点，则每棵子树的结点个数不超过 $\frac n2$ ，可以保证递归深度不超过 $\log n$。 | ||
| - | 在这个基础上如果能在 $O(n)$ 时间维护经过根结点路径相关信息，则算法总时间复杂度为 $O(n\log n)$。 | + | 在这个基础上如果能在 $O(n\log^{\alpha}n)$ 的时间内维护经过根结点路径相关信息，则算法总时间复杂度为 $O(n\log^{\alpha+1}n)$，即复杂度只增加一个 $\log$。 |
| ===== 代码实现 ===== | ===== 代码实现 ===== | ||
| - | 重心的寻找可使用 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)$。 | + | 重心的寻找可使用 ''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)$。 | ||
| 行 56: | 行 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){ | ||
| 行 61: | 行 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=inf; |
| find_root(v,u); | find_root(v,u); | ||
| solve(root); | solve(root); | ||
| 行 149: | 行 140: | ||
| 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(); | ||
| 行 172: | 行 164: | ||
| } | } | ||
| 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=inf; |
| find_root(v,u); | find_root(v,u); | ||
| solve(root); | solve(root); | ||
| 行 295: | 行 288: | ||
| } | } | ||
| 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){ | ||
| 行 300: | 行 294: | ||
| 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); | ||
| 行 342: | 行 336: | ||
| 给定一棵 $n$ 个结点的树，每条边包含长度 $L$ 和费用 $D (1\le D,L \le 1000)$ 。选择一条总费用不超过 $m$ 的路径，使得路径总长度最大。 | 给定一棵 $n$ 个结点的树，每条边包含长度 $L$ 和费用 $D (1\le D,L \le 1000)$ 。选择一条总费用不超过 $m$ 的路径，使得路径总长度最大。 | ||
| - | 考虑过根结点的路径，枚举到结点 $i$ 时，设它到根结点的路径费用为 $c(i)$ 。 | + | 考虑过根结点的路径，枚举到结点 $i$ 时，设它到根结点的路径费用为 $c(i)$。 |
| 需要在已经枚举的其他子树中的结点中选取费用不超过 $D-c(i)$ 的最长路径。 | 需要在已经枚举的其他子树中的结点中选取费用不超过 $D-c(i)$ 的最长路径。 | ||
| 行 348: | 行 342: | ||
| 对结点 $v_1$ 和 $v_2$ ，如果 $v_1$ 费用大于 $v_2$ ，长度小于 $v_2$ ，那 $v_1$ 显然不会对后续答案产生贡献。 | 对结点 $v_1$ 和 $v_2$ ，如果 $v_1$ 费用大于 $v_2$ ，长度小于 $v_2$ ，那 $v_1$ 显然不会对后续答案产生贡献。 | ||
| - | 因此可以考虑单调队列维护对答案有贡献的点集，总时间复杂度 $O(n\log^2 n)$ 。 | + | 因此可以考虑单调队列维护对答案有贡献的点集，总时间复杂度 $O(n\log^2 n)$。 |
| 另外本题存在 $O(n\log n)$ 解法，有兴趣的可以自己尝试。 | 另外本题存在 $O(n\log n)$ 解法，有兴趣的可以自己尝试。 | ||
| 行 505: | 行 499: | ||
| } | } | ||
| 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){ | ||
| 行 510: | 行 505: | ||
| 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); | ||
technique/centroid_decomposition.1591370551.txt.gz · 最后更改: 2020/06/05 23:22 由 jxm2001
