题意：给一颗n个节点的树，每条边上有一个距离v（v<=1000）。定义d(u,v)为u到v的最小距离。给定k值，求有多少点对（u，v）使u到v的距离小于等于k。
/* 照着点分治模板敲了敲，有很多细节地方应该注意，不然很容易出错。 点分治的大概就是解决树上路径中统计某些东西的一个算法，顾名思义，肯定与递归有些关系。 简单步骤就是：①求重心 ②统计这棵树的答案 ③递归到它的子树求解 推荐一篇博客：http://www.cnblogs.com/chty/p/5912360.html */ #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #define N 10010 #define inf 100000000 using namespace std; int head[N],deep[N],d[N],vis[N],son[N],f[N],root,sum,ans,n,m; struct node{ int to,t,pre; };node e[N*2]; void add(int i,int x,int y,int z){ e[i].to=y; e[i].t=z; e[i].pre=head[x]; head[x]=i; } void getroot(int x,int fa){ son[x]=1;f[x]=0; for(int i=head[x];i;i=e[i].pre){ if(vis[e[i].to]||e[i].to==fa) continue; getroot(e[i].to,x); son[x]+=son[e[i].to]; f[x]=max(f[x],son[e[i].to]); } f[x]=max(f[x],sum-son[x]); if(f[x]<f[root])root=x; } void getdeep(int x,int fa){//求出x的子树上的节点的深度（x深度不一定为0） deep[++deep[0]]=d[x]; for(int i=head[x];i;i=e[i].pre){ if(vis[e[i].to]||e[i].to==fa) continue; d[e[i].to]=d[x]+e[i].t; getdeep(e[i].to,x); } } int cal(int x,int v){//求出x的子树上的答案，但是对于本题目多计算了两个点在同一条子树上的情况 d[x]=v;deep[0]=0; getdeep(x,0); sort(deep+1,deep+deep[0]+1); int l=1,r=deep[0],tot=0; while(l<r){ if(deep[r]+deep[l]<=m) tot+=r-l,l++; else r--; } return tot; } void solve(int x){//求出x的子树上的答案 ans+=cal(x,0); vis[x]=1; for(int i=head[x];i;i=e[i].pre){ if(vis[e[i].to]) continue; ans-=cal(e[i].to,e[i].t); sum=son[e[i].to]; root=0; getroot(e[i].to,0); solve(root); } } int main(){ while(scanf("%d%d",&n,&m)){ if(!n&&!m) break; ans=root=0; memset(head,0,sizeof(head)); memset(vis,0,sizeof(vis)); for(int i=1;i<n;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(i*2-1,x,y,z);add(i*2,y,x,z); } sum=n;f[0]=inf; getroot(1,0); solve(root); printf("%d ",ans); } return 0; }