POJ 1741 树的分治(点分治)入门

看一下09年漆子超的论文，是论文的第一题，思路在其中讲得很清楚了。

复杂度分析：每次先找当前树的重心，再从重心为根遍历这颗树， 从表面上看来这个复杂度很大，但事实并非如此，通过找多次重心，使整棵树的深度不超过log(n)， 所以对于每个点的访问次数不超过log(n)， 总体复杂度nlog(n)， 如果在dfs里面添加一些操作，那么就要把复杂度乘上去，这题cal的复杂度是log(n)， 总体复杂度nlog^2(n)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10005;
struct Edge {
	int v, w, next;
} g[maxn << 2];
int head[maxn], E;
int n, k;
void init() {
	memset(head, -1, sizeof(head));
	E = 0;
	ans = 0;
	memset(vis, false, sizeof(vis));
}
void add(int s, int t, int w) {
	g[E].v = t;
	g[E].w = w;
	g[E].next = head[s];
	head[s] = E++;
}

int sz[maxn], mx[maxn];
bool vis[maxn];
void dfsSz(int u, int fa) { //计算子树大小
	mx[u] = 0, sz[u] = 1;
	for(int i = head[u]; ~i; i = g[i].next) {
		int v = g[i].v;
		if(v == fa || vis[v]) continue;
		dfsSz(v, u);
		sz[u] += sz[v];
		mx[u] = max(mx[u], sz[v]);
	}
}
int root, mi;
void dfsRt(int rt, int u, int fa) { //计算重心，并用root保存
	mx[u] = max(mx[u], sz[rt] - sz[u]);
	if(mi > mx[u]) mi = mx[u], root = u;
	for(int i = head[u]; ~i; i = g[i].next) {
		int v = g[i].v;
		if(v == fa || vis[v]) continue;
		dfsRt(rt, v, u);
	}
}
int dis[maxn], num;
void dfsDis(int u, int fa, int d) { //把子树的dis放入数组中
	dis[num++] = d;
	for(int i = head[u]; ~i; i = g[i].next) {
		int v = g[i].v;
		if(v == fa || vis[v]) continue;
		dfsDis(v, u, d + g[i].w);
	}
}
int cal(int u, int d) { //计算答案
	num = 0;
	dfsDis(u, -1, d);
	sort(dis, dis + num);
	int i = 0, j = num - 1, ret = 0;
	while (i < j) {
		while (i < j && dis[i] + dis[j] > k)
			j--;
		ret += j - i;
		i++;
	}
	return ret;
}
int ans;
void dfs(int u) {
	mi = n;
	dfsSz(u, -1);
	dfsRt(u, u, -1);
	ans += cal(root, 0);
	vis[root] = 1;
	for(int i = head[root]; ~i; i = g[i].next) {
		int v = g[i].v;
		if(vis[v]) continue;
		ans -= cal(v, g[i].w);
		dfs(v);
	}
}
int main() {
	while (~scanf("%d%d", &n, &k)) {
		if(!n && !k) break;
		init();
		int x, y, z;
		for(int i = 1; i < n; i++) {
			scanf("%d%d%d", &x, &y, &z);
			add(x, y, z);
			add(y, x, z);
		}
		dfs(1);
		printf("%d\n", ans);
	}
	return 0;
}

原文：http://blog.csdn.net/auto_ac/article/details/19567291