有关点分治的论文：国家集训队2009论文集分治算法在树的路径问
1.树的重心：删去某个节点，使得结点最多的树结点最少，这个结点称为树的重心。
2.每次选取树的重心，对其子树进行分治，递归深度最坏是 logn，论文中有证明。
3.基本解法，如果求点对对数，分为路径经过根与不经过根两种情况，我们需要求对于每个根经过根的方案数，可以用经过根所有符合条件的方案数减去不经过根满足条件的方案数，递归求解即可。
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 ", 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 ", i, Min); break; } } } return 0; }
Poj1741Tree
求满足条件 dis(a,b) <=k 的点对数
找到重心后，对其子树到根的距离排序，然后O(n)统计经过根的方案数 ，因为是从小到大排序完成的，所以当dis[a+1]+dis[b] <= k时，dis[a]+dis[b]<=k，所有从两端，分别设一个l，一个r开始 找到一个区间后，就可以加 r-l+1。因为排序的复杂度nlogn ，总体复杂度大约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) //统计节点大小 { 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) // 计算树中所有 dis[i] + dis[j] <= k 的方案数 { 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 ", ans); } return 0; }
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) //统计节点大小 { 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) // 计算树中所有 dis[i] + dis[j] <= k 的方案数 { 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 ", ans); } return 0; }
Codeforces Close Vertices
需要满足两个条件，一个是路径长度，一个是路径价值。我是用线段树维护长度在区间[a,b]中的个数，按照重量排序。枚举左端点，和之前一样，寻找对应区间，但是之前经过的不合条件的区间，我们需要将其重量所对应的路径值从线段树中删去，最后统计[0,l - l[i]]的个数，就是当前所枚举的区间的的满足条件的方案数。
#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在 使用x int 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; }
Hdu5314Happy King
统计方法和上题差不多，这题记录的是最大最小值。
#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; //EOF while (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; else ret += 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; }