题意：给定一棵 N (1 <= N <= 10000) 个结点的带权树,定义 dist(u, v) 为u, v 两点间的最短路径长度,路径的长度定义为路径上所有边的
权和。再给定一个 K (1 <= K <= 10^9 ) ,如果对于不同的两个结点 a, b ,如果满足 dist (a, b) <=K ,则称 (a, b) 为合法点对。求合法点的
个数。
思路：点分治。详见漆子超的《分治算法在树的路径问题中的应用》，详见代码：
// file name: poj1741.cpp //
// author: kereo //
// create time: 2014年10月18日 星期六 16时59分24秒 //
//***********************************//
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=10000+100;
const double eps=1e-8;
const int inf=0x3fffffff;
const int mod=1000000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
int n,k,edge_cnt,size,root,ans;
int head[MAXN],d[MAXN],vis[MAXN],sz[MAXN],dp[MAXN];
vector<int>vec;
struct Edge{
int v,w;
int next;
}edge[MAXN<<1];
void init(){
edge_cnt=0;
memset(vis,0,sizeof(vis));
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w){
edge[edge_cnt].v=v;
edge[edge_cnt].w=w;
edge[edge_cnt].next=head[u];
head[u]=edge_cnt++;
}
void getroot(int u,int fa){
dp[u]=0; sz[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(v == fa || vis[v])
continue;
getroot(v,u);
dp[u]=max(dp[u],sz[v]);
sz[u]+=sz[v];
}
dp[u]=max(dp[u],size-dp[u]);
if(dp[u]<dp[root])
root=u;
}
void getdepth(int u,int fa){
vec.push_back(d[u]);
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(v == fa || vis[v])
continue;
d[v]=d[u]+edge[i].w;
getdepth(v,u);
}
}
int cal(int u,int dis){
vec.clear(); d[u]=dis;
getdepth(u,0);
int res=0;
sort(vec.begin(),vec.end());
for(int l=0,r=vec.size()-1;l<r;){
if(vec[l]+vec[r]<=k){
res+=r-l;
l++;
}
else
r--;
}
return res;
}
void work(int u){
ans+=cal(u,0);
vis[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(vis[v])
continue;
ans-=cal(v,edge[i].w);
root=0;
getroot(v,0); size=sz[v];
work(root);
}
}
int main()
{
while(~scanf("%d%d",&n,&k) && n+k){
init();
int u,v,w;
for(int i=0;i<n-1;i++){
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w); addedge(v,u,w);
}
ans=0;
root=0; size=n; dp[root]=inf;
getroot(1,0);
work(root);
printf("%d\n",ans);
}
return 0;
}