點分治

點分治#

聽大佬說澱粉質可好吃了然後去做題的我

作用#

用來求樹上的路徑問題

比如求有多少個點之間的路徑長度為 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;
}

點分治#

作用#

步驟#

例題#

P3806 【模板】點分治 1#

P2634 聪聪可可#

P4178 Tree#

P3806 【模板】點分治 1 #

P2634 聪聪可可 #

P4178 Tree #