记录编号	363657	评测结果	AAAAAAAAAA
题目名称	[POJ1741][男人八题]树上的点对	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.789 s
提交时间	2017-01-12 14:00:26	内存使用	4.20 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct edge{
	int f,t,l;
	edge(int F=0,int T=0,int L=0){
		f=F;t=T;l=L;
	}
}w[N];
int n,k,head[N],tail[N],next[N],cnt;
void add(int f,int t,int l){
	w[++cnt]=edge(f,t,l);
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
}
int s[N],h[N],dis[N],big[N],root,size,sum;
bool vis[N];
void getroot(int x,int fa){
	s[x]=1;big[x]=0;
	for (int i=head[x];i;i=next[i]){
		int v=w[i].t;
		if (vis[v]||v==fa) continue;
		getroot(v,x);
		s[x]+=s[v];
		big[x]=max(big[x],s[v]);
	}
	if (big[x]<=size/2&&s[x]>=size/2) root=x;
}
void geth(int x,int fa){
	h[++sum]=dis[x];
	for (int i=head[x];i;i=next[i]){
		int v=w[i].t;
		if (vis[v]||v==fa) continue;
		dis[v]=dis[x]+w[i].l;
		geth(v,x);
	}
}
int calc(int x,int H){
	dis[x]=H;sum=0;
	geth(x,0);
	sort(h+1,h+sum+1);
	int ans=0;
	for (int l=1,r=sum;l<r;l++){
		while (l<r&&h[l]+h[r]>k) r--;
		ans+=r-l;
	}
	return ans;
}
int DC(int x){
	int ans=calc(x,0);
	vis[x]=1;
	getroot(x,0);
	for (int i=head[x];i;i=next[i]){
		int u=w[i].t;
		if (vis[u]) continue;
		ans-=calc(u,w[i].l);
		root=0;size=s[u];getroot(u,0);
		ans+=DC(root);
	}
	return ans;
}
int main()
{
	freopen("poj1741_tree.in","r",stdin);
	freopen("poj1741_tree.out","w",stdout);
	while (1){
		scanf("%d%d",&n,&k);
		if (!n&&!k) break;
		for (int i=1;i<=n;i++) head[i]=tail[i]=vis[i]=0;
		for (int i=1;i<=cnt;i++) next[i]=0;
		cnt=0;
		for (int i=1;i<n;i++){
			int f,t,l;
			scanf("%d%d%d",&f,&t,&l);
			add(f,t,l);add(t,f,l);
		}
		root=0;size=n;getroot(1,0);
		printf("%d\n",DC(root));
	}
	return 0;
}