程序RE，多测，范围 $n\le 10^4$,边权$\le1001$

链接POJ1741

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<cstdlib>
using namespace std;
void read(){}
template<typename _Tp,typename ..._Tps>
void read(_Tp &x,_Tps &...Ar){
	x=0;char c=getchar();bool flag=0;
	while(c<'0'||c>'9')flag|=(c=='-'),c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
	if(flag)x=-x;
	read(Ar...);
}
const int N=1e4+10;
int n,m;
struct tree{
	int ls,rs,siz,rnd,val;
}a[N];
int cnt,root,root1,root2,root3;
void pushup(int rt){
	a[rt].siz=a[a[rt].ls].siz+a[a[rt].rs].siz+1;
}
void split(int rt,int val,int &x,int &y){
	if(!rt)return x=y=0,void();
	if(val<a[rt].val)y=rt,split(a[rt].ls,val,x,a[rt].ls);
	else x=rt,split(a[rt].rs,val,a[rt].rs,y);
	pushup(rt);
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(a[x].rnd<a[y].rnd)return a[x].rs=merge(a[x].rs,y),pushup(x),x;
	return a[y].ls=merge(x,a[y].ls),pushup(y),y;
}
void insert(int val){
	a[++cnt]=(tree){0,0,1,rand(),val};
	split(root,val,root1,root2);
	root=merge(merge(root1,cnt),root2);
}
void clear(){
	cnt=root=0;
}
int less_cnt(int val){
	split(root,val,root1,root2);
	int ans=a[root1].siz;
	root=merge(root1,root2);
	return ans;
}
struct edges{
	int to,w,nex;
}edge[N*2];
int head[N],kk;
void add(int u,int v,int w){edge[++kk]=(edges){v,w,head[u]};head[u]=kk;}
int siz[N],son[N],d[N];
void dfs1(int u,int fa){
	siz[u]=1;
	for(int i=head[u];i;i=edge[i].nex){
		int v=edge[i].to;
		if(v==fa)continue;
		d[v]=d[u]+edge[i].w;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
int ans;
void calc(int u,int fa,int t){
	ans+=less_cnt(m+t*2-d[u]);
	for(int i=head[u];i;i=edge[i].nex){
		int v=edge[i].to;
		if(v==fa)continue;
		calc(v,u,t);
	}
}
void ins(int u,int fa){
	insert(d[u]);
	for(int i=head[u];i;i=edge[i].nex){
		int v=edge[i].to;
		if(v==fa)continue;
		ins(v,u);
	}
}
void dfs2(int u,int fa){
	for(int i=head[u];i;i=edge[i].nex){
		int v=edge[i].to;
		if(v==fa||v==son[u])continue;
		dfs2(v,u);
	}
	clear();
	if(son[u])dfs2(son[u],u),ans+=less_cnt(m+d[u]);
	insert(d[u]);
	for(int i=head[u];i;i=edge[i].nex){
		int v=edge[i].to;
		if(v==fa||v==son[u])continue;
		calc(v,u,d[u]);
		ins(v,u);
	}
}
int get(){
	int i,u,v,w;
	read(n,m);if((n|m)==0)return 0;
	for(i=1;i<n;i++)read(u,v,w),add(u,v,w),add(v,u,w);
	dfs1(1,-1);
	dfs2(1,-1);
	printf("%d\n",ans);
	for(kk=ans=0,clear(),i=1;i<=n;i++)head[i]=0;
	return 1;
} 
int main(){
	srand(time(0));
	while(get());
	return 0;
}