【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
나의 포인트 1 번 문제 ~ ~ ~
나무의 경 로 는 두 종류 로 나 뉜 다.
뿌리 결산 점 통과 하기;근결 점 을 거치 지 않다.
그러면 우 리 는 모든 점 을 뿌리 로 선택 한 다음 에 이 노드 의 길 이 를 계산 할 수 있 습 니 다. < = 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
",ans);
	}
	return 0;
}

깨 달 음:
1. TLE 는 Solve (root) 때문에 Solve (y) 라 고 썼 다.
2. 점 분 치 의 관건 은 경 로 를 통 해 근 결 점 과 근 결 점 을 거치 지 않 고 재 귀 방법 을 찾 는 것 이다.