题目叙述：
    给出一个有n个节点的树, 一个整数k. 定义dist(u, v)为节点u, v间的距离. 求这棵树中有多少节点对(u, v)满足dist(u, v)<=k. (n<=10000)

-------------------------------------------

对于这样一个数据范围，显然O(n^2)的直接算是会超时的。

大体的思路是：
    1.一个树中的路径可以分为两种：一种是过根的，一种是不过根的--那一定是过子树的根。所以可以对于每一棵树都统计过根的路径中长度小于等于K的有多少，然后加起来就是答案。
    2.对于每一棵子树，找出子树中所有点到根的距离，排序并统计路径长度小于等于K的条数。对于一个有序的序列a，如果有i<j且a[i]+a[j]<=K，那么a[i] + a[i+1~j]<=K，所以可以找出对于一个i满足条件最大的j或对于一个j满足条件的最小的i，进行统计。
    3.这样统计出来的路径有些是从某个子树到根后，又返回原来的子树，显然这样的路径是不满足条件的。而这些路径一定经过当前根的儿子，所以为了排除这些多余的路径，只需要减去所有的在儿子的子树中过儿子的路径条数，当然，这些路径长度并不是小于等于K了，而是小于等于K-2*根到儿子的边的长度。
    4.这样虽然能够得到解，但是时间复杂度在一条链的情况下最坏为O(n^2logn)(n个点，每个点快排)。对于一个无根树的统计，我们发现根的选择是无关结果的。所以每次对于一棵子树我们处理的时候，我们选择的根不一定刚好就是上一个根的儿子，而可以是当前子树当中的任意一个点，即每次把子树看做一个无根图来处理。而对于一个大小为n的无根树，一定存在至少一个点是的以这个点作为根的树的每个儿子的大小都不超过n/2。所以我们每次处理的时候就在当前的无根树找到一个这样的点，把它作为当前无根树的根。这个点叫做树的重心。这样的话每次处理节点的数目至少会减少一半，所以处理的深度不会超过logn。这样就把总的时间复杂度降到了O(nlognlogn)。

  1#include <iostream>
  2#include <cstdio>
  3#include <cstdlib>
  4#include <cstring>
  5#include <algorithm>
  6
  7#define MAXN 10000
  8#define MAXM MAXN*2
  9
 10using namespace std;
 11
 12int n,K;
 13int Count = 0;
 14int begin[MAXN+1],end[MAXM+1],next[MAXM+1],cost[MAXM+1];
 15void AddEdge(int a,int b,int c){
 16    Count++;
 17    next[Count] = begin[a];
 18    begin[a] = Count;
 19    end[Count] = b;
 20    cost[Count] = c;
 21}
 22void Solve();
 23void Init(){
 24    while (true){
 25        scanf("%d%d",&n,&K);
 26        if (n == 0 && K == 0)
 27            break;
 28        else
 29            Solve();
 30    }
 31}
 32
 33
 34bool hash[MAXN+1];
 35int size[MAXN+1];
 36int GetSize(int x,int fa){
 37    size[x] = 1;
 38    for (int now = begin[x]; now; now = next[now])
 39        if (!hash[end[now]] && end[now]!=fa)
 40            size[x] += GetSize(end[now],x);
 41    return size[x];
 42}
 43
 44int GetBestRoot(int x){
 45    GetSize(x,0);
 46    while (true){
 47        int MaxSize = 0,id = 0;
 48        for (int now = begin[x]; now; now = next[now])
 49            if (!hash[end[now]] && MaxSize < size[end[now]])
 50                MaxSize = size[id = end[now]];
 51        if (MaxSize <= (size[x] >> 1))
 52            break;
 53        size[x] -= size[id], size[id] += size[x], x = id;
 54    }
 55    return x;
 56}
 57int dist[MAXN+1];
 58int cnt;
 59void GetDist(int x,int fa,int d){
 60    if (d>K) return;
 61    dist[++cnt] = d;
 62    for (int now = begin[x]; now; now = next[now])
 63        if (!hash[end[now]] && end[now] != fa)
 64            GetDist(end[now],x,d + cost[now]);
 65}
 66int cmp(const void *a,const void *b){
 67    return (*(int *)a) - (*(int *)b);
 68}
 69int dfs(int x){
 70    x = GetBestRoot(x);
 71    hash[x] = true;
 72    int ret = 0;
 73    for (int now = begin[x]; now; now = next[now])
 74        if (!hash[end[now]])
 75            ret += dfs(end[now]);
 76    cnt = 0;
 77    GetDist(x,0,0);
 78    qsort(dist+1,cnt,sizeof(dist[0]),cmp);
 79    
 80    
 81    int l = 1, r = cnt;
 82    while (l<r){
 83        if (dist[l] + dist[r]<=K) ret += r-l, l++;
 84        else r--;
 85    }
 86    for (int now = begin[x]; now; now = next[now])
 87        if (!hash[end[now]]){
 88            int limit = K - cost[now] * 2;
 89            cnt = 0;
 90            GetDist(end[now],0, 0);
 91            qsort(dist+1,cnt,sizeof(dist[0]),cmp);
 92            int l = 1, r = cnt;
 93            while (l<r){
 94                if (dist[l] + dist[r]<=limit) ret -= r-l, l++;
 95                else r--;
 96            }
 97        }
 98    hash[x] = false;
 99    return ret;
100}
101
102void Solve(){
103    Count = 0;
104    memset(begin,0,sizeof(begin));
105    int t1,t2,t3;
106    for (int i = 1; i<n; i++){
107        scanf("%d%d%d",&t1,&t2,&t3);
108        AddEdge(t1,t2,t3);
109        AddEdge(t2,t1,t3);
110    }
111    printf("%d\n",dfs(1));
112}
113
114int main(){
115    Init();
116    return 0;
117}
118