POJ 1741
做到这题就像怎么做，想了半个小时网上搜下思路，发现是点分治板子题了属于是；
点分治，是在一棵树上的处理方法，处理什么问题我也不知道，主要步骤如下：
1.找重心；
2.统计合法方案；
3.递归找接下来的方案；
方案分成三类：
1.穿过重心的；
2.圈地自萌的；
3.停在重心的，需要去特判一下；
不同的点分治题目其区别在于统计的时候方法不同；

AcWing 252

就是板子题，直接上代码看下了；
首先这份代码看起来十分舒服，因为好几块内容分装了，函数拆的很好；

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 10010, M = N * 2;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
bool st[N];
int p[N],q[N];//P是长久队列Q是暂时队列
void add(int a,int b,int c){
	e[idx] = b, w[idx] = c, ne[idx] = h[a] ++ ;
}//加边函数
int get_size(int u,int fa){
	if(st[u]) return 0;
	int res = 1;
	for(int i = h[u]; ~i; i = ne[i])
		if(e[i] != fa)
			res += get_size(e[i],u);
	return res;
}//这个函数的功能就跟他的名字所说的是一样的
int get_wc(int u,int fa,int tot, int& wc){
	if(st[u]) return 0;
	int sum = 1, ms = 0;//sum一定要等于1不然会死
	for(int i = h[u]; ~i; i = ne[i]){
		int j = e[i]; 
		if(j == fa) continue;
		int t = get_wc(j,u,tot,wc);
		ms = max(ms,t);		sum += t;
	}//和求size的方式有点像哦
	ms = max(ms,tot - sum);
	if(ms <= tot/2 ) wc = u;
	return sum;
}//找重心函数，是直接传参传回去的，当然这个找的不是严格的重心
//只是符合性质的一个节点
void get_dist(int u ,int fa,int dist, int& qt){
	if (st[u]) return;
	q[qt++] = dist;
	for(int i = h[u]; ~i; i = ne[i]){
		if(e[i] != fa) get_dist(e[i], u, dist + w[i], qt);
	}
}//深搜因为好找
int get(int a[],int k){
	sort(a,a+k);
	int res = 0;
	for(int i = k - 1, j = -1; i >= 0; i--){
		while(j+1<i && a[j+1] + a[i] <= m) j ++ ;
		j = min(j, i-1) ;
		res += j+1;
	}
	return res;
}//尺取法
int calc(int u){
	if(st[u]) return 0;
	int res = 0;
	get_wc(u,-1,get_size(u,-1),u);
	st[u] = true;
	int pt = 0;
	for(int i=h[u];~i;i = ne[i]){
		int j = e[i], qt = 0;
		get_dist(j,-1,w[i],qt);
		res -= get(q,qt);//容斥原理
		for(int k = 0;k < qt;k++){
			if(q[k] <= m) res++;
			p[pt++] = q[k];
		}
	}
	res += get(p,pt);
	for(int i = h[u];~i;i = ne[i]) res += calc(e[i]);
	return res;
}//别的没啥好说了。
int main()
{
	while(scanf("%d%d",&n,&m), n || m){
		memset(st,0,sizeof st);
		memset(h,-1,sizeof h);
		idx = 0;
		for(int i = 0; i < n-1 ; i++){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			add(a,b,c);		add(b,a,c);
		}
		printf("%d\n",calc(0));
	}
	
	return 0;
}

再来个例题；

AcWing 264

和上一题大体相同就是归并部分不一样；

#inclulde<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 200010, M = N * 2,S = 1000010, INF = 0x3f3f3f3f;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
int f[S],ass = INF;
PII p[N],q[N];
bool st[N];
void add(int a,int b,int c){
	e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++ ;
}
int get_size(int u,int fa){
	if(st[u]) return 0;
	int res = 1;
	for(int i=h[u]; ~i;i = ne[i]){
		int j = e[i];
		if(j == fa) continue;
		res += get_size(j,u);
	}
	return res;
}int get_wc(int u,int fa,int tot,int& wc){
	if(st[u]) return 0;
	int sum = 1,ms = 0;
	for(int i = h[u]; ~i; i = ne[i]){
		int j = e[i];
		if(j == fa) continue;
		int t = get_wc(j,u,tot,wc);
		ms = max(ms,t);
		sum += t;
	}
	ms = max(ms,tot - sum);
	if( ms <= tot/2 ) wc = u;
	return sum;
}void get_dist(int u,int fa,int dist,int cnt,int& qt){
	if(st[u] || dist > m) return;
	q[qt++] = {dist, cnt};
	for(int i = h[u]; ~i;i = ne[i]) {
		int j = e[i];
		if(j == fa) continue; 
		get_dist(j,u,dist+w[i],cnt+1,qt);
	}
}void calc(int u){
	if(st[u]) return;
	get_wc(u,-1,get_size(u,-1),u);
	st[u] = true;
	int pt = 0;
	for(int i = h[u]; ~i; i = ne[i]){
		int j = e[i], qt = 0;
		get_dist(j,u,w[i],1,qt);
		for(int k = 0; k <qt; k ++){
			auto& t = q[k];
			if( t.first == m) ass = min(ass,t.second);
			ass = min(ass,f[m-t.first] + t.second);
			p[pt++] = t;
		}
		for(int k = 0; k < qt; k ++){
			auto& t = q[k];
			f[t.first] = min(f[t.first], t.second);
		}
	}
	for(int i =0 ;i <pt; i++)
		f[p[i].first] = INF;
	for(int i = h[u];~i; i = ne[i]) calc(e[i]);
}
int main()
{
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof h);
	for(int i = 0;i < n-1; i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c),  add(b,a,c);
	}
	memset(f,0x3f,sizeof f);
	calc(0);
	
	if(ass == INF) ass= -1;
	printf("%d\n",ass);
	
	return 0;
}