BuringStraw

BuringStraw

HomeArchives

Point Division

#点分治64
AI Translation
This post is translated from Chinese into English through AI.View Original
AI-generated summary
The "Divide and Conquer" algorithm is used to solve path problems on trees by finding the centroid of the tree and then recursively solving subproblems on each subtree.

Centroid Decomposition#

I heard from the experts that starchy foods are delicious, so I went to solve problems.

image

Purpose#

Used to solve path problems on trees.

For example, to find how many paths between points have a length of k.

Steps#

  • First, find the centroid to ensure that the tree has fewer levels, preventing TLE.

    • void getG(int p, int fa) {
    treeSize[p] = 1; // Size of the subtree rooted at the current node
    sonLargest[p] = 0; // Size of the largest subtree of a node
    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); // Considering the parent as a subtree is also a case (I feel like we need to add 1 here, but other experts' codes do not add it) (although it seems to have no effect)
    if (sonLargest[p] < sonLargest[root]) root = p;
}

  • Then recursively solve starting from the centroid.

    • void solve(int u) {
    v[u] = 1;
    ans += calc(u, 0); // Calculate the path situation where the current node is the root, connecting nodes in the left child to nodes in the right child
    for (int i = head[u]; i; i = e[i].nex) {
        int y = e[i].to;
        if (!v[y]) {
            ans -= calc(y, e[i].w); // Deduplication
            sonLargest[0] = sizeTot = treeSize[u];
            root = 0;
            getG(y, 0);
            solve(root);
        }
    }
}

    • Deduplication generally removes such situations.

      image

  • Path calculation from left child — root — right child.

    • This depends on the specific problem.

    • // This is an example of finding paths shorter than 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 is used to find the distance from p to its children.

       void getDep(int p, int fa, int l) { // l is the distance from root to 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);
         }
     }
 }

Example Problems#

All from Luogu.

P3806 【Template】Centroid Decomposition 1#

Template problem.

Make the queries offline, and during calc, enumerate pairs of points to count all possible results.

#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 Congcong Keke#

In getDep, use dep[0] to record multiples, and dep[1] to record remainders of 1...

In calc, the answer equals 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#

In this problem, calc cannot use brute force enumeration, otherwise it will 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;
}
Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.