[PKU/POJ][1741][Tree][树的分治]

LTC 男人八题之一，解题报告见09看论文。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

int const N= 10010, inf= 0x7fffffff;
int n, k, cnt, tot, root, size, nchild, first, last, pre, ans;
int Fnum;

struct Edge{
	int adj, wt;
	Edge* next;
}tb[N<<1];

Edge* mat[N];
int dist[N], flag[N], que[N], vis[N], num[N];

void inline add( int u, int v, int d ){
	++cnt;
	tb[cnt].adj= v; tb[cnt].wt= d;
	tb[cnt].next= mat[u]; mat[u]= tb+ cnt;
	
	++cnt;
	tb[cnt].adj= u; tb[cnt].wt= d;
	tb[cnt].next= mat[v]; mat[v]= tb+ cnt;
}

int selectRoot( int rt ){
	flag[rt]= Fnum;
	
	int tmp= 0, sum= 0;
	for( Edge* p= mat[rt]; p; p= p->next ){
		int v= p->adj;
		
		if( vis[v]== 0 && flag[v]!= Fnum ){
			int s= selectRoot( v );
			
			if( s> tmp ) tmp= s;
			sum+= s;
		}
	}
	
	if( nchild- 1- sum> tmp ) tmp= nchild- 1- sum;
	
	if( tmp< size ){  size= tmp; root= rt; }
	
	return sum+ 1;
}

int inline getCount( int first, int last ){
	sort( dist+ first, dist+ last+ 1 );
	
	int head= first, tail= last, ret= 0;
	while( first< last ){
		if( dist[first]+ dist[last]<= k ) ret+= last- first++; 
		else last--;
	}
	return ret;
}

int dfs( int rt, int len ){
	flag[rt]= Fnum; dist[++last]= len;
	
	int sum= 0;
	for( Edge* p= mat[rt]; p; p= p->next )
	if( !vis[p->adj] && flag[p->adj]!= Fnum ){
		int v= p->adj, wt= p->wt;
		
		sum+= dfs( v, len+ wt );
	}
	
	num[rt]= sum+ 1;
	return sum+ 1;
}

void solve( int rt ){
	pre= 1;
	for( Edge* p= mat[rt]; p; p= p->next )
	if( !vis[p->adj] && flag[p->adj]!= Fnum ){
		int v= p->adj, wt= p->wt;
		
		dfs( v, wt );
		ans-= getCount( pre, last );

		pre= last+ 1;
	}
}

int main(){
	while( scanf("%d%d",&n,&k)!= EOF ){
		if( n== 0 && k== 0 ) return 0;
		
		for( int i= 0; i<= n; ++i ) mat[i]= 0, flag[i]= 0, vis[i]= 0;
		cnt= -1; tot= -1;
		
		int u, v, d;
		for( int i= 1; i< n; ++i ){
			scanf("%d%d%d", &u,&v,&d );
			
			add( u, v, d );
		}
		
		int head= 0, tail= 0; que[0]= 1; 
		nchild= n; ans= 0; Fnum= 0; num[1]= n;
		
		while( head<= tail ){
			int now= que[head++]; nchild= num[now]; Fnum++;
			
			size= 0x7fffffff; selectRoot( now ); vis[root]= 1;		
			
			for( Edge*p= mat[root]; p; p= p->next )
			if( !vis[p->adj] ) que[++tail]= p->adj;
			
			first= pre= 1; last= 0; Fnum++;
	
			solve( root ); dist[++last]= 0;
			ans+= getCount( first, last );
		}
		
		printf("%d\n", ans );
	}
	
	return 0;
}