树的分治

树的分治分为两种：点分治、边分治。

点分治：点分治就是每次找到重心，然后把重心去掉，对分成的每两棵树之间分别统计路径信息（以重心的每个相邻点为根，遍历整棵子树即可得到这个根到每个结点的统计信息），就可以知道包含这个重心的所有路径的信息，然后对于剩下的路径就是在子树里面进行同样的操作了，直到只剩一个点为止（注意这一个点所构成的路径有时也要处理一下）。

边分治：边分治就是每次找到一条边，使得删掉这条边后分成的两棵子树大小尽可能平均，然后以删掉的边的两端点为根，分别统计根到两棵树中的每个结点的路径信息，最后合并算路径，即可得到包含这条边的所有路径的信息，剩下的路径在两棵树中递归处理。

点分治和边分治是可以通用的。

例题（点分治）

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

5 4

1 2 3

1 3 1

1 4 2

3 5 1

0 0

Sample Output

题目大意：

给定一棵N个节点、边上带权的树，再给出一个K，询问有多少个数对(i,j)满足i小于j，且i与j两点在树上的距离小于等于K。

对于一棵有根树，其中任意两点的距离路径一定是一下两种情况之一：

（1）距离路径经过树根。

（2）距离路径未经过树根，即在根节点的一棵子树中。

首先考虑（1）情况，假设两点到根的距离即深度为depth[a],depth[b]，有两点的距离为depth[a]+depth[b]。

但对于（2）情况，上式显然不成立，但是我们可以通过递归到根节点的子树，直到（2）情况也转换为了（1）。

在统计距离时需要判断两点是否位于同一子树，可以使用belong[i]和father[i]实现。如果i为根则belong[i]=0;如果father[i]为根则belong[i]=i；其他belong[i]=belong[father[i]]。以上都可以通过一次dfs得出。

除了上面那种方法还有一种不用进行判断的方法。

设X为满足i<=j且depth[i]+depth[j]<=k的（i，j）点对的个数。

设Y为满足i<=j且depth[i]+depth[j]<=k且belong[i]==belong[j]的（i，j）点对的个数。

那么我们所求（1）情况个数就是X-Y。

在求X，Y时可以转换为以下问题。

a[1],a[2],a[3]…a[i]…a[j]…其中i<j求满足a[i]+a[j]<=k的（i,j）点对的个数。（此处的a与depth不一样，a的下标与对应节点无关，它们虽然一一对应但因为只要求给出点对个数所以不需要知道对应关系）

设b[i]用来储存a[i]+a[j]<=k其中最大的j，那么这个i对答案的贡献就是b[i]-i。

因为随着i的增大，a[i]在增大，所以b[i]不可能增大，所以我们可以在线性时间内求出b[i]数组进而求出答案。

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

而然如果遇到了极端的情况，树是一条链那么N最大为10000，这样的数据下算法就非常的低效，所以我们在选择割点时要选尽可能“优”的节点，即割后分成的最大子树尽可能的小。这时树的分治就派上了用途。这个点可以通过树形DP在O(N)时间内求出，不会增加时间复杂度。这样一来，即使是遇到一根链的情况时，L的值也仅仅是O(logN)的。

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

#include
   
    #include
    
     using namespace std;const int MAX = 10000;struct Edge{   	int to, w, next;}edge[MAX << 1];int head[MAX];int n, k;int cnt = 0, Max, root, ans = 0;int dis[MAX], vis[MAX], siz[MAX], maxv[MAX], num;void init(){   	for (int i = 0; i < MAX; i++)	{   		edge[i].next = -1;		head[i] = -1;	}	cnt = 0;}void addedge(int u, int v,int w){   	edge[cnt].to = v;	edge[cnt].w = w;	edge[cnt].next = head[u];	head[u] = cnt++;}void dfssize(int u,int f){   	siz[u] = 1;	maxv[u] = 0;	for (int i = head[u]; i != -1; i = edge[i].next)	{   		int v = edge[i].to;		if (v == f || vis[v])continue;		dfssize(v, u);		siz[u] += siz[v];		if (maxv[u] < siz[v])maxv[u] = siz[v];	}}void dfsroot(int r, int u, int f){   	if (siz[r] - siz[u] > maxv[u])		maxv[u] = siz[r] - siz[u];	if (maxv[u] < Max)	{   		Max = maxv[u];		root = u;	}	for (int i = head[u]; i != -1; i = edge[i].next)	{   		int v = edge[i].to;		if (v == f || vis[v])continue;		dfsroot(r, v, u);	}}void dfsdis(int u, int d, int f){   	dis[num++] = d;	for (int i = head[u]; i != -1; i = edge[i].next)	{   		int v = edge[i].to;		if (v == f || vis[v])continue;		dfsdis(v, d + edge[i].w, u);	}}int calc(int u, int d){   	int ret = 0;	num = 0;	dfsdis(u, 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 dfs(int u){   	Max = MAX;	dfssize(u, 0);	dfsroot(u, u, 0);	ans += calc(root, 0);	vis[root] = 1;	for (int i = head[root]; i != -1; i = edge[i].next)	{   		int v = edge[i].to;		if (vis[v])continue;		ans -= calc(v, edge[i].w);		dfs(v);	}}int main(){   	init();	cin >> n >> k;	for (int i = 1; i < n; i++)	{   		int u, v, w;		cin >> u >> v >> w;		addedge(u, v, w);		addedge(v, u, w);	}	dfs(1);	cout << ans << endl;	system("pause");	return 0;}

转载地址：http://nrdmz.baihongyu.com/

你可能感兴趣的文章