记录编号	586541	评测结果	AAAAAAAAAA
题目名称	[POJ1741][男人八题]树上的点对	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.622 s
提交时间	2024-01-31 22:08:29	内存使用	7.90 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 4e4+10;
int n,K;
ll ans;
struct made{
	int ver,nx,ed;
}e[N<<1];
int hd[N],tot;
bool v[N];
void add(int x,int y,int z){
	tot++;
	e[tot].nx = hd[x],e[tot].ver = y,e[tot].ed = z,hd[x] = tot;
}
int size[N],mx[N],rt,sum;
void calsize(int x,int fa){
	size[x] = 1;mx[x] = 0;
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(y == fa || v[y])continue;
		calsize(y,x);
		size[x] += size[y];
		mx[x] = max(mx[x],size[y]);
	}
	mx[x] = max(mx[x],sum-size[x]);
	if(mx[x] < mx[rt])rt = x;
} 
int dis[N],cnt[N],b[N],sub[N],idx;
bool cmp(int x,int y){
	return dis[x] < dis[y];
}
void caldis(int x,int fa){
	if(fa == rt)b[x] = x;
	else b[x] = b[fa];
	sub[++idx] = x,cnt[b[x]]++;
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver,z = e[i].ed;
		if(y == fa || v[y])continue;
		dis[y] = dis[x] + z;
		caldis(y,x);
	}
}
void dfs(int x,int fa){
	idx = 0,v[x] = 1;
	sub[++idx] = x,dis[x] = cnt[x] = 0,b[x] = x;//b[x] = x
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(y == fa || v[y])continue;
		dis[y] = e[i].ed,cnt[y] = 0;
		caldis(y,x);
	}
	sort(sub+1,sub+1+idx,cmp);
	int l = 1,r = idx;
	while(l < r){
		while(dis[sub[l]] + dis[sub[r]] > K)cnt[b[sub[r]]]--,r--;
		ans += (long long)r - l - cnt[b[sub[l]]];
		l++,cnt[b[sub[l]]]--;
	}
	//
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(y == fa || v[y])continue;
		rt = 0,sum = size[y];mx[0] = INT_MAX;
		calsize(y,x),calsize(rt,0);
		dfs(rt,0);
	}
} 
void first(){
	tot = 0;
	memset(hd,0,sizeof hd);
	memset(v,0,sizeof v);
}
int main(){
	freopen("poj1741_tree.in","r",stdin);
	freopen("poj1741_tree.out","w",stdout);
	while(~scanf("%d%d",&n,&K) && n){
		first();
		ans = 0;
		for(int i = 1;i < n;i++){
			int x,y,z;
		    scanf("%d%d%d",&x,&y,&z);
			add(x,y,z),add(y,x,z); 
		}
		rt = 0,mx[0] = INT_MAX,sum = n;
		calsize(1,0),calsize(rt,0);
		dfs(rt,0);
		printf("%lld\n",ans);
	}
	
	return 0;
	
}