題目
給出一棵帶邊權的樹，問有多少對點的距離<=Len
分析
這是一道點分治的經典題目，可以給點分治的初學者練手。
點分治，顧名思義就是把每個點分開了處理答案。
假設，目前做到了以x為根的子樹。
先求出子樹中每個點到根的距離\(dis\)，對于兩個點\(i\)和\(j\)，如果\(dis_{i}+dis_{j}<=k\)，那么\(（i，j）\)就是一個合法的點對。
而點對的路徑就會有兩種：經過x點的和不經過x點的。
顯然，不經過x點的一定會再x的兒子的子樹中被計算過。所以，我們要減去不經過x點的。
那怎么把不經過x點的減去呢？
用以x為根的子樹的\(dis\)值（why？如果用以x的兒子為根的子樹的\(dis\)，就會有些可以到達x的兒子的卻不能到達x的點對，被多減掉），來計算以x的兒子為根的子樹中的點對數量，用減去它們就可以了。
記住要找重心
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const long long maxlongint=2147483647;
using namespace std;
long long dis[12000],next[22000],last[20020],to[20200],n,m,tot,v[20200],d[5000],sum=0,size[20020],mx[20020],f,root,ans;
bool bz[20020];
long long bj(long long x,long long y,long long z)
{next[++tot]=last[x];last[x]=tot;to[tot]=y;v[tot]=z;
}
void findroot(long long x,long long fa)
{mx[x]=0;size[x]=1;for(long long i=last[x];i;i=next[i]){if(to[i]!=fa && (!bz[to[i]])) {findroot(to[i],x);size[x]+=size[to[i]];mx[x]=max(mx[x],size[to[i]]);}}mx[x]=max(mx[x],f-size[x]);if (mx[x]<mx[root]) root=x;return;
}
void q(long long l,long long r)
{long long i=l,j=r,mid=d[(l+r)/2],e;while(i<j){while(dis[d[i]]<dis[mid]) i++;while(dis[d[j]]>dis[mid]) j--;if(i<=j){e=d[i];d[i]=d[j];d[j]=e;i++;j--;}}if(i<r) q(i,r);if(l<j) q(l,j);
}
long long dg1(long long x,long long fa)
{d[++tot]=x;for(long long i=last[x];i;i=next[i]){long long j=to[i];if(fa!=j && (!bz[j])){dis[j]=dis[x]+v[i];dg1(j,x);}}
}
long long getsum()
{q(1,tot);int i=1,j=tot;long long y=0;while(i<j){if(dis[d[i]]+dis[d[j]]-2>m)j--;else{y+=j-i;i++; } }return y;
}
long long dg(long long x,long long fa)
{bz[x]=true;dis[x]=1;tot=0;dg1(x,fa);ans+=getsum();for(int i=last[x];i;i=next[i]){int j=to[i];if(!bz[j]) {dis[j]=v[i]+1;tot=0;dg1(j,x);ans-=getsum();f=size[j];root=0;findroot(j,x);dg(root,x);}}
}
int main()
{scanf("%lld%lld",&n,&m);for(long long i=1;i<=n-1;i++){long long x,y,z;scanf("%lld%lld%lld",&x,&y,&z);bj(x,y,z);bj(y,x,z); }mx[0]=maxlongint;f=n;findroot(1,0);dg(root,0);printf("%lld\n",ans);
}
)
)
