记录编号	494021	评测结果	AAAAAAAAAA
题目名称	[POJ1741][男人八题]树上的点对	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	1.696 s
提交时间	2018-04-08 09:50:12	内存使用	0.29 MiB

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10010;
struct poi{int u,w;};
vector<poi>p[maxn];
int n,k,cnt,ans,Sum,root,d[maxn],sz[maxn],siz[maxn],dis[maxn];
bool vis[maxn];
inline void init(){
	for(int i=1;i<=n;i++)p[i].clear();
	memset(vis,0,sizeof(vis));
}
inline void getdis(int x,int fa){
	d[++cnt]=dis[x];
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i].u,w=p[x][i].w;
		if(vis[u]||u==fa)continue;
		dis[u]=dis[x]+w;
		getdis(u,x);
	}
}
inline void getroot(int x,int fa){
	siz[x]=1,sz[x]=0;
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i].u;
		if(vis[u]||u==fa)continue;
		getroot(u,x);
		siz[x]+=siz[u];
		sz[x]=max(sz[x],siz[u]);
	}
	sz[x]=max(sz[x],Sum-siz[x]);
	if(sz[x]<sz[root])root=x;
}
int calc(int x,int v){
	cnt=0,dis[x]=v;
	getdis(x,0);
	sort(d+1,d+1+cnt);
	int res=0;
	for(int l=1,r=cnt;l<=cnt;l++){
		while(d[l]+d[r]>k)r--;
		if(r<=l)break;
		res+=r-l;
	}
	return res;
}
inline void build(int x){
	ans+=calc(x,0);
	vis[x]=1;
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i].u,w=p[x][i].w;
		if(vis[u])continue;
		ans-=calc(u,w);
		Sum=siz[u],root=0,getroot(u,0);
		build(root);
	}
}
int main(){
	freopen("poj1741_tree.in","r",stdin);
	freopen("poj1741_tree.out","w",stdout);
	while(scanf("%d%d",&n,&k)&&n&&k){
		int u,v,w;
		init();
		for(int i=1;i<n;i++){
			scanf("%d%d%d",&u,&v,&w);
			p[u].push_back((poi){v,w});
			p[v].push_back((poi){u,w});
		}
		sz[0]=Sum=n;ans=root=0;
		getroot(1,0);build(root);
		printf("%d\n",ans);
	}
	return 0;
}