记录编号	385227	评测结果	AAAAAAAAAA
题目名称	[POJ1741][男人八题]树上的点对	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.738 s
提交时间	2017-03-20 16:35:35	内存使用	0.70 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <list>
using namespace std;
#define MAXN 10023
int n, k;
int div_size, root;
int cnt;
vector<int> G[MAXN];
vector<int> D[MAXN]; 
int deep[MAXN], size[MAXN], wei[MAXN];
bool vis[MAXN];
void get_root(int u, int f){
	size[u] = 1;
	int son = 0;
	for(int i = 0; i < G[u].size(); i++){
		int to = G[u][i];
	    if(to != f && !vis[to]){
			get_root(to, u);
			size[u] += size[to];
			if(size[son] < size[to])
				son = to;
		}
	}
	wei[u] = max(size[son], div_size-size[son]);
	if(wei[root] > wei[u])root = u;	
}
int dfs_tim;
int dfs_deep[MAXN];
int calc_deep(int u, int f){
	dfs_deep[++dfs_tim] = deep[u];
	for(int i = 0; i < G[u].size(); i++){
		int to = G[u][i];
		if(to == f || vis[to])continue;
		deep[to] = deep[u]+D[u][i];
		calc_deep(to, u);
	}
}
int calc_ans(int u, int d = 0){
	deep[u] = d;
	dfs_tim = 0;
	calc_deep(u, 0);
	sort(dfs_deep+1, dfs_deep+1+dfs_tim);
	int l = 1, r = dfs_tim, ans = 0;
	while(l < r){
		while((l < r) && dfs_deep[l]+dfs_deep[r] > k)r--;
		ans += r-l;
		l++;
	}		
	return ans;
}
void div_process(int u){
	div_size = size[u];
	vis[u] = true;
    int ans = calc_ans(u);
	for(int i = 0; i < G[u].size(); i++){
		int to = G[u][i];
		if(vis[to])continue;
		ans -= calc_ans(to, D[u][i]);
		
		root = 0;
		div_size = size[to];
		get_root(to, u);
		div_process(root);
	}
	cnt += ans;	
}
void clear(){
	for(int i = 1; i <= n; i++)G[i].clear(), D[i].clear();
	memset(vis, false, sizeof(bool)*(n+1));
}
void read(){
	for(int i = 1; i < n; i++){
		int u, v, c; scanf("%d %d %d", &u, &v, &c);
		G[u].push_back(v); G[v].push_back(u);
		D[u].push_back(c); D[v].push_back(c); 
	}	
}
void solve(){
	size[0] = 0;
	wei[0] = (int)2e9;
	cnt = 0;
	div_size = n;
	root = 0;
	get_root(1, 0);
	div_process(root);
	printf("%d\n", cnt);
}
int main(){	
	freopen("poj1741_tree.in", "r", stdin);
	freopen("poj1741_tree.out", "w", stdout);
	while(~scanf("%d %d", &n, &k) && n && k){
		clear();
		read();	
		solve(); 
	}	
	return 0;
}