樹上點(diǎn)分治

思想

兩個(gè)點(diǎn)之間的距離無(wú)非就是兩種關(guān)系：我們約定$dis[i]$表示這個(gè)點(diǎn)到當(dāng)前根節(jié)點(diǎn)的距離

• $dis[u]+dis[v]$，在同一個(gè)根節(jié)點(diǎn)的不同子樹上。
• $dis[u]+dis[v]$，在同一個(gè)棵子樹上。

樹上點(diǎn)分治的思想就是通過(guò)改變根節(jié)點(diǎn)從而轉(zhuǎn)化任意兩點(diǎn)的距離為在同一個(gè)根節(jié)點(diǎn)下的情況。

舉個(gè)例子

當(dāng)我們選定1號(hào)節(jié)點(diǎn)作為我們的根節(jié)點(diǎn)時(shí)，我們可以簡(jiǎn)單的得到（三號(hào)節(jié)點(diǎn)的子樹上的點(diǎn)到節(jié)點(diǎn)1， 4， 2， 7的距離，也就是不在三號(hào)節(jié)點(diǎn)子樹上的點(diǎn)的距離）（4， 2子樹同理）。

通過(guò)這一步轉(zhuǎn)換我們只需要得到三號(hào)節(jié)點(diǎn)子樹上的點(diǎn)之間的距離即可，這就是分治思想的體現(xiàn)，我們可以不斷地遞歸最后只剩一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)的子樹上的點(diǎn)到其子樹上的點(diǎn)的距離就是確定的了，就是0嘛，只可能是它自己到它自己。

所以簡(jiǎn)而言之，點(diǎn)分治就是去不斷地遞歸某個(gè)節(jié)點(diǎn)地子樹，知道沒(méi)有子樹。

假如我們的點(diǎn)是連接成一串的，我們能任選一個(gè)點(diǎn)去當(dāng)初始節(jié)點(diǎn)的子樹嗎？

這里顯然是不能的，當(dāng)我們選定的節(jié)點(diǎn)剛好是端點(diǎn)的時(shí)候，這個(gè)時(shí)候復(fù)雜度將會(huì)變成$n^2$，這完全違背了我們優(yōu)化其的初衷。

于是這里有一個(gè)簡(jiǎn)單的優(yōu)化方法，就是每次我們選取每顆子樹的重心去充當(dāng)根節(jié)點(diǎn)，這樣的分治效果顯然是最優(yōu)的。

于是我們的樹上點(diǎn)分治算法好像已近逐漸可以寫出來(lái)了，我們通過(guò)下面這個(gè)例子來(lái)更加理解一下實(shí)現(xiàn)過(guò)程吧。

P3806 【模板】點(diǎn)分治1 + 代碼

/*樹上點(diǎn)分治 */#include <bits/stdc++.h>using namespace std;const int INF = 0x3f3f3f3f; const int N = 1e5 + 10;int head[N], to[N << 1], nex[N << 1], value[N << 1], cnt = 1; int sz[N], maxsz[N], dis[N], pre[N], vis[N], judge[10000010], is_true[110], query[110], q[N]; int n, m, sum, root;inline int read() {int f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }void get_root(int rt, int fa) {//簡(jiǎn)單的找重心sz[rt] = 1, maxsz[rt] = 0;for(int i = head[rt]; i; i = nex[i]) {if(vis[to[i]] || to[i] == fa) continue;//加了一個(gè)vis判斷，防止跑到已經(jīng)訪問(wèn)過(guò)的根節(jié)點(diǎn)給上去。get_root(to[i], rt);maxsz[rt] = max(maxsz[rt], sz[to[i]]);sz[rt] += sz[to[i]];}maxsz[rt] = max(maxsz[rt], sum - sz[rt]);if(maxsz[rt] < maxsz[root]) root = rt; }void get_dis(int rt, int fa) {//就是dfs樹上最短路的實(shí)現(xiàn)過(guò)程。pre[++pre[0]] = dis[rt];//記錄其子樹的每個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的距離。for(int i = head[rt]; i; i = nex[i]) {if(to[i] == fa || vis[to[i]]) continue;dis[to[i]] = dis[rt] + value[i];get_dis(to[i], rt);} }void calc(int rt) {//核心。int p = 0;for(int i = head[rt]; i; i = nex[i]) {if(vis[to[i]]) continue;//同樣的也是訪問(wèn)子樹。dis[to[i]] = value[i];//這里一定要記得重置。pre[0] = 0;get_dis(to[i], rt);for(int j = 1; j <= pre[0]; j++)//查詢有沒(méi)有點(diǎn)到當(dāng)前子樹的點(diǎn)的距離是符合query中的要求的。for(int k = 1; k <= m; k++)if(query[k] >= pre[j])is_true[k] |= judge[query[k] - pre[j]];for(int j = 1; j <= pre[0]; j++)//記錄我們judge中被標(biāo)記的點(diǎn)，方便在下一次分治之前重置。if(pre[j] <= 1e7 + 5)//特判一下吧，題目的dis可能會(huì)到1e8，為了防止數(shù)組越界，q[++p] = pre[j], judge[pre[j]] = 1;}for(int i = 1; i <= p; i++)//不用memset重置，防止變成n^2的算法。judge[q[i]] = 0; }void solve(int rt) {vis[rt] = judge[0] = 1;//置這個(gè)點(diǎn)被訪問(wèn)過(guò)，防止其子樹上的點(diǎn)再次訪問(wèn)這個(gè)點(diǎn)。calc(rt);for(int i = head[rt]; i; i = nex[i]) {if(vis[to[i]]) continue;//我們肯定是找一個(gè)沒(méi)有訪問(wèn)的子樹上的點(diǎn)去進(jìn)行下一次分治遞歸。sum = sz[to[i]], root = 0;maxsz[root] = INF;get_root(to[i], 0);solve(root);} }void add(int x, int y, int w) {to[cnt] = y;nex[cnt] = head[x];value[cnt] = w;head[x] = cnt++; }int main() {// freopen("in.txt", "r", stdin);n = read(), m = read();int x, y, w;for(int i = 1; i < n; i++) {//雙向建邊。x = read(), y = read(), w = read();add(x, y, w);add(y, x, w);}for(int i = 1; i <= m; i++)query[i] = read();root = 0;//尋找初始的遞歸根節(jié)點(diǎn)。maxsz[root] = INF;get_root(1, 0);solve(root);for(int i = 1; i <= m; i++)puts(is_true[i] ? "AYE" : "NAY");return 0; }

[國(guó)家集訓(xùn)隊(duì)]聰聰可可

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h>#define mp make_pair #define pb push_back #define endl '\n' #define mid (l + r >> 1) #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define ls rt << 1 #define rs rt << 1 | 1using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }const int N = 2e4 + 10;int head[N], to[N << 1], nex[N << 1], value[N << 1], cnt = 1;int sz[N], visit[N], msz[N], dis[N], pre[N], now[N], tot, root, n, m, sum, ans;void add(int x, int y, int w) {to[cnt] = y;nex[cnt] = head[x];value[cnt] = w;head[x] = cnt++; }void get_root(int rt, int fa) {sz[rt] = 1, msz[rt] = 0;for(int i = head[rt]; i; i = nex[i]) {if(to[i] == fa || visit[to[i]]) continue;get_root(to[i], rt);sz[rt] += sz[to[i]];msz[rt] = max(msz[rt], sz[to[i]]);}msz[rt] = max(msz[rt], sum - sz[rt]);if(msz[rt] < msz[root]) root = rt; }void get_dis(int rt, int fa) {now[++tot] = dis[rt];for(int i = head[rt]; i; i = nex[i]) {if(to[i] == fa || visit[to[i]]) continue;dis[to[i]] = dis[rt] + value[i];get_dis(to[i], rt);} }int num[4];int calc(int rt) {int ans = 0, sum = 0;for(int i = head[rt]; i; i = nex[i]) {if(visit[to[i]]) continue;dis[to[i]] = value[i];tot = 0;get_dis(to[i], rt);for(int j = 1; j <= tot; j++) {ans += num[(3 - (now[j] % 3)) % 3];}for(int j = 1; j <= tot; j++) {num[now[j] % 3]++;}}num[0] = num[1] = num[2] = 0;return ans; }void solve(int rt) {visit[rt] = num[0] = 1;ans += calc(rt);for(int i = head[rt]; i; i = nex[i]) {if(visit[to[i]]) continue;sum = sz[to[i]];root = 0, msz[0] = inf;get_root(to[i], rt);solve(root);} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf("%d", &n);for(int i = 1; i < n; i++) {int x, y, w;scanf("%d %d %d", &x, &y, &w);add(x, y, w);add(y, x, w);}root = 0, msz[0] = inf, sum = n;get_root(1, 0);solve(root);int d = __gcd(ans * 2 + n, n * n);printf("%d/%d\n", (ans * 2 + n) / d, (n * n) / d);return 0; }

總結(jié)

以上是生活随笔為你收集整理的点分治（简要讲解 + 模板）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。