记录编号	214123	评测结果	AAAAAAAAAA
题目名称	[POJ1741][男人八题]树上的点对	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	1.071 s
提交时间	2015-12-14 14:52:47	内存使用	4.83 MiB

#define MAXN 10010UL

#include <cstdio>
#include <cstring>
#include <algorithm>

struct Edge{int v,w,nx;};
Edge edge[MAXN<<1];
int n,ec,k,root,cnt,f[MAXN],size[MAXN],s[MAXN],dis[MAXN],headlist[MAXN];
bool vist[MAXN];

inline int MAX(int a,int b){
	return a>b?a:b;
}

inline void Add_Edge(int u,int v,int w){
	edge[++ec].v=v;
	edge[ec].nx=headlist[u];
	edge[ec].w=w;
	headlist[u]=ec;
	return;
}

inline int in(){
	int x=0,c=getchar();
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return x;
}

void dfs(int p,int fa){
	f[p]=0,size[p]=1;
	for(int i=headlist[p];i;i=edge[i].nx){
		if(fa==edge[i].v||vist[edge[i].v]) continue;
		dfs(edge[i].v,p);
		size[p]+=size[edge[i].v];
		f[p]=MAX(f[p],size[edge[i].v]);
	}
	f[p]=MAX(f[p],cnt-size[p]);
	if(!root||f[p]<f[root]) root=p;
	return;
}

void Build(int p,int fa){
	s[++s[0]]=dis[p];
	for(int i=headlist[p];i;i=edge[i].nx){
		if(fa==edge[i].v||vist[edge[i].v]) continue;
		dis[edge[i].v]=dis[p]+edge[i].w;
		Build(edge[i].v,p);
	}
	return;
}

inline int Cal(int p,int b){
	s[0]=0;dis[p]=b;
	Build(p,0);
	std::sort(s+1,s+s[0]+1);
	int Ans=0,l=1,r=s[0];
	while(l<r){
		while(l<r&&s[l]+s[r]>k) r--;
		Ans+=r-l;l++;
	}
	return Ans;
}

int tree_dc(int p){
	int Ans=Cal(p,0);
	vist[p]=true;
	for(int i=headlist[p];i;i=edge[i].nx){
		if(vist[edge[i].v]) continue;
		Ans-=Cal(edge[i].v,edge[i].w);
		root=0;cnt=size[edge[i].v];
		dfs(edge[i].v,0);
		Ans+=tree_dc(root);
	}
	return Ans;
}

inline bool Work(){
	n=in(),k=in();
	if(!n) return false;
	ec=0;
	memset(vist,false,sizeof(vist));
	memset(headlist,0,sizeof(headlist));
	for(int i=1,a,b,t;i<n;i++){
		a=in(),b=in(),t=in();
		Add_Edge(a,b,t);
		Add_Edge(b,a,t);
	}	
	root=0;cnt=n;dfs(1,0);
	printf("%d\n",tree_dc(root));
	return true;
}

int main(){
	freopen("poj1741_tree.in","r",stdin);
	freopen("poj1741_tree.out","w",stdout);
	while(Work());
	return 0;
}