【模版】【P3806】点分治
(7.17)早就想学点分治了……今天状态不太在线,眯一会写篇笔记来理理思路。
--------------------------------------------------------------------
(静态)点分治是一种利用无根树性质暴力分治的思想,可以在O(nlogn)的复杂度下统计可带权树上的路径信息。
像是这道例题,多组询问是否存在长度为k的路径,需要我们预处理出一个储存所有路径长度信息的桶。
点分治的做法,就是选定一个合适的根节点,把树上的所有路径分成不重不漏的两部分来统计:
1、经过根节点u的路径;
2、在u某个子树中的路径。
每次分治我们会统计出第一种路径的信息,然后递归进入u的每个子树,将第二种路径看作它的子树内的子问题来求解。
首先,我们要选定一个合适的根节点开始分治。最理想的根节点要满足它的每个子树大小都基本一样大;于是我们就想起了重心这个好东西。
无根树的重心u的性质:
1、最大子树的大小最小。
2、最大的子树大小小于等于树大小的一半。
如果每次选定该子树的重心为根来进行分治,我们就可以保证递归的进行不超过logn层。
- void find_rt(int u, int pre) {
- size[u] = 1;
- int Mx = 0;
- for (int i = head[u]; i; i = edge[i].nxt) {
- int v = edge[i].to;
- if (v == pre || vis[v]) continue;
- find_rt(v, u);
- size[u] += size[v];
- Mx = max(Mx, size[v]);
- }
- Mx = max(Mx, Size - size[u]);
- if (Mx < Mn)
- root = u, Mn = Mx;
- }
--------------------------------------------------------------------
接下来是分治和统计的过程。O(nlogn)实际上是算法框架的复杂度,实际复杂度会随统计手段而改变。
针对这道题来说,我们通过一次暴力dfs统计出当前子树中每个点的路径信息(包括根自身,深度为0),然后继续很暴力地两两组合路径,然后就出问题了……
直接合并任意两条路径是行不通的,因为这两条路径可能来自u的同一个子节点v。此时我们得到的这条不合法路径的信息把u--->v的这条边统计了两次,所以我们要再遍历一遍它的每个子树,把这些不合法路径去掉。具体的操作可以看代码,用到了容斥原理。
- void dfs(int u, int pre, int depth) {
- chd[++tot] = depth; //记录每个子节点深度
- for (int i = head[u]; i; i = edge[i].nxt) {
- int v = edge[i].to;
- if (v == pre || vis[v])
- continue;
- dfs(v, u, depth + edge[i].w);
- }
- }
- void solve(int u, int extra, bool f) { //第三个参数表示加减
- tot = 0;
- dfs(u, 0, extra);
- if (f) {
- for (int i = 1; i <= tot; ++i)
- for (int j = i + 1; j <= tot; ++j)
- ++ans[chd[i] + chd[j]];
- } else {
- for (int i = 1; i <= tot; ++i)
- for (int j = i + 1; j <= tot; ++j)
- --ans[chd[i] + chd[j]];
- }
- }
- void divide(int u) { //分治过程
- vis[u] = true;
- solve(u, 0, 1);
- for (int i = head[u]; i; i = edge[i].nxt) {
- int v = edge[i].to;
- if (vis[v]) continue;
- solve(v, edge[i].w, 0); //第二个参数为初始的深度,保证与以u为根算出的深度统一。
- Mn = inf, Size = size[v];
- find_rt(v, 0);
- divide(root);
- }
- }
大概不管是谁看到这里都想吐槽了:这个常数大到哪里去了?每回都要多跑一遍O(n)的搜索和O(n^2)的统计,虽然复杂度没有变,但是接受不能。
实际上该题分治的过程有第二种写法,但是我还没有掌握,所以今天就先更新到这里。
--------------------------------------------------------------
(7.19)肝出了点分治的第二种写法。
我们完全可以通过直接进行不重不漏的统计来避免容斥。处理u时,我们每次跑出点u的一个子树内的所有深度,把它们计入子树深度信息的同时,与之前得到的别的子树的信息组合,统计答案。注意这里要把点u本身计入这个child数组中,深度为0,这样就涵盖了路径结尾在u的情况。
代码:
- int chd[maxn], temp, tot;
- void dfs(int u, int pre, int d) {
- chd[++tot] = d;
- for (int i = head[u]; i; i = edge[i].nxt) {
- int v = edge[i].to;
- if (v == pre || vis[v])
- continue;
- dfs(v, u, d + edge[i].w);
- }
- }
- void solve(int u, int extra) {
- temp = tot;
- dfs(u, 0, extra);
- for (register int i = temp + 1; i <= tot; ++i)
- for (register int j = 1; j <= temp; ++j)
- ++ans[chd[i] + chd[j]];
- }
- void divide(int u) {
- vis[u] = true;
- // memset(chd, 0, sizeof(chd));//直接覆盖原数组信息即可,不用拷贝也不用清空
- chd[1] = 0;
- tot = 1; //算上自己
- for (int i = head[u]; i; i = edge[i].nxt) {
- int v = edge[i].to;
- if (vis[v]) continue;
- solve(v, edge[i].w);
- }
- for (int i = head[u]; i; i = edge[i].nxt) {
- int v = edge[i].to;
- if (vis[v]) continue;
- Mn = inf, Size = size[v];
- find_rt(v, 0);
- divide(root);
- }
- }
这段代码的实测效率比上一种写法快了一倍(开O2快10倍@w@)。下面放上完整的代码:
- #include <iostream>
- #include <cstring>
- #include <cstdio>
- #define maxn 10010
- const int inf(0x3fffffff);
- using namespace std;
- template <typename T>
- void read(T &x) {
- x = 0;
- int f = 1;
- char ch = getchar();
- while (!isdigit(ch)) {
- if (ch == '-')
- f = -1;
- ch = getchar();
- }
- while (isdigit(ch)) {
- x = x * 10 + (ch ^ 48);
- ch = getchar();
- }
- x *= f;
- return;
- }
- int n, m;
- int head[maxn], top;
- struct E {
- int to, nxt, w;
- } edge[maxn << 1];
- inline void insert(int u, int v, int w) {
- edge[++top] = (E) {v, head[u], w};
- head[u] = top;
- }
- int Mn, root, Size, size[maxn], ans[10000010];
- bool vis[maxn];
- void find_rt(int u, int pre) {
- size[u] = 1;
- int Mxson = 0;
- for (int i = head[u]; i; i = edge[i].nxt) {
- int v = edge[i].to;
- if (vis[v] || v == pre)
- continue;
- find_rt(v, u);
- size[u] += size[v];
- if (size[v] > Mxson)
- Mxson = size[v];
- }
- Mxson = max(Mxson, Size - size[u]);
- if (Mxson < Mn)
- root = u, Mn = Mxson;
- }
- int chd[maxn], temp, tot;
- void dfs(int u, int pre, int d) {
- chd[++tot] = d;
- for (int i = head[u]; i; i = edge[i].nxt) {
- int v = edge[i].to;
- if (v == pre || vis[v])
- continue;
- dfs(v, u, d + edge[i].w);
- }
- }
- void solve(int u, int extra) {
- temp = tot;
- dfs(u, 0, extra);
- for (register int i = temp + 1; i <= tot; ++i)
- for (register int j = 1; j <= temp; ++j)
- ++ans[chd[i] + chd[j]];
- }
- void divide(int u) {
- vis[u] = true;
- // memset(chd, 0, sizeof(chd));//直接覆盖原数组信息即可,不用拷贝也不用清空
- chd[1] = 0;
- tot = 1; //算上自己
- for (int i = head[u]; i; i = edge[i].nxt) {
- int v = edge[i].to;
- if (vis[v]) continue;
- solve(v, edge[i].w);
- }
- for (int i = head[u]; i; i = edge[i].nxt) {
- int v = edge[i].to;
- if (vis[v]) continue;
- Mn = inf, Size = size[v];
- find_rt(v, 0);
- divide(root);
- }
- }
- int main() {
- // freopen("testdata.in.txt", "r", stdin);
- // freopen("testdata.out", "w", stdout);
- read(n), read(m);
- int u, v, w, k;
- for (register int i = 1; i < n; ++i) {
- read(u), read(v), read(w);
- insert(u, v, w), insert(v, u, w);
- }
- Size = n, Mn = inf;
- find_rt(1, 0);
- divide(root);
- for (register int i = 1; i <= m; ++i) {
- read(k);
- puts(ans[k] ? "AYE" : "NAY");
- }
- return 0;
- }
由于通过枚举每一条可行路径来n^2进行统计,这种写法有很大的局限性。例如【P4178】Tree 这道题,直接枚举统计会爆炸,需要排序和双指针扫描的技巧来成段统计可行路径。在大多数情况下还是需要使用容斥去重的方法进行点分治。
最新文章
- [转]你不需要jQuery
- struts2项目启动报错。关于jar的问题
- 第三次作业:PSP耗时
- POJ 3903
- jQuery.cookie
- jQuery实现Checkbox中项目开发全选全不选的使用
- SSAS-many 2 many one simple sample
- grep、egrep、fgrep
- 2、HTML
- Oracle内存参数配置及版本问题
- 线段树---HDU1394Minimum Inversion Number
- 武汉科技大学ACM:1005: 单位转换
- Port 8081 already in use, packager is either not running or not running correctly
- Android sdk content loader 0%的解决方案
- java实现解析二进制文件(字符串、图片)
- View requires API level 14 (current min is 8): <;GridLayout>;
- Wireshark使用介绍(二):应用Wireshark观察基本网络协议
- Linux安装mysql5.7
- fastjson对象转为json字符串日期格式变为时间戳问题
- Git 日常操作
热门文章
- python自动化测试,读取excal数据报";&#39;str&#39; object has no attribute &#39;items&#39;";问题解决
- [Luogu P3203] [HNOI2010]弹飞绵羊 (LCT维护链的长度)
- IOCP 模型1
- Netcore中简单使用MemoryCache
- leetcode99:n-queens
- Go语言如何像foreach一样有序遍历map
- 【老孟Flutter】6种极大提升Flutter开发效率的工具包
- flex-shrink值的计算
- ESP32的Linux开发环境搭建
- Spring源码之Springboot中监听器介绍