POJ 1741 Tree 树 点分治

题意：给定一颗n(n<=10000)个点的带权树，问这颗树中两点最短路小于等于K的点对有多少。

漆子超 的《分治算法在树的路径问题中的应用》中的例题之一。

因为是无根树，每次找树的重心，以重心转换为有根树，可以防止算法从$O(NlogN)$退化为$O(n^2)$，，然后求经过该点的最短路小于等于K的点对数。但是会算多，因此要减去算多的那些部分。。
代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int MAXN=10000+100;
struct Edge {
	int to,next,w;
	Edge(){}
	Edge(int _to,int _next,int _w):to(_to),next(_next),w(_w){}
}e[MAXN<<1];
int head[MAXN],tot;
void init(){
	memset(head,-1,sizeof(head));
	tot=0;
}
void AddEdge(int u,int v,int w){
	e[tot]=Edge(v,head[u],w);
	head[u]=tot++;
	e[tot]=Edge(u,head[v],w);
	head[v]=tot++;
}
int n,K;
int has[MAXN],root,siz[MAXN],ts[MAXN];
void getroot(int u,int fa){
	siz[u]=1; ts[u]=0;
	for(int i=head[u];~i;i=e[i].next){
		int v=e[i].to;
		if(has[v]||v==fa)continue;
		getroot(v,u);
		siz[u]+=siz[v];
		ts[u]=max(ts[u],siz[v]);
	}
	ts[u]=max(ts[u],ts[0]-siz[u]);
	if(ts[u]<ts[root])root=u;
}
int dis[MAXN],res[MAXN];
void getdis(int u,int fa){
	res[++res[0]]=dis[u];
	siz[u]=1;
	for(int i=head[u];~i;i=e[i].next){
		int v=e[i].to;
		if(has[v]||v==fa)continue;
		dis[v]=dis[u]+e[i].w;
		getdis(v,u);
		siz[u]+=siz[v];
	}
}
int calc(int u,int init){
	//printf("u:%d init:%d\n",u,init);
	dis[u]=init;res[0]=0;getdis(u,u);
	sort(res+1,res+1+res[0]);
	//for(int i=1;i<=res[0];i++)printf("%d ",res[i]);
	//puts("");
	int l=1,r=res[0];
	int ans=0;
	while(l<r){
		if(res[l]+res[r]<=K)ans+=r-l++;
		else --r;
	}
	//printf("%d\n",ans);
	return ans;
}
int Ans;
void dfs(int u){
	Ans+=calc(u,0);
	has[u]=1;
	for(int i=head[u];~i;i=e[i].next){
		int v=e[i].to;
		if(has[v])continue;
		//printf("%d-->%d %d\n",u,v,e[i].to);
		Ans-=calc(v,e[i].w);
		root=0;ts[0]=siz[v];
		getroot(v,v);
		//printf("root:%d\n",root);
		dfs(root);
	}
}
int main(){
	while(~scanf("%d%d",&n,&K)){
		if(n+K==0)break;
		init();
		memset(has,0,sizeof(has));
		for(int i=0,x,y,w;i<n-1;i++){
			scanf("%d%d%d",&x,&y,&w);
			AddEdge(x,y,w);
		}
		root=0;ts[0]=n;
		getroot(1,1);
		Ans=0;
		//printf("root:%d\n",root);
		dfs(root);
		printf("%d\n",Ans);
	}
	return 0;
}