Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

点分治

发布于：Jun 4, 2019

次浏览

点分治

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

作用

用来求树上的路径问题

比如求有多少个点之间的路径长度为 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);
        }
    }
}

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

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

    • 这个要看具体题目

    • //这是一个求比 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;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://zhufn.fun/archives/41/

更新于：Aug 21, 2023

点分治

评论