点分治被用来解决的问题：
给你一棵TREE,以及这棵树上边的距离。问有多少对点它们两者间的距离小于等于K。
算法实现：
先想想暴力做法吧，n3的，都会吧，暴力枚举两点，再暴力求出他们间的距离，判断是否小于k，统计答案。
n2 log呢？很简单吧，就是把暴力求距离那一步改成LCA嘛。
那么我们的点分治就更加牛逼了，它可以在n log2 的时间内求解。
那么它是如何做到这么优秀的呢？我们来看看他的算法流程吧。
点分治主要是通过统计路径经过u的两个点（包括以u为路径的端点，其中这两个点是要在以u为根的子树中的），长度小于等于k的有多少，递归来求出最终的答案。
我们先讲讲如何统计路径经过u的两个点，长度小于等于k的有多少吧。
这应该很容易想的。
先一遍dfs求出从点u到以u为根的子树中各个点的距离。
那么我们把以u为根的子树中各个点到u的距离排序。
排序之后，对于每一个点都二分匹配一个最大的和它相加小于等于k的另一个点，再统计答案。
但是我们发现，这么做会锅。
会遇到下图情况：
（手画的，有点难看，讲究一下下吧。。。）
假设k=8，当我们在做1号点时，我们会发现d[4]=4,d[5]=4，然后他俩就会牵手成功，然而这是错的，因为1-2的边被计算了两次。
这个时候呢，我们有两种解决方法：
1、注意到当这两个点不在u的同一个儿子时，便不会产生重复的路径，所以我们把各个点进行染色，把在u的同一个儿子中的点染成同一种颜色，然后不去匹配颜色相同的点就OK了。
2、利用融斥的思想，做以v（v为u的儿子）为根的子树，并把u中的各个节点到u的距离通通加上dist[u,v]，在这种情况下依然能够牵手成功的两个点，就说明它是我们在上一次统计中出锅的情况，只要把这些情况减掉就可以了。
代码中我是用了第二种方法（毕竟比较简单嘛，代码也短）。
另一个问题——为什么一定要是在以u为根的子树中的点呢？还是直接看图吧：
也就是说此时的v2不在以u为根的子树中，那么就说明v1和v2被u到v2这段路径，辈分最高的那个点统计过了（就是图中从u连到骚粉矩形的边的另一个端点），不需要再次重复统计。
关于选择点的顺序以及时间复杂度的计算：
看了上述的算法流程，相比大家都会算时间复杂度吧。
T(n)=∑v∈u's sons [T(siz[v])+Θ(siz[v] log siz[v])]
很显然，时间复杂度和我们递归的层数是有关系的，那么我们选择点的顺序就很清楚了：
为了让递归的层数尽可能的小，所以我们要每次选子树的重心开始做。
那么理论上时间复杂度最大的时候，就恰恰是一条链的时候，因为它会递归log n层，那么理论时间复杂度便是O(n log2)的了。
代码实现：
#include <bits/stdc++.h> using namespace std; const int maxn=40005,inf=100000000; int d[maxn],siz[maxn],f[maxn],head[maxn],nxt[maxn<<1],vet[maxn<<1],dist[maxn<<1]; bool vis[maxn]; int n,k,x,y,z,root,Siz,tot,cnt,ans; void add(int x,int y,int z){ nxt[++tot]=head[x]; vet[tot]=y; head[x]=tot; dist[tot]=z; } void getroot(int u,int father){ //找重心 siz[u]=1; f[u]=0; for (int i=head[u];i;i=nxt[i]){ int v=vet[i]; if (vis[v]||v==father) continue; getroot(v,u); f[u]=max(f[u],siz[v]); siz[u]+=siz[v]; } f[u]=max(f[u],Siz-siz[u]); if (f[u]<f[root]) root=u; } void getdis(int u,int father,int dis){ //求距离 d[++cnt]=dis; for (int i=head[u];i;i=nxt[i]){ int v=vet[i]; if (vis[v]||v==father) continue; getdis(v,u,dis+dist[i]); } } int find_right(int k,int left){ //求最大的能与now牵手成功的右端点 int l=left,r=cnt,ans=left; while (l<=r){ int mid=l+r>>1; if (d[mid]<=k) ans=mid,l=mid+1; else r=mid-1; } return ans; } int getans(int u,int dis){ //求答案 cnt=0; int res=0,now=1; getdis(u,0,dis); sort(d+1,d+1+cnt); while (now<cnt&&d[now]+d[cnt]<k) res+=cnt-now,now++; //说明全部都可以牵手成功 while (now<cnt&&d[now]+d[now+1]<=k){ int right=find_right(k-d[now],now+1); res+=right-now; now++; } return res; } void dfs(int u){ vis[u]=true; ans+=getans(u,0); for (int i=head[u];i;i=nxt[i]){ int v=vet[i]; if (vis[v]) continue; ans-=getans(v,dist[i]); //去掉上述在同一儿子中的情况 Siz=siz[v]; root=v; getroot(v,u); //确定下一个点 dfs(root); } } int main(){ scanf("%d",&n); for (int i=1;i<n;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } scanf("%d",&k); root=1; Siz=n; getroot(1,0); dfs(root); printf("%d ",ans); }