POJ Tree

點的分質。。   詳細見09年漆子超論文。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 10010
#define INF 1000000000
using namespace std;

int n,m,tot,cent,t,res,mi;

int head[MAXN],mnum[MAXN],summ[MAXN],vis[MAXN],dis[MAXN];

struct edge{
	int to;
	int l;
	int next;
}edge[MAXN*2];

void init(){
	tot=0;
	for(int i=0;i<=n;i++)
		head[i]=-1;
}

void add_edge(int a,int b,int c){
	edge[tot].to=b;
	edge[tot].l=c;
	edge[tot].next=head[a];
	head[a]=tot++;
}

void dfs1(int s,int f){
	summ[s]=1;
	mnum[s]=0;
	for(int i=head[s];i!=-1;i=edge[i].next){
		int To=edge[i].to;
		int w=edge[i].l;
		if(vis[To] || To==f)	continue;
		dfs1(To,s);
		summ[s]+=summ[To];
		if(mnum[s]<summ[To])
			mnum[s]=summ[To];
	}
}


void zhongxin(int r,int s,int f){
	if(summ[r]-summ[s]>mnum[s])	mnum[s]=summ[r]-summ[s];
	if(mnum[s]<mi){
		mi=mnum[s];
		cent=s;
	}
	for(int i = head[s]; i != -1; i = edge[i].next)
    {
        int To = edge[i].to;
        if(To != f && !vis[To])	zhongxin(r, To, s);
    }
}


void caldis(int s,int d,int f){
	dis[t++]=d;
	for(int i=head[s];i!=-1;i=edge[i].next){
		int To=edge[i].to;
		int w=edge[i].l;
		if(vis[To] || To==f) continue;
		caldis(To,d+w,s);
	}
}


int calcu(int s,int d){
	int ans=0;
	t=0;
	caldis(s,d,-1);
	sort(dis,dis+t);
	int i=0,j=t-1;
	while(i<j){
		while(dis[i]+dis[j]>m && i<j) j--;
		ans+=j-i;
		i++;
	}
	return ans;
}


void dfs(int s){
	int i;
	mi=n;
	/*memset(mnum,0,sizeof mnum);
	for(i=0;i<=n;i++)
		summ[i]=1;*/
	//puts("1");
	dfs1(s,-1);
	zhongxin(s,s,-1);
	res+=calcu(cent,0);
	//printf("DD%d\n",res);
	vis[cent]=1;
	for(i=head[cent];i!=-1;i=edge[i].next){
		int To=edge[i].to;
		int w=edge[i].l;
		if(vis[To]) continue;
		res-=calcu(To,w);
		dfs(To);
	}
}


int main(){
	int i;
	int u,v,l;
	while(~scanf("%d%d",&n,&m)){
		if(n==0 && m==0)	break;
		init();
		res=0;
		memset(vis,0,sizeof vis);
		for(i=0;i<n-1;i++){
			scanf("%d%d%d",&u,&v,&l);
			add_edge(u,v,l);
			add_edge(v,u,l);
		}
		dfs(1);
		printf("%d\n",res);
	}
	return 0;
}

/*
5 4
1 2 3
1 3 1
1 4 2
3 5 1
*/