BuringStraw

BuringStraw

主页归档

点分治

#点分治74
AI 生成的摘要
标题：点分治 日期：2019-06-04 13:56:00 标签：[点分治] 链接：41 点分治是一种用于求解树上路径问题的算法，例如计算点之间路径长度为k的数量。其主要步骤包括：首先确定树的重心，以减少树的层数，避免超时（TLE）。算法中使用了递归方法来计算每个节点的子树大小和最大子树大小，并通过深度优先搜索（DFS）来获取路径长度。最后，通过分治的方式解决问题，确保高效性。

点分治#

听大佬说淀粉质可好吃了然后去做题的我

image

作用#

用来求树上的路径问题

比如求有多少个点之间的路径长度为 k 之类的。

步骤#

  • 首先求重心，以保证这棵树的层数较少，防止 TLE

    • void getG(int p, int fa) {
    treeSize[p] = 1;//以当前节点为根的子树大小
    sonLargest[p] = 0;//某节点最大的子树大小
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y != fa && (v[y] == 0)) {
            getG(y, p);
            treeSize[p] += treeSize[y];
            sonLargest[p] = max(sonLargest[p], treeSize[y]);
        }
    }
    sonLargest[p] = max(sonLargest[p], sizeTot - treeSize[p] + 1);//把爸爸作为子树也是一种情况（我自己感觉这里要加个 1 但是其他大佬的代码都没加）（虽然好像并没有什么影响）
    if (sonLargest[p] < sonLargest[root]) root = p;
}

  • 然后从重心开始递归求解

    • void solve(int u) {
    v[u] = 1;
    ans += calc(u, 0);//计算当前节点为根，左儿子里的的节点连到右儿子里的节点的路径情况
    for (int i = head[u]; i; i = e[i].nex) {
        int y = e[i].to;
        if (!v[y]) {
            ans -= calc(y, e[i].w);//去重
            sonLargest[0] = sizeTot = treeSize[u];
            root = 0;
            getG(y, 0);
            solve(root);
        }
    }
}

    • 去重大概去的是这样的情况

      image

  • 左儿子 —— 根 —— 右儿子路径求解

    • 这个要看具体题目

    • //这是一个求比 k 短的路径的例子
int calc (int p, int de) {
	newd = 0;
	int ans = 0;
    getDep(p, 0, de);
    sort(dep + 1, dep + 1 + newd);
	int l = 1, r = newd;
	while (l < r) {
		if (dep[l] + dep[r] <= k) {
			ans += r - l;
			++l;
		}
		else {
			--r;
		}
	}
	return ans;
}

    • getDep 用来求从 p 到 p 的儿子们的距离

       void getDep(int p, int fa, int l) {//l为根到p的距离
     dep[++newd] = l;
     for (int i = head[p]; i; i = e[i].nex) {
         int y = e[i].to;
         if (y !=fa && (!v[y])) {
             getDep(y, p, l + e[i].w);
         }
     }
 }

例题#

全是洛谷的

P3806 【模板】点分治 1#

模板题

把询问离线，在 calc 时两两枚举点对，统计所有可能的结果

#include<cstdio>
#include<ctime>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

const int MAXN=40000 * 2 + 5, INF=0x3f3f3f3f;

struct ed {
    int to,w,nex;
} e[MAXN];

int dep[MAXN];
int newp, root, sizeTot,newd;
int n, m, k;
int ans[10000000 + 5];
int head[MAXN], dist[MAXN];
int treeSize[MAXN], sonLargest[MAXN]={INF};
bool v[MAXN];

void lineAdd (int p1, int p2, int w);
void getG (int v, int fa);
void getDep (int p, int fa, int l);
void solve (int u);
void calc (int p, int de, int add);

int main(void) {
    #ifndef ONLINE_JUDGE
    long _begin_time = clock();
    freopen("in.txt","r",stdin);
    freopen("out.txt", "w", stdout);
    #endif

    scanf("%d%d", &n, &m);
    sizeTot = sonLargest[0] = n;
    for (int i = 1; i < n; ++i) {
        int p1, p2, w;
        scanf("%d%d%d", &p1, &p2, &w);
        lineAdd(p1, p2, w);
        lineAdd(p2, p1, w);
    }
    getG(1, 0);
    //memset(v, 0, sizeof(v));
    solve(root);
    for(int i = 1; i <= m; ++i) {
        scanf("%d", &k);
        printf("ans[k] > 0?"AYE\n":"NAY\n");
    }

    #ifndef ONLINE_JUDGE
    long _end_time = clock();
    cout << "time = " << _end_time - _begin_time << "ms" <<endl;
    #endif
    return 0;
}

void lineAdd(int p1, int p2, int w) {
    ++newp;
    e[newp].w = w;
    e[newp].to = p2;
    e[newp].nex = head[p1];
    head[p1] = newp;
}

void getG(int p, int fa) {
    treeSize[p] = 1;
    sonLargest[p] = 0;
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y != fa && (v[y] == 0)) {
            getG(y, p);
            treeSize[p] += treeSize[y];
            sonLargest[p] = max(sonLargest[p], treeSize[y]);
        }
    }
    sonLargest[p] = max(sonLargest[p], sizeTot - treeSize[p] + 1);
    if (sonLargest[p] < sonLargest[root]) root = p;
}

void getDep(int p, int fa, int l) {
    dep[++newd] = l;
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y !=fa && (!v[y])) {
            getDep(y, p, l + e[i].w);
        }
    }
}

void solve(int u) {
    v[u] = 1;
    calc(u, 0, 1);
    for (int i = head[u]; i; i = e[i].nex) {
        int y = e[i].to;
        if (!v[y]) {
            calc(y, e[i].w, -1);
            sonLargest[0] = sizeTot = treeSize[u];
            root = 0;
            getG(y, 0);
            solve(root);
        }
    }
}

void calc (int p, int de, int add) {
	newd = 0;
    getDep(p, 0, de);
    for (int i = 1; i <= newd; ++i) {
        for (int j = 1; j <= newd; ++j) {
            ans[dep[i] + dep[j]] += add;
        }
    }
}

P2634 聪聪可可#

getDep 时用dep[0]记录整除，dep[1]记录余数为 1 的。。。。。。

calc 中答案等于 dep[0] * dep[0] + dep[1] * dep[2] * 2

#include<cstdio>
#include<ctime>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define clear(a) memset(a, 0, sizeof(a))
using namespace std;

const int MAXN=40000 * 2 + 5, INF=0x3f3f3f3f;

struct ed {
    int to,w,nex;
} e[MAXN];

int dep[MAXN];
int newp, root, sizeTot,newd;
int n, m, k;
int ans;
int head[MAXN], dist[MAXN];
int treeSize[MAXN], sonLargest[MAXN]={INF};
bool v[MAXN];

void lineAdd (int p1, int p2, int w);
void getG (int v, int fa);
void getDep (int p, int fa, int l);
void solve (int u);
int calc (int p, int de);
int gcd (int p1, int p2) {return (p2 % p1 == 0) ? p1 : gcd(p2 % p1, p1);}

int main(void) {
    #ifndef ONLINE_JUDGE
    long _begin_time = clock();
    freopen("in.txt","r",stdin);
    freopen("out.txt", "w", stdout);
    #endif
    scanf("%d", &n);
    sizeTot = sonLargest[0] = n;
    for (int i = 1; i < n; ++i) {
        int p1, p2, w;
        scanf("%d%d%d", &p1, &p2, &w);
        lineAdd(p1, p2, w);
        lineAdd(p2, p1, w);
    }
    getG(1, 0);
    solve(root);
    int fenMu = n * n;
    int g = gcd(ans, fenMu);
    printf("%d/%d\n", ans / g, fenMu / g);

    #ifndef ONLINE_JUDGE
    long _end_time = clock();
    cout << "time = " << _end_time - _begin_time << "ms" <<endl;
    #endif
    return 0;
}

void lineAdd(int p1, int p2, int w) {
    ++newp;
    e[newp].w = w;
    e[newp].to = p2;
    e[newp].nex = head[p1];
    head[p1] = newp;
}

void getG(int p, int fa) {
    treeSize[p] = 1;
    sonLargest[p] = 0;
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y != fa && (v[y] == 0)) {
            getG(y, p);
            treeSize[p] += treeSize[y];
            sonLargest[p] = max(sonLargest[p], treeSize[y]);
        }
    }
    sonLargest[p] = max(sonLargest[p], sizeTot - treeSize[p] + 1);
    if (sonLargest[p] < sonLargest[root]) root = p;
}

void getDep(int p, int fa, int l) {
    ++dep[l % 3];
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y !=fa && (!v[y])) {
            getDep(y, p, (l + e[i].w) % 3);
        }
    }
}

void solve(int u) {
    v[u] = 1;
    ans += calc(u, 0);
    for (int i = head[u]; i; i = e[i].nex) {
        int y = e[i].to;
        if (!v[y]) {
            ans -= calc(y, e[i].w);
            sonLargest[0] = sizeTot = treeSize[u];
            root = 0;
            getG(y, 0);
            solve(root);
        }
    }
}

int calc (int p, int de) {
    dep[0] = dep[1] = dep[2] = 0;
    getDep(p, 0, de);
    int ans = dep[0] * dep[0] + dep[1] * dep[2] * 2;
    return ans;
}

P4178 Tree#

这道题 calc 统计时不能暴力枚举，否则全 TLE

#include<cstdio>
#include<ctime>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

const int MAXN=40000 * 2 + 5, INF=0x3f3f3f3f;

struct ed {
    int to,w,nex;
} e[MAXN];

int dep[MAXN];
int newp, root, sizeTot,newd;
int n, m, k;
int ans;
int head[MAXN], dist[MAXN];
int treeSize[MAXN], sonLargest[MAXN]={INF};
bool v[MAXN];

void lineAdd (int p1, int p2, int w);
void getG (int v, int fa);
void getDep (int p, int fa, int l);
void solve (int u);
int calc (int p, int de);

int main(void) {
    #ifndef ONLINE_JUDGE
    long _begin_time = clock();
    freopen("in.txt","r",stdin);
    freopen("out.txt", "w", stdout);
    #endif

    scanf("%d", &n);
    sizeTot = sonLargest[0] = n;
    for (int i = 1; i < n; ++i) {
        int p1, p2, w;
        scanf("%d%d%d", &p1, &p2, &w);
        lineAdd(p1, p2, w);
        lineAdd(p2, p1, w);
    }
    scanf("%d", &k);
    getG(1, 0);
    solve(root);
	printf("%d\n", ans);

    #ifndef ONLINE_JUDGE
    long _end_time = clock();
    cout << "time = " << _end_time - _begin_time << "ms" <<endl;
    #endif
    return 0;
}

void lineAdd(int p1, int p2, int w) {
    ++newp;
    e[newp].w = w;
    e[newp].to = p2;
    e[newp].nex = head[p1];
    head[p1] = newp;
}

void getG(int p, int fa) {
    treeSize[p] = 1;
    sonLargest[p] = 0;
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y != fa && (v[y] == 0)) {
            getG(y, p);
            treeSize[p] += treeSize[y];
            sonLargest[p] = max(sonLargest[p], treeSize[y]);
        }
    }
    sonLargest[p] = max(sonLargest[p], sizeTot - treeSize[p] + 1);
    if (sonLargest[p] < sonLargest[root]) root = p;
}

void getDep(int p, int fa, int l) {
    dep[++newd] = l;
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y !=fa && (!v[y])) {
            getDep(y, p, l + e[i].w);
        }
    }
}

void solve(int u) {
    v[u] = 1;
    ans += calc(u, 0);
    for (int i = head[u]; i; i = e[i].nex) {
        int y = e[i].to;
        if (!v[y]) {
            ans -= calc(y, e[i].w);
            sonLargest[0] = sizeTot = treeSize[u];
            root = 0;
            getG(y, 0);
            solve(root);
        }
    }
}

int calc (int p, int de) {
	newd = 0;
	int ans = 0;
    getDep(p, 0, de);
    sort(dep + 1, dep + 1 + newd);
	int l = 1, r = newd;
	while (l < r) {
		if (dep[l] + dep[r] < k) {
			ans += r - l;
			++l;
		}
		else {
			--r;
		}
	}
	return ans;
}
加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。