记录编号	390584	评测结果	AAAAATTTTT
题目名称	[POJ1741][男人八题]树上的点对	最终得分	50
用户昵称	Go灬Fire	是否通过	未通过
代码语言	C++	运行时间	5.359 s
提交时间	2017-04-03 14:29:11	内存使用	47.05 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
const int maxn=1000050;
char ch;
inline void Read(register int & x){
	while(ch=getchar(),ch<'0' || ch>'9');
	x=ch-48;
	while(ch=getchar(),ch>='0' && ch<='9')x=x*10+ch-48;
}
struct Edge{
	int next,to,dis;
}e[maxn<<1];
int len,head[maxn];
inline void Insert(int x,int y,int z){
	len++;e[len].to=y;e[len].next=head[x];e[len].dis=z;head[x]=len;
}
int n,L;
int RT,sum,size[maxn],Max[maxn];
bool vis[maxn];
inline int bmax(int x,int y){
	if(x>y) return x;
	return y;
}
inline void getroot(int x,int fa){
	size[x]=1;Max[x]=0;
	for(register int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(j^fa && !vis[j]){
			getroot(j,x);
			size[x]+=size[j];
			Max[x]=bmax(Max[x],size[j]);
		}
	}
	Max[x]=bmax(Max[x],sum-size[x]);
	if(Max[x]<Max[RT]) RT=x;
}
LL ans=0;
int c[maxn],Tim[maxn],tim;
#define Lowbit(x) (x&(-x))
inline int Query(int x){
	int res=0;
	for(register int i=x;i;i-=Lowbit(i)) {
		if(Tim[i]^tim) {Tim[i]=tim;c[i]=0;}
		res+=c[i];
	}
	return res;
}
inline void Update(register int x,register int add){
	for(register int i=x;i<=L;i+=Lowbit(i)){
		if(Tim[i]^tim){Tim[i]=tim;c[i]=0;}
		c[i]+=add;
	}
}
int nowdep,num[maxn];
inline void Dfs(int x,int fa,int dep){
	if(dep>L) return;
	nowdep=bmax(nowdep,dep);
	num[dep]++;
	for(int i=head[x];i;i=e[i].next){
		if(e[i].to^fa && !vis[e[i].to])
			Dfs(e[i].to,x,dep+e[i].dis);
	}
}
inline void calc(int x){
	tim++;
	Update(1,1);
	register int i,j,k;
	for(i=head[x];i;i=e[i].next){
		j=e[i].to;
		if(vis[j])continue;
		nowdep=0;
		Dfs(j,0,1+e[i].dis);
		for(k=2;k<=nowdep;k++) ans+=(LL)num[k]*Query(L-k+1);
		for(k=2;k<=nowdep;k++) Update(k,num[k]),num[k]=0;
	}
}
inline void Solve(int x){
	vis[x]=true;
	calc(x);
	for(register int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(!vis[j]){
			RT=0;sum=size[j];
			getroot(j,0);
			Solve(RT);
		}
	}
}
inline void Init();
int main(){
	freopen("poj1741_tree.in","r",stdin);freopen("poj1741_tree.out","w",stdout);
	while(scanf("%d%d",&n,&L) && L && n)Init();
    getchar();getchar();
    return 0;
}
inline void Init(){
	memset(vis,0,sizeof(vis));
	memset(head,0,sizeof(head));
	len=0;ans=0;
	L++;
	register int i,x,y,z;
	for(i=1;i<n;i++){
		Read(x);Read(y);Read(z);
		Insert(x,y,z);Insert(y,x,z);
	}
	RT=0;Max[RT]=Inf;
	sum=n;
	getroot(1,0);
	Solve(RT);
	printf("%lld\n",ans);
}