记录编号	386073	评测结果	AAAAAAAAAA
题目名称	[POJ1741][男人八题]树上的点对	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	0.558 s
提交时间	2017-03-23 15:07:40	内存使用	0.71 MiB

#include <stdio.h>
#include <ctime>
#include <algorithm>
#include <cstring>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <cmath>
#include <vector>
#define Mem(a, b) memset(a, b, sizeof a)
#define Mcpy(a, b) memcpy(a, b, sizeof a)
#define RG register
#define IL inline
using namespace std;
typedef long long LL;
typedef unsigned int uint;
typedef unsigned long long ull;
IL void qkin(RG int &res){
	RG int x,f=1; RG char ch;
	while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')f=-1;x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;res=x*f;}
IL void read(RG int &A){ qkin(A); }
IL void read(RG int &A,RG int &B){ qkin(A),qkin(B); }
IL void read(RG int &A,RG int &B,RG int &C){ qkin(A),qkin(B),qkin(C); }
#define Gets(s) scanf("%s", s+1);
const double INF = 1e60;
const int inf = 0x7f7f7f7f;
const double Pi = acos(-1);
const double eps = 1e-8;
const int maxn = 10010;

int n,K,len,head[maxn];
struct Edge
{
	int to,next,dis;
}e[maxn<<1];
void add_edge(int x,int y,int z){
	e[++len].to = y;
	e[len].dis = z;
	e[len].next = head[x];
	head[x] = len;
}
bool vis[maxn];
int root,Sz,dep[maxn],size[maxn],mxsz[maxn],tot;

void getroot(int x,int fa){
	size[x] = 1; mxsz[x] = 0;
	for(int i=head[x]; i; i=e[i].next){
		int p = e[i].to;
		if(vis[p] || fa == p) continue;
		getroot(p, x);
		size[x] += size[p];
		mxsz[x] = max(mxsz[x], size[p]);
	}
	mxsz[x] = max(mxsz[x], Sz - size[x]);
	if(!root || mxsz[root]>mxsz[x]) root = x;
}
void getdep(int x,int fa,int dis){
	dep[++tot] = dis;
	for(int i=head[x]; i; i=e[i].next){
		int p = e[i].to;
		if(vis[p] || p == fa) continue;
		getdep(p, x, dis + e[i].dis);
	}
}
int calc(int x,int base){
	tot = 0;
	getdep(x, 0, base);
	sort(dep+1, dep+1+tot);
	int ans = 0, l = 1, r = tot;
	while(l<r){
		while(l<r && dep[l]+dep[r]>K) r--;
		ans += r-l;
		l++;
	}
	return ans;
}
int solve(int x){
	vis[x] = 1;
	int ans = calc(x, 0);
	for(int i=head[x]; i; i=e[i].next){
		int p = e[i].to;
		if(!vis[p]){
			ans -= calc(p, e[i].dis);
			root = 0; Sz = size[p]; getroot(p, 0);
			ans += solve(root);
		}
	}
	return ans;
}

void init(){
	len = 0;
	Mem(vis, 0);
	Mem(head, 0);
}
bool Read(){
	read(n, K);
	if(!n && !K) return 0;
	init();
	int x, y, z;
	for(int i=1; i<n; i++){
		read(x, y, z);
		add_edge(x, y, z); add_edge(y, x, z);
	}
	root = 0; Sz = n; getroot(1, 0); 
	printf("%d\n", solve(root));
	return 1;
}
int main(){
#define HAHA LALA
#ifdef HAHA
	freopen("poj1741_tree.in", "r", stdin);
	freopen("poj1741_tree.out", "w", stdout);
#endif
	while( Read() );
	return 0;
}