有關(guān)點(diǎn)分治的論文：國家集訓(xùn)隊(duì)2009論文集分治算法在樹的路徑問

1.樹的重心：刪去某個(gè)節(jié)點(diǎn)，使得結(jié)點(diǎn)最多的樹結(jié)點(diǎn)最少，這個(gè)結(jié)點(diǎn)稱為樹的重心。

2.每次選取樹的重心，對(duì)其子樹進(jìn)行分治，遞歸深度最壞是 logn，論文中有證明。

3.基本解法，如果求點(diǎn)對(duì)對(duì)數(shù)，分為路徑經(jīng)過根與不經(jīng)過根兩種情況，我們需要求對(duì)于每個(gè)根經(jīng)過根的方案數(shù)，可以用經(jīng)過根所有符合條件的方案數(shù)減去不經(jīng)過根滿足條件的方案數(shù)，遞歸求解即可。

Poj1655Balancing Act?求樹的重心

#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <string> #include <vector> #include <cmath> #include <queue> #include <map> #include <set> using namespace std; const int maxn = 40000 + 10; int len; int head[maxn]; int n; struct Node {int to; int next; }e[maxn];void add(int from, int to) {e[len].to = to;e[len].next = head[from];head[from] = len++; } int Size[maxn]; void gao(int x, int fa) {Size[x] = 1;for (int i = head[x]; i != -1; i = e[i].next) {int cc = e[i].to;if (cc == fa)continue;gao(cc, x);Size[x] += Size[cc];} } int m[maxn];void gao1(int x, int fa) {//printf("%d %djiji\n", x, fa);m[x] = 0;int t = n - Size[x];m[x] = max(m[x], t);for (int i = head[x]; i != -1; i = e[i].next) {int cc = e[i].to;if (cc == fa) continue;m[x] = max(m[x], Size[cc]);gao1(cc, x);} }int main() {int T, a, b;cin >> T;while (T--) {len = 0;memset(head, -1, sizeof(head));scanf("%d", &n);for (int i = 1; i < n; i++) {scanf("%d%d", &a, &b);add(a, b); add(b, a);}gao(1, 1);gao1(1, 1);int Min = 1e9;for (int i = 1; i <= n; i++)Min = min(Min, m[i]);for (int i = 1; i <= n; i++) {if (m[i] == Min) {printf("%d %d\n", i, Min); break;}}}return 0; } View Code

Poj1741Tree

求滿足條件 dis(a,b) <=k 的點(diǎn)對(duì)數(shù)

找到重心后，對(duì)其子樹到根的距離排序，然后O(n)統(tǒng)計(jì)經(jīng)過根的方案數(shù) ，因?yàn)槭菑男〉酱笈判蛲瓿傻?#xff0c;所以當(dāng)dis[a+1]+dis[b] <= k時(shí)，dis[a]+dis[b]<=k，所有從兩端，分別設(shè)一個(gè)l，一個(gè)r開始 找到一個(gè)區(qū)間后，就可以加 r-l+1。因?yàn)榕判虻膹?fù)雜度nlogn ，總體復(fù)雜度大約nlognlogn

#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <string> #include <vector> #include <cmath> #include <queue> #include <map> #include <set> using namespace std; const int maxn = 1e5 + 20; struct Node {int to; int next; int val; }e[maxn*2]; int len, ans, mi, Root, num, n, k; int head[maxn], Size[maxn],dis[maxn], m[maxn], vis[maxn]; void add(int from, int to, int val) //鄰接表 {e[len].to = to;e[len].next = head[from];e[len].val = val;head[from] = len++; } void init()//初始化 {len = 0;memset(head, -1, sizeof(head));memset(vis, 0, sizeof(vis));ans = 0; }void gaosize(int x, int fa) //統(tǒng)計(jì)節(jié)點(diǎn)大小 {Size[x] = 1; m[x] = 0;for (int i = head[x]; i != -1; i = e[i].next) {int cc = e[i].to;if (cc == fa||vis[cc]) continue;gaosize(cc, x);Size[x] += Size[cc];m[x] = max(m[x], Size[cc]);} } void gaoroot(int root, int x, int fa) //求重心 {m[x] = max(m[x], Size[root] - Size[x]);if (mi > m[x]) {Root = x; mi = m[x];}for (int i = head[x]; i != -1; i = e[i].next) {int cc = e[i].to;if (vis[cc] || cc == fa) continue;gaoroot(root, cc, x);} } void gaodis(int x, int val, int fa) //求到重心距離 {dis[num++] = val;for (int i = head[x]; i != -1; i = e[i].next) {int cc = e[i].to;if (vis[cc] || cc == fa) continue;gaodis(cc, val + e[i].val, x);} }int calc(int x, int d) // 計(jì)算樹中所有 dis[i] + dis[j] <= k 的方案數(shù) {int ret = 0;num = 0;gaodis(x, d, 0);sort(dis, dis + num);int i = 0, j = num - 1;while (i < j) {while (dis[i] + dis[j]>k&&i < j) j--;ret += j - i;i++;}return ret; }void gao(int x) {mi = n;gaosize(x, 0);gaoroot(x, x, 0);ans += calc(Root ,0);vis[Root] = 1;for (int i = head[Root]; i != -1; i = e[i].next) {int cc = e[i].to;if (vis[cc]) continue;ans -= calc(cc, e[i].val); //去重 gao(cc);} }int main() {int a, b, c;while (scanf("%d%d", &n, &k), n || k) {init();for (int i = 0; i < n - 1; i++) {scanf("%d%d%d", &a, &b, &c);add(a, b, c); add(b, a, c);}gao(1);printf("%d\n", ans);}return 0; } View Code

Poj1987Distance Statistics

和上題類似

#define _CRT_SECURE_NO_WARNINGS #pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <string> #include <vector> #include <cmath> #include <queue> #include <map> #include <set> using namespace std; const int maxn = 44444; struct Node {int to; int next; int val; }e[maxn * 2]; int len, ans, mi, Root, num, n, k; int head[maxn], Size[maxn], dis[maxn], m[maxn], vis[maxn]; void add(int from, int to, int val) //鄰接表 {e[len].to = to;e[len].next = head[from];e[len].val = val;head[from] = len++; } void init()//初始化 {len = 0;memset(head, -1, sizeof(head));memset(vis, 0, sizeof(vis));ans = 0; }void gaosize(int x, int fa) //統(tǒng)計(jì)節(jié)點(diǎn)大小 {Size[x] = 1; m[x] = 0;for (int i = head[x]; i != -1; i = e[i].next) {int cc = e[i].to;if (cc != fa && !vis[cc]){gaosize(cc, x);Size[x] += Size[cc];if(Size[cc]>m[x]) m[x] = Size[cc];}} } void gaoroot(int root, int x, int fa) //求重心 {if(Size[root] -Size[x]>m[x]) m[x] = Size[root] - Size[x];if (mi > m[x]) {Root = x; mi = m[x];}for (int i = head[x]; i != -1; i = e[i].next) {int cc = e[i].to;if (cc!=fa&&!vis[cc])gaoroot(root, cc, x);} } void gaodis(int x, int val, int fa) //求到重心距離 {dis[num++] = val;for (int i = head[x]; i != -1; i = e[i].next) {int cc = e[i].to;if (cc!=fa && !vis[cc]) gaodis(cc, val + e[i].val, x);} }int calc(int x, int d) // 計(jì)算樹中所有 dis[i] + dis[j] <= k 的方案數(shù) {int ret = 0;num = 0;gaodis(x, d, 0);sort(dis, dis + num);int i = 0, j = num - 1;while (i < j) {while (dis[i] + dis[j]>k&&i < j) j--;ret += j - i;i++;}return ret; }void gao(int x) {mi = n;gaosize(x, 0);gaoroot(x, x, 0);ans += calc(Root, 0);vis[Root] = 1;for (int i = head[Root]; i != -1; i = e[i].next) {int cc = e[i].to;if (!vis[cc]){ans -= calc(cc, e[i].val); //去重 gao(cc);}} }int main() {int M;int a, b, c;char d[5];while (scanf("%d%d", &n, &M)!=EOF) {init();for (int i = 0; i < M; i++) {scanf("%d%d%d%s", &a, &b, &c, d);add(a, b, c); add(b, a, c);}scanf("%d", &k);gao(1);printf("%d\n", ans);}return 0; } View Code

Codeforces Close Vertices

需要滿足兩個(gè)條件，一個(gè)是路徑長度，一個(gè)是路徑價(jià)值。我是用線段樹維護(hù)長度在區(qū)間[a,b]中的個(gè)數(shù)，按照重量排序。枚舉左端點(diǎn)，和之前一樣，尋找對(duì)應(yīng)區(qū)間，但是之前經(jīng)過的不合條件的區(qū)間，我們需要將其重量所對(duì)應(yīng)的路徑值從線段樹中刪去，最后統(tǒng)計(jì)[0,l - l[i]]的個(gè)數(shù)，就是當(dāng)前所枚舉的區(qū)間的的滿足條件的方案數(shù)。

#define _CRT_SECURE_NO_WARNINGS #pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <string> #include <vector> #include <cmath> #include <queue> #include <map> #include <set>using namespace std;#define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const int maxn = 1e5 + 10; int len, num, n, l, w; typedef long long LL; LL ans; int head[maxn], sum[maxn << 2]; int m[maxn], Size[maxn], mi, Root, vis[maxn]; struct Node {int l; int w; }dis[maxn];struct Edge {int to; int next; int val; }e[maxn << 1]; void add(int from, int to, int val) {e[len].to = to;e[len].val = val;e[len].next = head[from];head[from] = len++; }void up(int rt) {sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }void build(int l, int r, int rt) {sum[rt] = 0;if (l == r) return;int mid = (l + r) >> 1;build(lson); build(rson); }void update(int key, int add, int l, int r, int rt) {if (l == r) {sum[rt] += add; return;}int mid = (l + r) >> 1;if (key <= mid) update(key, add, lson);else update(key, add, rson);up(rt); }int ask(int L, int R, int l, int r, int rt) {if (L <= l&&r <= R) return sum[rt];int mid = (l + r) >> 1;int ans = 0;if (L <= mid) ans += ask(L, R, lson);if (R > mid) ans += ask(L, R, rson);return ans; }void clear(int key, int l, int r, int rt) {sum[rt] = 0;if (l == r) return;int mid = (l + r) >> 1;if (key <= mid) clear(key, lson);else clear(key, rson); }void gaosize(int x, int fa) {Size[x] = 1; m[x] = 0;for (int i = head[x]; i != -1; i = e[i].next) {int cc = e[i].to;if (cc == fa || vis[cc]) continue;gaosize(cc, x);Size[x] += Size[cc];if (Size[cc] > m[x]) m[x] = Size[cc];} }void gaoroot(int root, int x, int fa) {m[x] = max(m[x], Size[root] - Size[x]);if (mi > m[x]) {mi = m[x]; Root = x;}for (int i = head[x]; i != -1; i = e[i].next) {int cc = e[i].to;if (vis[cc] || cc == fa) continue;gaoroot(root, cc, x);} }void gaodis(int x, int fa, Node val) {dis[num++] = val;for (int i = head[x]; i != -1; i = e[i].next) {int cc = e[i].to;if (vis[cc] || cc == fa) continue;Node t = val; t.l++; t.w += e[i].val;gaodis(cc, x, t);} }int cmp(const Node &a, const Node &b) {return a.w < b.w; }LL calc(int x, Node val) {LL ret = 0;num = 0;gaodis(x, 0, val);sort(dis, dis + num, cmp);for (int i = 0; i < num; i++) {update(dis[i].l, 1, 0, n, 1);}int i = 0; int j = num - 1;while (i < j) {while (dis[i].w + dis[j].w>w&&i < j) {update(dis[j].l, -1, 0, n, 1); j--;}update(dis[i].l, -1, 0, n, 1);if(l>=dis[i].l)ret += ask(0, min(n, l - dis[i].l), 0, n, 1);i++;}if (i == j)update(dis[i].l, -1, 0, n, 1);return ret;}void gao(int x) {mi = n;gaosize(x, 0);gaoroot(x, x, 0);Node t; t.l = 0; t.w = 0;ans += calc(Root, t);vis[Root] = 1;for (int i = head[Root]; i != -1; i = e[i].next) {//從劃分出的重心開始，一直wa在 使用xint cc = e[i].to;if (vis[cc]) continue;Node t; t.l = 1; t.w = e[i].val;ans -= calc(cc, t);gao(cc);} }void init() {ans = 0; len = 0;memset(head, -1, sizeof(head));memset(vis, 0, sizeof(vis)); }int main() {int a, b;cin >> n >> l >> w;init();for (int i = 1; i < n; i++) {scanf("%d%d", &a, &b);add(i + 1, a, b); add(a, i + 1, b);}gao(1);cout << ans << endl;return 0; } View Code

Hdu5314Happy King

統(tǒng)計(jì)方法和上題差不多，這題記錄的是最大最小值。

#define _CRT_SECURE_NO_WARNINGS #pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <string> #include <vector> #include <cmath> #include <queue> #include <map> #include <set>using namespace std; typedef long long LL; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const int maxn = 1e5 + 10; int len, n, Root, mi, num, D; int head[maxn], vis[maxn], sum[maxn << 2], Size[maxn], m[maxn]; LL ans; inline bool scanf_(int &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0; //EOFwhile (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c - '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');ret *= sgn;return 1; }inline void printf_(int x) {if (x>9) printf_(x / 10);putchar(x % 10 + '0'); } struct Edge {int next; int to; }e[maxn << 1];void add(int from, int to) {e[len].to = to;e[len].next = head[from];head[from] = len++; } void init() {len = 0; ans = 0;memset(vis, 0, sizeof(vis));memset(head, -1, sizeof(head));memset(sum, 0, sizeof(sum)); }struct Node {int Max; int Min;friend const Node operator+(const Node &a, const Node &b) {Node t;t.Max = max(a.Max, b.Max); t.Min = min(a.Min, b.Min);return t;} }dis[maxn], V[maxn];void up(int rt) {sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }void update(int key, int add, int l, int r, int rt) {if (l == r) {sum[rt] += add; return;}int mid = (l + r) >> 1;if (key <= mid) update(key, add, lson);else update(key, add, rson);up(rt); }int ask(int L, int R, int l, int r, int rt) {if (L <= l&&r <= R) return sum[rt];int mid = (l + r) >> 1;int ans = 0;if (L <= mid) ans += ask(L, R, lson);if (R > mid) ans += ask(L, R, rson);return ans; }void gaosize(int x, int fa) {Size[x] = 1; m[x] = 0;for (int i = head[x]; i != -1; i = e[i].next) {int cc = e[i].to;if (cc == fa || vis[cc]) continue;gaosize(cc, x);Size[x] += Size[cc];m[x] = max(m[x], Size[cc]);} }void gaoroot(int root, int x, int fa) {m[x] = max(m[x], Size[root] - Size[x]);if (mi > m[x]) {mi = m[x]; Root = x;}for (int i = head[x]; i != -1; i = e[i].next) {int cc = e[i].to;if (vis[cc] || cc == fa) continue;gaoroot(root, cc, x);} }void gaodis(int x, Node val, int fa) {dis[num++] = val;for (int i = head[x]; i != -1; i = e[i].next) {int cc = e[i].to;if (vis[cc] || cc == fa) continue;Node t = val;gaodis(cc, t + V[cc], x);} }int cmp(const Node &a, const Node &b) {return a.Max < b.Max; } int tem[maxn]; int temt[maxn]; LL gaocalc(int x, Node val) {num = 0;gaodis(x, val, 0);sort(dis, dis + num, cmp);for (int i = 0; i < num; i++) tem[i] = dis[i].Min;sort(tem, tem + num);for (int i = 0; i < num; i++) {temt[i] = lower_bound(tem, tem + num, dis[i].Min) - tem;}LL ret = 0;for (int i = 0; i < num; i++) {int cc = dis[i].Max - D;int t = lower_bound(tem, tem + num, cc) - tem;if (dis[i].Min < cc) ret += 0;elseret += ask(t, num, 0, num, 1);update(temt[i], 1, 0, num, 1);}for (int i = 0; i < num; i++) {update(temt[i], -1, 0, num, 1);}return ret; }void gao(int x) {mi = n;gaosize(x, 0);gaoroot(x, x, 0);ans += gaocalc(Root, V[Root]);vis[Root] = 1; Node t = V[Root];for (int i = head[Root]; i != -1; i = e[i].next) {int cc = e[i].to;if (vis[cc]) continue;ans -= gaocalc(cc, t + V[cc]);gao(cc);} }int main() {int T, a, b;scanf_(T);while (T--) {scanf_(n); scanf_(D);init();for (int i = 1; i <= n; i++) {scanf_(V[i].Max);V[i].Min = V[i].Max;}for (int i = 0; i < n - 1; i++) {scanf_(a);scanf_(b);add(a, b); add(b, a);}gao(1);ans = ans * 2;cout << ans << endl;}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/yigexigua/p/4696190.html

總結(jié)

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

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