點分治

什么是點分治？

點分治主要用于有關樹上路徑統計的問題。

怎么點分治？

1，選取一個點，把樹變成有根樹。為了讓遞歸層數盡可能的小，我們要選取樹的重心，即子樹大小最大值最小的點。

2，處理聯通塊中通過根的路徑。

3，刪除根節點。

4，遞歸處理子樹。

操作

1 void getR(int u, int f) { 2 sz[u] = 1; mx[u] = 0; 3 for (int v, i = 0; i < g[u].size(); ++i) if ((v = g[u][i].v) != f && !vis[v]) { 4 getR(v, u); sz[u] += sz[v]; gmax(mx[u], sz[v]); 5 } gmax(mx[u], size - sz[u]); 6 if (mx[R] > mx[u]) R = u; 7 } 8 //找重心

例題們

?

POJ - 1741??BZOJ - 1468?BZOJ - 1316

1 #include<algorithm> 2 #include<vector> 3 #include<cstdio> 4 #include<bitset> 5 #include<iostream> 6 using namespace std; 7 inline char nc() { 8 static char b[1<<15],*s=b,*t=b; 9 return s==t&&(t=(s=b)+fread(b,1,1<<15,stdin),s==t)?-1:*s++; 10 } 11 inline void read(int &x) { 12 char b = nc(); x = 0; 13 for (; !isdigit(b); b = nc()); 14 for (; isdigit(b); b = nc()) x = x * 10 + b - '0'; 15 } 16 const int N = 10010; 17 int n, m, R, sz[N], msz[N], ans, size, dep[N], D, d[N]; 18 struct Edge {int v,w;}; 19 vector < Edge > g[N]; 20 bitset < N > vis; 21 inline void ae(int u, int v, int w) { 22 g[u].push_back((Edge){v, w}); 23 g[v].push_back((Edge){u, w}); 24 } 25 void getR(int u, int f) { 26 sz[u] = 1; msz[u] = 0; 27 for (int v, i = 0; i < g[u].size(); ++i) if ((v = g[u][i].v) != f && !vis[v]) { 28 getR(v, u); sz[u] += sz[v]; msz[u] = max(msz[u], sz[v]); 29 } msz[u] = max(msz[u], size - sz[u]); 30 if (msz[u] < msz[R]) R = u; 31 } 32 void getD(int u, int f) { 33 d[++D] = dep[u]; 34 for (int v, i = 0; i < g[u].size(); ++i) 35 if ((v = g[u][i].v) != f && !vis[v]) 36 dep[v] = dep[u] + g[u][i].w, getD(v, u); 37 } 38 int calc(int u) { 39 D = 0; getD(u, 0); 40 sort(d + 1, d + 1 + D); 41 int res = 0, l = 1, r = D; 42 while (l < r) { 43 if (d[l] + d[r] <= m) res += r - l, ++l; 44 else --r; 45 } return res; 46 } 47 void solve(int u) { 48 dep[u] = 0; vis[u] = 1; ans += calc(u); 49 for (int v, i = 0; i < g[u].size(); ++i) { 50 if (!vis[v = g[u][i].v]) { 51 dep[v] = g[u][i].w; 52 ans -= calc(v); 53 size = sz[v]; 54 getR(v, R = 0); 55 solve(R); 56 } 57 } 58 } 59 void solve() { 60 for (int i = 1, u, v, w; i < n; ++i) 61 read(u), read(v), read(w), ae(u, v, w); 62 size = n; getR(1, R = 0); solve(R); 63 printf("%d\n", ans); ans = 0; 64 for (int i = 1; i <= n; ++i) g[i].clear(); 65 vis.reset(); 66 } 67 int main() { 68 msz[0] = 0x3f3f3f3f; 69 while (read(n), read(m), n + m) solve(); 70 return 0; 71 } View Code 1 #include<set> 2 #include<bitset> 3 #include<vector> 4 #include<cstdio> 5 #include<iostream> 6 #define fir first 7 #define pb push_back 8 #define sec second 9 using namespace std; 10 inline char nc() { 11 static char b[1<<16],*s=b,*t=b; 12 return s==t&&(t=(s=b)+fread(b,1,1<<16,stdin),s==t)?-1:*s++; 13 } 14 template < class T > 15 inline void read(T &x) { 16 char b = nc(); x = 0; 17 for (; !isdigit(b); b = nc()); 18 for (; isdigit(b); b = nc()) x = x * 10 + b - '0'; 19 } 20 typedef long long ll; 21 const int N = 10010; 22 int n, m, sz[N], R, mx[N], size; 23 ll dis[N]; 24 set < int > s; 25 bitset < N > vis; 26 struct Edge {int v,w;}; 27 pair < ll , bool > q[110]; 28 vector < Edge > g[N]; 29 inline void ae(int u, int v, int w) { 30 g[u].pb((Edge){v, w}); 31 g[v].pb((Edge){u, w}); 32 } 33 inline void gmax(int &x, int y) { 34 if (x < y) x = y; 35 } 36 void getR(int u, int f) { 37 sz[u] = 1; mx[u] = 0; 38 for (int v, i = 0; i < g[u].size(); ++i) if ((v = g[u][i].v) != f && !vis[v]) { 39 getR(v, u); sz[u] += sz[v]; gmax(mx[u], sz[v]); 40 } gmax(mx[u], size - sz[u]); 41 if (mx[R] > mx[u]) R = u; 42 } 43 inline void upd(ll x) { 44 for (int i = 1; i <= m; ++i) 45 if (!q[i].sec && s.count(q[i].fir - x)) q[i].sec = 1; 46 } 47 void calc(int u, int f) { 48 upd(dis[u]); 49 for (int i = 0, v; i < g[u].size(); ++i) 50 if ((v = g[u][i].v) != f && !vis[v]) 51 dis[v] = dis[u] + g[u][i].w, calc(v, u); 52 } 53 void add(int u, int f) { 54 s.insert(dis[u]); 55 for (int i = 0, v; i < g[u].size(); ++i) 56 if ((v = g[u][i].v) != f && !vis[v]) add(v, u); 57 } 58 void solve(int u) { 59 vis[u] = 1; dis[u] = 0; s.clear(); s.insert(0); 60 for (int v, i = 0; i < g[u].size(); ++i) if (!vis[v = g[u][i].v]) { 61 dis[v] = g[u][i].w; calc(v, u); add(v, u); 62 } 63 for (int v, i = 0; i < g[u].size(); ++i) if (!vis[v = g[u][i].v]) { 64 size = sz[v]; getR(v, R = 0); solve(R); 65 } 66 } 67 int main() { 68 read(n); read(m); mx[0] = ~0U >> 1; 69 for (int u, v, w, i = 1; i < n; ++i) 70 read(u), read(v), read(w), ae(u, v, w); 71 for (int i = 1; i <= m; ++i) read(q[i].fir); 72 size = n; getR(1, 1); solve(R); 73 for (int i = 1; i <= m; ++i) puts(q[i].fir == 0 || q[i].sec ? "Yes" : "No"); 74 return 0; 75 } 76 //bzoj1316 View Code

入門題。

題意：找出距離$? \leqslant m$的點對的數目。

為了不重復計算，咱每次都統計必須經過根節點的滿足條件的路徑的條數。

要統計在某子樹中滿足條件的路徑，咱只要把子樹中每一點到根的距離都算出來，排序，掃一次就行。

必須經過根節點的滿足條件的路徑的條數為$calc(u) - \Sigma calc(v)$。

?

[IOI2011]Race

1 #include<bitset> 2 #include<cstdio> 3 #include<vector> 4 #include<iostream> 5 using namespace std; 6 inline char nc() { 7 static char b[1<<16],*s=b,*t=b; 8 return s==t&&(t=(s=b)+fread(b,1,1<<16,stdin),s==t)?-1:*s++; 9 } 10 inline void read(int &x) { 11 char b = nc(); x = 0; 12 for (; !isdigit(b); b = nc()); 13 for (; isdigit(b); b = nc()) x = x * 10 + b - '0'; 14 } 15 const int N = 200005; 16 struct Edge {int v,w;}; 17 vector < Edge > g[N]; 18 inline void ae(int u, int v, int w) { 19 g[u].push_back((Edge){v, w}); 20 g[v].push_back((Edge){u, w}); 21 } 22 int n, m, R, sz[N], mx[N], size, dep[N], ans, dis[N]; 23 bitset < N > vis; 24 int h[1000010], T[1000010], D; 25 inline void gmin(int &x, int y) {if (x > y) x = y;} 26 inline void gmax(int &x, int y) {if (x < y) x = y;} 27 void getR(int u, int f) { 28 sz[u] = 1; mx[u] = 0; 29 for (int v, i = 0; i < g[u].size(); ++i) 30 if ((v = g[u][i].v) != f && !vis[v]) { 31 getR(v, u); sz[u] += sz[v]; gmax(mx[u], sz[v]); 32 } gmax(mx[u], size - sz[u]); 33 if (mx[R] > mx[u]) R = u; 34 } 35 inline void query(int x, int y) { 36 if (x <= m && T[m-x] == D) gmin(ans, y + h[m-x]); 37 } 38 inline void upd(int x, int y) { 39 if (T[x] == D) gmin(h[x], y); else h[x] = y, T[x] = D; 40 } 41 void calc(int u, int f) { 42 dep[u] = dep[f] + 1; query(dis[u], dep[u]); 43 for (int v, i = 0; i < g[u].size(); ++i) 44 if ((v = g[u][i].v) != f && !vis[v]) 45 dis[v] = dis[u] + g[u][i].w, calc(v, u); 46 } 47 void add(int u, int f) { 48 if (dis[u] <= m) upd(dis[u], dep[u]); 49 for (int v, i = 0; i < g[u].size(); ++i) 50 if ((v = g[u][i].v) != f && !vis[v]) add(v, u); 51 } 52 void solve(int u) { 53 vis[u] = 1; ++D; upd(dis[u] = 0, dep[u] = 0); 54 for (int v, i = 0; i < g[u].size(); ++i) 55 if (!vis[v = g[u][i].v]) { 56 dis[v] = g[u][i].w; 57 calc(v, u); add(v, u); 58 } 59 for (int v, i = 0; i < g[u].size(); ++i) { 60 if (!vis[v = g[u][i].v]) { 61 size = sz[v]; 62 getR(v, R = 0); 63 solve(R); 64 } 65 } 66 } 67 int main() { 68 read(n); read(m); ans = ~0U >> 1; mx[0] = 0x3f3f3f3f; 69 for (int i = 1, u, v, w; i < n; ++i) 70 read(u), read(v), read(w), ae(++u, ++v, w); 71 size = n; getR(1, 1); solve(R); 72 printf("%d\n", ans != ~0U >> 1 ? ans : -1); 73 return 0; 74 } View Code

咱每次只統計經過了根節點的路徑。所以要先統計子樹答案在加入子樹信息。

全局開一個數組，記錄到根節點的長度為$x$時，最小的深度$h[x]$。

?

3697: 采藥人的路徑

1 #include<bitset> 2 #include<vector> 3 #include<cstdio> 4 #include<iostream> 5 using namespace std; 6 inline char nc() { 7 static char b[1<<16],*s=b,*t=b; 8 return s==t&&(t=(s=b)+fread(b,1,1<<16,stdin),s==t)?-1:*s++; 9 } 10 inline void read(int &x) { 11 char b = nc(); x = 0; 12 for (; !isdigit(b); b = nc()); 13 for (; isdigit(b); b = nc()) x = x * 10 + b - '0'; 14 } 15 const int N = 100005; 16 struct Edge {int v,w;}; 17 vector < Edge > e[N]; 18 inline void ae(int u, int v, int w) { 19 e[u].push_back((Edge){v, w}); 20 e[v].push_back((Edge){u, w}); 21 } 22 int n, sz[N], mx[N], R, size, ff[N+N][2], gg[N+N][2], dis[N], dmx, hmx; 23 long long ans; 24 bitset < N > vis; 25 int (*f)[2] = ff + 100000, (*g)[2] = gg + 100000; 26 int cc[N+N], *c = cc + 100000; 27 inline int ABS(int x) {return x > 0 ? x : -x;} 28 inline void gmax(int &x, int y) { 29 if (x < y) x = y; 30 } 31 void getR(int u, int f) { 32 sz[u] = 1; mx[u] = 0; 33 for (int v, i = 0; i < e[u].size(); ++i) 34 if ((v = e[u][i].v) != f && !vis[v]) { 35 getR(v, u); sz[u] += sz[v]; gmax(mx[u], sz[v]); 36 } 37 gmax(mx[u], size - sz[u]); 38 if (mx[R] > mx[u]) R = u; 39 } 40 void calc(int u, int f) { 41 gmax(dmx, ABS(dis[u])); 42 ++g[dis[u]][bool(c[dis[u]])]; 43 ++c[dis[u]]; 44 for (int v, i = 0; i < e[u].size(); ++i) 45 if ((v = e[u][i].v) != f && !vis[v]) 46 dis[v] = dis[u] + e[u][i].w, calc(v, u); 47 --c[dis[u]]; 48 } 49 void solve(int u) { 50 f[dis[u] = 0][0] = 1; vis[u] = 1; hmx = 0; 51 for (int v, i = 0; i < e[u].size(); ++i) 52 if (!vis[v = e[u][i].v]) { 53 dmx = 0; dis[v] = e[u][i].w; 54 calc(v, u); gmax(hmx, dmx); 55 ans += (f[0][0]-1) * g[0][0]; 56 for (int j = -dmx; j <= dmx; ++j) 57 ans += f[j][0] * g[-j][1] + f[j][1] * g[-j][0] + f[j][1] * g[-j][1]; 58 for (int j = -dmx; j <= dmx; ++j) 59 f[j][0] += g[j][0], f[j][1] += g[j][1], g[j][0] = g[j][1] = 0; 60 } 61 for (int i = -hmx; i <= hmx; ++i) f[i][0] = f[i][1] = 0; 62 for (int v, i = 0; i < e[u].size(); ++i) 63 if (!vis[v = e[u][i].v]) { 64 size = sz[v]; 65 getR(v, R = 0); 66 solve(R); 67 } 68 } 69 int main() { 70 read(n); mx[0] = 0x3f3f3f3f; size = n; 71 for (int i = 1, u, v, w; i < n; ++i) 72 read(u), read(v), read(w), ae(u, v, w == 1 ? 1 : -1); 73 getR(1, 1); solve(R); 74 printf("%lld\n", ans); 75 return 0; 76 } View Code

題意：邊權有$1,-1$，求有多少條路徑權值和為$0$，且從中間某點斷開，剩下的兩條路徑的權值和也為$0$。

記$dis(u)$為當前根$r$到$u$的距離，$f(d,0/1)$為之前幾棵子樹中距離為$d$，是否出現過$d$這個權值的邊的個數。$g(d,0/1)$則是當前子樹的。

如果向下$dfs$時發現現在的距離$d$在$r-u$上是出現過的，說明$u$到之前出現$d$的點$v$的這一段距離為$0$。也就是說$u-v$邊權和為$0$，用題目的說法就是陰陽平衡。

算出了$f$和$g$后就很好計算答案了，$ans = f(0,0) \times g(0,0) + \sum_d f(d,0) \times g(-d, 1) +f(d, 1) \times g(-d, 0) + f(d, 1) \times g(d, 1)$。

分別對應著休息點在根上，當前子樹中，前幾棵子樹中的某一棵中，當前子樹和前幾棵子樹的某一棵都行。

?

A1486. 樹

1 #include<stack> 2 #include<cstdio> 3 #include<vector> 4 #include<bitset> 5 #include<iostream> 6 #define pb push_back 7 using namespace std; 8 inline char nc() { 9 static char b[1<<16],*s=b,*t=b; 10 return s==t&&(t=(s=b)+fread(b,1,1<<16,stdin),s==t)?-1:*s++; 11 } 12 inline void read(int &x) { 13 char b = nc(); x = 0; 14 for (; !isdigit(b); b = nc()); 15 for (; isdigit(b); b = nc()) x = x * 10 + b - '0'; 16 } 17 const int N = 100005; 18 inline void gmax(int &x, int y) {if (x < y) x = y;} 19 struct Node { 20 Node *ch[2]; int v; 21 } Tnull, *null = &Tnull, *root; 22 Node mem[6000000], *C; 23 inline Node* newNode() { 24 C->ch[0] = C->ch[1] = null; 25 C->v = 0; return C++; 26 } 27 void insert(int x, int v) { 28 Node *u = root; 29 for (int c, i = 30; ~i; --i) { 30 c = (x >> i) & 1; 31 if (u->ch[c] == null) 32 u->ch[c] = newNode(); 33 u = u->ch[c]; 34 gmax(u->v, v); 35 } 36 } 37 int query(int x, int v) { 38 if (root == null) return -1; 39 int res = 0; 40 Node *u = root; 41 for (int c, i = 30; ~i; --i) { 42 c = !((x >> i) & 1); 43 if (u->ch[c] != null && u->ch[c]->v >= v) 44 res |= 1 << i; 45 else c = !c; 46 u = u->ch[c]; 47 if (u->v < v) return -1; 48 } return res; 49 } 50 vector < int > g[N]; 51 int n, m, val[N], sz[N], mx[N], R, ans, size; 52 bitset < N > vis, a; 53 inline void ae(int u, int v) { 54 g[u].pb(v); g[v].pb(u); 55 } 56 void getR(int u, int f) { 57 sz[u] = 1; mx[u] = 0; 58 for (int v,i = 0; i < g[u].size(); ++i) if ((v = g[u][i]) != f && !vis[v]) { 59 getR(v, u); sz[u] += sz[v]; gmax(mx[u], sz[v]); 60 } gmax(mx[u], size - sz[u]); 61 if (mx[R] > mx[u]) R = u; 62 } 63 void calc(int u, int f, int w, int c) { 64 gmax(ans, query(w, m - c)); 65 for (int v, i = 0; i < g[u].size(); ++i) 66 if ((v = g[u][i]) != f && !vis[v]) { 67 calc(v, u, w ^ val[v], c + a[v]); 68 } 69 } 70 void add(int u, int f, int w, int c) { 71 insert(w, c); 72 for (int v, i = 0; i < g[u].size(); ++i) 73 if ((v = g[u][i]) != f && !vis[v]) 74 add(v, u, w ^ val[v], c + a[v]); 75 } 76 void solve(int u) { 77 vis[u] = 1; C = mem; root = newNode(); insert(0, 0); 78 for (int v, i = 0; i < g[u].size(); ++i) if (!vis[v = g[u][i]]) { 79 calc(v, u, val[u] ^ val[v], a[u] + a[v]); 80 add(v, u, val[v], a[v]); 81 } gmax(ans, query(val[u], m - a[u])); 82 for (int v, i = 0; i < g[u].size(); ++i) if (!vis[v = g[u][i]]) { 83 size = sz[v]; getR(v, R = 0); solve(R); 84 } 85 } 86 int main() { 87 null->ch[0] = null->ch[1] = null; 88 ans = -1; mx[0] = ~0U >> 1; 89 read(n); read(m); 90 for (int i = 1, t; i <= n; ++i) 91 read(t), a[i] = t; 92 if (a.count() < m) return puts("-1"), 0; 93 for (int i = 1; i <= n; ++i) read(val[i]); 94 for (int i = 1, u, v; i < n; ++i) 95 read(u), read(v), ae(u, v); 96 size = n; getR(1, 1); solve(R); 97 printf("%d\n", ans); 98 return 0; 99 } View Code

題意：有喜歡的點，點上有點權。求出一條路徑使得點權異或和最大且有至少$k$個喜歡的點在路徑上。

$k=0$時的原題：The xor-longest Path

要讓異或和最大，當然還是在$trie$上貪心。

還是跟上面的套路一樣，咱只統計經過了根節點的路徑。

咱往$trie$里插入異或和時不計算根的值，算時把根加進去。這樣就不會把根的異或掉。

在$trie$里還要額外記錄路徑上喜歡的節點的個數。

?

轉載于:https://www.cnblogs.com/p0ny/p/8176474.html

總結

以上是生活随笔為你收集整理的点分治的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。