POJ - 1741 Tree （点分治）

Tree

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 29895		Accepted: 10019

Description

Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.

Input

The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l.
The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

Sample Output

给你一颗树，求满足a,b之间<=k的对数有几个；

正常的思路暴力是N^2的数据范围爆炸是肯定的；这个时候就要用到点的分治的思想；

首先讲解一下树分治，以下树分治内容转自：http://blog.sina.com.cn/s/blog_6d5aa19a0100o73m.html

对于一棵有根树，树中满足要求的一个数对所对应的一条路径，必然是以下两种情况之一：
1、经过根节点
2、不经过根节点，也就是说在根节点的一棵子树中
对于情况2，可以递归求解，下面主要来考虑情况1。

设点i的深度为Depth[i]，父亲为Parent[i]。
若i为根，则Belong[i]=-1，若Parent[i]为根，则Belong[i]=i，否则Belong[i]=Belong[Parent[i]]。
这三个量都可以通过一次BFS求得。
我们的目标是要统计：有多少对(i,j)满足i<j，Depth[i]+Depth[j]<=K且Belong[i]!=Belong[j]

如果这样考虑问题会变得比较麻烦，我们可以考虑换一种角度：
设X为满足i<j且Depth[i]+Depth[j]<=K的数对(i,j)的个数
设Y为满足i<j，Depth[i]+Depth[j]<=K且Belong[i]==Belong[j]数对(i,j)的个数
那么我们要统计的量便等于X-Y

求X、Y的过程均可以转化为以下问题：
已知A[1],A[2],...A[m]，求满足i<j且A[i]+A[j]<=K的数对(i,j)的个数

对于这个问题，我们先将A从小到大排序。
设B[i]表示满足A[i]+A[p]<=K的最大的p(若不存在则为0)。我们的任务便转化为求出A所对应的B数组。那么，若B[i]>i，那么i对答案的贡献为B[i]-i。
显然，随着i的增大，B[i]的值是不会增大的。利用这个性质，我们可以在线性的时间内求出B数组，从而得到答案。

综上，设递归最大层数为L，因为每一层的时间复杂度均为“瓶颈”——排序的时间复杂度O(NlogN)，所以总的时间复杂度为O(L*NlogN)

然而，如果遇到极端情况——这棵树是一根链，那么随意分割势必会导致层数达到O(N)级别，对于N=10000的数据是无法承受的。因此，我们在每一棵子树中选择“最优”的点分割。所谓“最优”，是指删除这个点后最大的子树尽量小。这个点可以通过树形DP在O(N)时间内求出，不会增加时间复杂度。这样一来，即使是遇到一根链的情况时，L的值也仅仅是O(logN)的。

简单来说：点分治就是每次找到重心，然后把重心去掉，对分成的每两棵树之间分别统计路径信息（以重心的每个相邻点为根，遍历整棵子树即可得到这个根到每个结点的统计信息），就可以知道包含这个重心的所有路径的信息，然后对于剩下的路径就是在子树里面进行同样的操作了，直到只剩一个点为止（注意这一个点所构成的路径有时也要处理一下）。边分治就是每次找到一条边，使得删掉这条边后分成的两棵子树大小尽可能平均，然后以删掉的边的两端点为根，分别统计根到两棵树中的每个结点的路径信息，最后合并算路径，即可得到包含这条边的所有路径的信息，剩下的路径在两棵树中递归处理。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010;
const int inf = 0x3f3f3f3f;
int head[maxn], cnt, vis[maxn], n, k, allnode;
int ans, root, son[maxn], maxSon[maxn], dis[maxn], deep[maxn];
struct *** {
	int u, v, ne, w;
}edis[maxn << 1];
void init() {
	memset(vis, 0, sizeof(vis));
	memset(head, -1, sizeof(head));
	cnt = root = ans = 0; maxSon[0] = inf;
}
void add(int u, int v, int w) {
	edis[cnt].u = u; edis[cnt].v = v; edis[cnt].w = w;
	edis[cnt].ne = head[u]; head[u] = cnt++;
}
void getRoot(int u, int fa) {
	son[u] = 1; maxSon[u] = 0;
	for (int s = head[u]; ~s; s = edis[s].ne) {
		int v = edis[s].v;
		if (v == fa || vis[v])continue;
		getRoot(v, u);
		son[u] += son[v];
		maxSon[u] = max(maxSon[u], son[v]);
	}
	maxSon[u] = max(maxSon[u], allnode - son[u]);
	if (maxSon[u] < maxSon[root])root = u;
}
void getDeep(int x, int fa) {
	deep[++deep[0]] = dis[x];
	for (int s = head[x]; ~s;s = edis[s].ne) {
		int v = edis[s].v;
		if (v == fa || vis[v])continue;
		dis[v] = dis[x] + edis[s].w;
		getDeep(v, x);
	}
}
int cal(int x, int now) {
	dis[x] = now; deep[0] = 0;
	getDeep(x, 0);
	sort(deep + 1, deep + deep[0] + 1);
	int all = 0;
	for (int l = 1, r = deep[0]; l < r;) {
		if (deep[l] + deep[r] <= k)all += r - l, l++;
		else r--;
	}
	return all;
}
void getDfs(int st) {
	vis[root] = 1;
	ans += cal(st, 0);
	for (int s = head[root]; ~s; s = edis[s].ne) {
		int v = edis[s].v;
		if (vis[v])continue;
		ans -= cal(v, edis[s].w);
		allnode = son[v];
		root = 0; getRoot(v, st);
		getDfs(root);
	}
}
int main() {
	while (~scanf("%d%d", &n, &k) && n) {
		init();
		for (int s = 1; s < n; s++) {
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			add(a, b, c); add(b, a, c);
		}
		getRoot(1, -1);
		getDfs(root);
		printf("%d\n", ans);
	}
}