记录编号	366182	评测结果	AAAAAAAAAA
题目名称	[POJ1741][男人八题]树上的点对	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.642 s
提交时间	2017-01-23 09:07:04	内存使用	0.70 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=10010;
void solve(int,int);
void dfs_getcenter(int,int,int&);
void dfs_getdis(int);
int calc(int*);
vector<int>G[maxn],W[maxn];
int size[maxn],son[maxn],p[maxn],d[maxn];
int a[maxn],b[maxn];
bool vis[maxn]={false};
int n,k,x,y,z,ans;
int main(){
	freopen("poj1741_tree.in","r",stdin);
	freopen("poj1741_tree.out","w",stdout);
	while(scanf("%d%d",&n,&k)==2&&n&&k){
		fill(vis,vis+n+1,false);
		ans=0;
		for(int i=1;i<=n;i++){
			G[i].clear();
			W[i].clear();
		}
		for(int i=1;i<n;i++){
			scanf("%d%d%d",&x,&y,&z);
			G[x].push_back(y);
			W[x].push_back(z);
			G[y].push_back(x);
			W[y].push_back(z);
		}
		solve(1,n);
		printf("%d\n",ans);
	}
	return 0;
}
void solve(int x,int s){
	int u=0;
	dfs_getcenter(x,s,u);
	vis[x=u]=true;
	a[a[0]=1]=0;
	for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]){
		d[G[x][i]]=W[x][i];
		p[G[x][i]]=0;
		b[0]=0;
		dfs_getdis(G[x][i]);
		ans-=calc(b);
		for(int i=1;i<=b[0];i++)a[++a[0]]=b[i];
	}
	ans+=calc(a);
	for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]])solve(G[x][i],size[G[x][i]]);
}
void dfs_getcenter(int x,int s,int &u){
	size[x]=1;
	son[x]=0;
	for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]&&G[x][i]!=p[x]){
		p[G[x][i]]=x;
		dfs_getcenter(G[x][i],s,u);
		size[x]+=size[G[x][i]];
		if(size[G[x][i]]>size[son[x]])son[x]=G[x][i];
	}
	if(!u||max(s-size[x],size[son[x]])<max(s-size[u],size[son[u]]))u=x;
}
void dfs_getdis(int x){
	b[++b[0]]=d[x];
	size[x]=1;
	for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]&&G[x][i]!=p[x]){
		p[G[x][i]]=x;
		d[G[x][i]]=d[x]+W[x][i];
		dfs_getdis(G[x][i]);
		size[x]+=size[G[x][i]];
	}
}
int calc(int *a){
	sort(a+1,a+a[0]+1);
	int ans=0,i=1,j=a[0];
	while(i<j){
		while(j>i&&a[i]+a[j]>k)j--;
		ans+=j-i;
		i++;
	}
	return ans;
}