POJ1741 Tree.

5 41 2 31 3 11 4 23 5 10 0Sample Output
8（说起来这应该是人生第一道点分治呗。。。quq蒟蒻的悲哀：）题意：给定一棵N(1<= N <=10000)个结点的带权树，定义dist(u,v)为u,v两点间的最短路径长度，路径的长度定义为路径上所有边的权和。再给定一个 K  ，如果对于不同的两个结点a,b，如果满足dist(a,b) <=K，则称(a,b)为合法点对。求合法点对个数。题解：也是刚刚搞完点分治呗。。。%XZK难得一次编译过AC。。。所谓点分治嘞，就是在一个无根树里选取一个点作为根【重心】然后再递归处理每个子树对于这道题嘛，我们考虑一条路径只有两种情况——经过根or不过根【也可以说是：两点在同一棵子树内or不在同一颗子树内】那么我们就可以得出一个大致框架：记录每个子树内的到子树【我们递归处理的树】根节点距离值，然后从小到大排一个序，就可以计算出符合dist(a,b)<=k的点对个数，用这种方法对每一个子树计一个res表示合法点对数这个时候要注意：对于一棵这样的树 ，由于递归的缘故，会有重复计算的情况所以我们的结果ans=ans-sigama res的【即：所有满足合法的点对-在同一个子树的点对数】以下是AC代码：=v=
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define inf 0x7fffffff#define maxn 10010using namespace std;struct node{	int v,w,nxt;}e[maxn*4];int n,k;int vis[maxn];int dis[maxn],dep[maxn];int size[maxn],f[maxn];int head[maxn],cnt;int rt,cd;void add(int u,int v,int w){	e[++cnt].v=v;	e[cnt].w=w;	e[cnt].nxt=head[u];	head[u]=cnt;}void getroot(int x,int fa,int sum){	size[x]=1;f[x]=0;	for(int i=head[x];i!=-1;i=e[i].nxt){		int v=e[i].v;		if(!vis[v] && v!=fa){			getroot(v,x,sum);			size[x]+=size[v];			f[x]=max(f[x],size[v]);		}	}	f[x]=max(f[x],sum-size[x]);	if(f[x]<f[rt])rt=x;	}void getdeep(int x,int fa){	dis[++cd]=dep[x];	for(int i=head[x];i!=-1;i=e[i].nxt){		int v=e[i].v;		if(!vis[v] && v!=fa){			dep[v]=dep[x]+e[i].w;			getdeep(v,x);		}	}}int work(int x,int val){	dep[x]=val;cd=0;	getdeep(x,0);	sort(dis+1,dis+cd+1);	int res=0,l=1,r=cd;	while(l<r){		if(dis[l]+dis[r]<=k)res+=r-l,l++;		else r--;	}	return res;}int ans;void solve(int x){	ans+=work(x,0);	vis[x]=1;	for(int i=head[x];i!=-1;i=e[i].nxt){		int v=e[i].v;		if(!vis[v]){			ans-=work(v,e[i].w);			rt=0;			getroot(v,rt,size[v]);			solve(rt);		}	}}int main(){	while(~scanf("%d%d",&n,&k)){		if(n==0 && k==0)break;		ans=0,rt=0;		memset(head,-1,sizeof head);memset(vis,0,sizeof vis);		cnt=0;		memset(size,0,sizeof size);		for(int i=1;i<n;i++){			int u,v,w;scanf("%d%d%d",&u,&v,&w);			add(u,v,w);add(v,u,w);		}		f[0]=inf;		getroot(1,0,n);		solve(rt);		printf("%d/n",ans);	}	return 0;}8