有一道众所周知的典是 P4178 / poj1741 Tree。

同样的代码，改了输入和 k 范围放洛谷能过，且每个点没跑超过 50ms，放 poj 直接 T 飞。各种改输入卡常均无效。

不知道是 poj 数据比洛谷强还是 C++98 相关的问题。就算 k 变成了 1e7 也不至于 log 变大导致 50ms->1s+罢。

#include <iostream>
#include <cstdio>
#include <vector>
//#include <windows.h>
#define ED cerr<<endl;
#define TS cerr<<"I AK IOI"<<endl;
#define cr(x) cerr<<x<<endl;
#define cr2(x,y) cerr<<x<<" "<<y<<endl;
#define cr3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<endl;
#define cr4(x,y,z,w) cerr<<x<<" "<<y<<" "<<z<<" "<<w<<endl;
#define pii pair<int,int>
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define ll long long
//#define ull unsigned long long
using namespace std;
const int N=4e4+5,M=1e7+5,INF=2e9,mod=1e9+7;
int n,k,ans=0;

struct edge {
	int ne,to,w;
	
	void read(int _ne,int _to,int _w) {
		ne=_ne,to=_to,w=_w;
	};
}e[N<<1];
int head[N],tot=0;
int sz[N],mx[N],vis[N],dis[N],sum=0,rt=0;
int all[N],s[N],t=0,t2=0;
int tr[M];

void update(int u,int x) {
	for(int i=u;i<=k+1;i+=i&(-i)) tr[i]+=x;
}

int query(int u) {
	int res=0;
	for(int i=u;i!=0;i-=i&(-i)) res+=tr[i];
	return res;
}

void add(int u,int v,int w) {
	e[++tot].read(head[u],v,w);
	head[u]=tot;
}

void getrt(int u,int fa) {
	sz[u]=1,mx[u]=0;
	//cr2(u,fa)
	for(int i=head[u];i;i=e[i].ne) {
		int to=e[i].to;
		if(vis[to]||to==fa) continue;
		getrt(to,u),sz[u]+=sz[to];
		mx[u]=max(mx[u],sz[to]);
	}
	mx[u]=max(mx[u],sum-sz[u]);
	if(mx[u]<mx[rt]) rt=u;
}

void getdis(int u,int fa) {
	if(dis[u]>k) return;
	s[++t]=dis[u];
	for(int i=head[u];i;i=e[i].ne) {
		int to=e[i].to;
		if(vis[to]||to==fa) continue;
		dis[to]=dis[u]+e[i].w,getdis(to,u);
	}
}

void work(int u) {
	t2=0;
	for(int i=head[u];i;i=e[i].ne) {
		int to=e[i].to;
		if(vis[to]) continue;
		t=0,dis[to]=e[i].w,getdis(to,u);
		for(int j=1;j<=t;++j) ans+=query(k-s[j]+1)+1;
		for(int j=1;j<=t;++j) update(s[j]+1,1);
		for(int j=1;j<=t;++j) all[++t2]=s[j];
	}
	for(int i=1;i<=t2;++i) update(all[i]+1,-1);
}

void solve(int u) {
	vis[u]=1,work(u);
	for(int i=head[u];i;i=e[i].ne) {
		int to=e[i].to;
		if(vis[to]) continue;
		sum=sz[to],mx[rt=0]=INF;
		getrt(to,-1),getrt(rt,-1); 
		solve(to); 
	}
}

void Main() {
	int u,v,w;ans=tot=0;
	for(int i=1;i<=n;++i) {
		vis[i]=head[i]=0;
	}
	//TS
	for(int i=1;i<=n-1;++i) {
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w),add(v,u,w);
	}
	if(k>M-3) {
		printf("%d\n",n*(n-1)/2);
		return;
	}
	//TS
	mx[rt=0]=INF,sum=n;
	getrt(1,-1),getrt(rt,-1);
	solve(rt);
	printf("%d\n",ans);
}

int main()
{
	//freopen("qwq.in","r",stdin);
	//ios::sync_with_stdio(false);
	//cin.tie(0),cout.tie(0);
	while(scanf("%d%d",&n,&k)) {
		if(!n&&!k) break; 
		Main();
	}
	return 0;
}