记录编号	465853	评测结果	AAAAAAAAAA
题目名称	[POJ1741][男人八题]树上的点对	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.128 s
提交时间	2017-10-28 00:03:26	内存使用	0.67 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cassert>
#include<stack>
using namespace std;
const int SIZEN=10010,MXINT=0x7fffffff;
class Node{
public:
	int l,r;
	int key;
	int hkey;
	int sz;
	#define l(x) treap[x].l
	#define r(x) treap[x].r
	#define key(x) treap[x].key
	#define hkey(x) treap[x].hkey
	#define sz(x) treap[x].sz
}treap[SIZEN];
int root,tot=0;
int getrand(void){
	return ((rand()<<15)|rand())&MXINT;
}
int newnode(int val){
	tot++;
	l(tot)=r(tot)=0;
	key(tot)=val;
	hkey(tot)=getrand();
	sz(tot)=1;
	return tot;
}
void update(int x){
	sz(x)=sz(l(x))+sz(r(x))+1;
}
int zig(int x){//left rotate
	int y=l(x);
	assert(y!=0);
	l(x)=r(y);
	r(y)=x;
	update(x);
	update(y);
	return y;
}
int zag(int x){
	int y=r(x);
	assert(y!=0);
	r(x)=l(y);
	l(y)=x;
	update(x);
	update(y);
	return y;
}
int insert(int x,int val){
	if(val<=key(x)){
		if(!l(x)) l(x)=newnode(val);
		else l(x)=insert(l(x),val);
	}
	else{
		if(!r(x)) r(x)=newnode(val);
		else r(x)=insert(r(x),val);
	}
	if(hkey(l(x)) < hkey(x)) x=zig(x);
	else if(hkey(r(x)) < hkey(x)) x=zag(x);
	else update(x);
	return x;
}
int count_lower(int x,int val){//in subtree of x, how many nodes <=val
	if(!x) return 0;
	if(val<key(x)) return count_lower(l(x),val);
	else return sz(l(x))+1+count_lower(r(x),val);
}
void init_treap(void){
	tot=0;
	l(0)=r(0)=0;
	key(0)=0;
	sz(0)=0;
	hkey(0)=MXINT;
	root=newnode(-MXINT);
	root=insert(root,MXINT);
}
int N,K,ans;
vector<pair<int,int> > c[SIZEN];
bool used[SIZEN]={0};
int subsz[SIZEN]={0};
int find_G(int x,int rootsz,int fa,int &nowans,int &nowval){//return subtree size
	int ret=1,mxson=0;
	for(int i=0;i<c[x].size();i++){
		int y=c[x][i].first;
		if(y==fa||used[y]) continue;
		int s=find_G(y,rootsz,x,nowans,nowval);
		ret+=s;
		mxson=max(mxson,s);
	}
	mxson=max(mxson,rootsz-ret);
	if(nowans==-1||mxson<nowval){
		nowans=x;
		nowval=mxson;
	}
	return ret;
}
stack<int> S;
int count_subtree(int x,int fa,int dep){//count answer in a subtree, and push all depths in s
	subsz[x]=1;
	int ans=count_lower(root,K-dep)-1;//note that it counts sentinel
	S.push(dep);
	for(int i=0;i<c[x].size();i++){
		int y=c[x][i].first,w=c[x][i].second;
		if(y==fa||used[y]) continue;
		ans+=count_subtree(y,x,dep+w);
		subsz[x]+=subsz[y];
	}
	return ans;
}
int count_by(int g){
	while(!S.empty()) S.pop();
	init_treap();
	root=insert(root,0);
	int ans=0;
	for(int i=0;i<c[g].size();i++){
		int y=c[g][i].first,w=c[g][i].second;
		if(used[y]) continue;
		ans+=count_subtree(y,g,w);
		while(!S.empty()){
			int d=S.top();S.pop();
			root=insert(root,d);
		}
	}
	return ans;
}
int DQ(int x,int rootsz){//Dairy-Queen, for sure
	int g=-1,nowval=-1;
	find_G(x,rootsz,0,g,nowval);
	used[g]=true;
	int ans=count_by(g);
	for(int i=0;i<c[g].size();i++){
		int y=c[g][i].first;
		if(!used[y]){
			ans+=DQ(y,subsz[y]);
		}
	}
	return ans;
}
void work(void){
	ans=0;
	memset(used,0,sizeof(used));
	printf("%d\n",DQ(1,N));
}
bool read(void){
	scanf("%d%d",&N,&K);
	if(!N&&!K) return false;
	for(int i=1;i<=N;i++) c[i].clear();
	for(int i=1;i<N;i++){
		int a,b,w;
		scanf("%d%d%d",&a,&b,&w);
		c[a].push_back(make_pair(b,w));
		c[b].push_back(make_pair(a,w));
	}
	return true;
}
int main(){
	freopen("poj1741_tree.in","r",stdin);
	freopen("poj1741_tree.out","w",stdout);
	while(read()) work();
	return 0;
}