题目链接：http://poj.org/problem?id=1741
题目大意：

给定一棵有n个点的树
询问树上距离<=k的点对有多少。

点分治，是处理树上路径的一个极好的工具。
一般如果需要大规模处理树上路径，点分治是一个不错的选择。

这里我就来讲一讲我自己对于点分治的一点理解和感悟（帮助新手入坑……）
现在就开始吧！

1.点分治的基本思想
点分治，顾名思义就是基于树上的节点进行分治。
如果我们在深入一点呢？对于点的拆开其实就是对于树的拆开。
所以我认为点分治的本质其实是将一棵树拆分成许多棵子树处理，并不断进行。
这应该也是点分治的精髓。

2.分治点的选择
既然我们要将一个点进行分治，那么选点肯定最首要的。
思考下面一个问题：
如果树退化为一个链，
我们选取链首作为分治点，理论时间复杂度？
而如果选择链的中心，它的理论时间复杂度又是多少？
答案其实还是挺简单的。
选择链首：O( n )
选择链心：O( logn )
通过这个例子,我们不难发现：
如果选点后左右子树越大，递归层数越多，时间越慢，反之则越快。
所以我们的选点标准就出来了，而我们把有这个性质的点叫做：树的重心！

这是一道点分治的模板题。

点分治一般有以下几种用法:

求路径长度等于或小于等于k的点对(路径条数);
路径长度为k的倍数;
路径长度为k且路径的边数最少;
路径长度对某个数x取余后等于k;
路径上经过的点的个数不能超过k，且路径长度最大。
 对于树上的路径来说，可以分为两种：

经过根root。
包含于root的某一棵子树中，即不经过root。

思路：对于这题求出所有的子节点到root的距离，排序后用相向搜索。得到对数。需要容斥一下，因为这些点可能来自同一棵子树。但是要经过root就必须来自不同的子树。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+20, inf=1e9+1000;

struct edg{
    int to, w, next;
}e[N*4];

int tot, root, ans, allnode, n, k;
int head[N], vis[N], siz[N], d[N];
int deep[N];//路径长度//deep[0]子节点个数
int f[N];//求重心的最多子节点个数

void add(int u, int v, int w){
    e[tot].to=v, e[tot].next=head[u];
    e[tot].w=w, head[u]=tot++;
}

void getroot(int u, int fa){//求重心

    siz[u]=1;
    f[u]=0;
    for(int i=head[u]; i!=-1; i=e[i].next){
        int to=e[i].to;
        if(to==fa||vis[to]){
            continue;
        }
        getroot(to, u);
        siz[u]+=siz[to];
        f[u]=max(f[u], siz[to]);
    }
    f[u]=max(allnode-siz[u], f[u]);
    if(f[u]<f[root]){
        root=u;
    }
}

void getdeep(int u, int fa){//获取子树所有节点与根的距离
    deep[++deep[0]]=d[u];
    for(int i=head[u]; i!=-1; i=e[i].next){
        int to=e[i].to;
        if(to==fa||vis[to]){
            continue;
        }
        d[to]=d[u]+e[i].w;
        getdeep(to, u);
    }
}

int cal(int u, int w){//计算当前以重心x的子树下，所有情况的答案

    d[u]=w, deep[0]=0;
    getdeep(u, 0);
    sort(deep+1, deep+deep[0]+1);
    int ans=0;
    for(int l=1, r=deep[0]; l<r; ){
        if(deep[l]+deep[r]<=k){
            ans+=r-l;
            l++;
        }
        else{
            r--;
        }
    }
    return ans;
}

void work(int u){//以x为重心进行计算
    vis[u]=1;
    ans+=cal(u, 0);
    for(int i=head[u]; i!=-1; i=e[i].next){
        int to=e[i].to;
        if(vis[to]){
            continue;
        }
        ans-=cal(to, e[i].w);//删除在同一棵子树的点对贡献
        
        allnode=siz[to];//继续分治
        root=0;
        getroot(to, u);
        work(root);
    }
}

int main(){

    int u, v, w;
    while(scanf("%d%d", &n, &k), (n+k)){
        memset(head, -1, sizeof(head));
        memset(vis, 0, sizeof(vis));
        tot=1;
        for(int i=1; i<=n-1; i++){
            scanf("%d%d%d", &u, &v, &w);
            add(u, v ,w), add(v, u, w);
        }
        root=ans=0;
        allnode=n, f[0]=inf;
        getroot(1, 0);
        work(root);
        printf("%d\n", ans);

    }

    return 0;
}