首页 > 代码库 > 【POJ 1741】Tree

【POJ 1741】Tree

Tree
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 11570 Accepted: 3626

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

8

Source

LouTiancheng@POJ

我的点分治第一题~~~


树上的路径分为两类:

经过根结点;不经过根结点。


那么我们可以选择每一个点为根,然后计算经过这个根结点的长度<=k的路径,再按照相同的方法计算他的所有子树中的路径条数,这样就能不重不漏。


如何计算经过根结点且长度<=k的路径条数?


用所有的减去在同一棵子树中的就可以。


怎么计算所有的长度<=k的路径?


用dfs求出每个点的深度,存在一个数组里,然后从小到大排个序,用两个指针扫:l=1,r=tot,在l增加的过程中满足dep[l]+dep[r]<=k的r指针是不增的,所以O(n)可以出解,再加上sort的O(nlogn),这个操作的复杂度为O(nlogn)。


所以总的复杂度为O(递归层数*nlogn),如何让递归层数最少?


每次让重心(找重心【POJ 1655】)当根结点,递归层数是logn的。


于是总复杂度为O(nlog^2n)~


#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define M 10005
using namespace std;
struct edge
{
	int y,ne,l;
}e[M*100];
int ans,all,h[M],f[M],done[M],s[M],dep[M],tot=0,size,n,k,root;
void Addedge(int x,int y,int l)
{
	tot++;
	e[tot].y=y;
	e[tot].ne=h[x];
	e[tot].l=l;
	h[x]=tot;
}
void Getroot(int x,int fa)
{
	f[x]=0;
	s[x]=1;
	for (int i=h[x];i;i=e[i].ne)
	{
		int y=e[i].y;
		if (y==fa||done[y]) continue;
		Getroot(y,x);
		s[x]+=s[y];
		f[x]=max(f[x],s[y]);
	}
	f[x]=max(f[x],size-s[x]);
	if (f[x]<f[root]) root=x;
}
void Getdep(int x,int fa,int de)
{
	dep[++all]=de;
	s[x]=1;
	for (int i=h[x];i;i=e[i].ne)
	{
		int y=e[i].y,l=e[i].l;
		if (y==fa||done[y]) continue;
		Getdep(y,x,de+l);
		s[x]+=s[y];
	}
}
int calc(int x,int de)
{
	int an=0;
	all=0;
	Getdep(x,0,de);
	sort(dep+1,dep+1+all);
	for (int l=1,r=all;l<r;)
		if (dep[l]+dep[r]<=k) an+=r-l++;
	    else r--;
	return an;
}
void Solve(int x)
{
	ans+=calc(x,0);
	done[x]=true;
	for (int i=h[x];i;i=e[i].ne)
	{
		int y=e[i].y;
		if (done[y]) continue;
		ans-=calc(y,e[i].l);
		size=f[0]=s[y];
		Getroot(y,root=0);
		Solve(root);
	}
}
int main()
{
    while (scanf("%d%d",&n,&k)==2)
	{
		if (n==k&&n==0) break;
		tot=0;
		for (int i=1;i<=n;i++)
			h[i]=0,done[i]=false;
		for (int i=1;i<n;i++)
		{
			int x,y,l;
			scanf("%d%d%d",&x,&y,&l);
			Addedge(x,y,l);
			Addedge(y,x,l);
		}
		ans=0;
		f[0]=size=n;
	        Getroot(1,root=0);
		Solve(root);
		printf("%d\n",ans);
	}
	return 0;
}

技术分享


感悟:

1.TLE是因为Solve(root),写成Solve(y)了。。


2.点分治的关键是要知道路径分经过根结点和不经过根结点,由此找到递归方法。

【POJ 1741】Tree