題目敘述：
    給出一個有n個節(jié)點的樹, 一個整數(shù)k. 定義dist(u, v)為節(jié)點u, v間的距離. 求這棵樹中有多少節(jié)點對(u, v)滿足dist(u, v)<=k. (n<=10000)

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

對于這樣一個數(shù)據(jù)范圍，顯然O(n^2)的直接算是會超時的。

大體的思路是：
    1.一個樹中的路徑可以分為兩種：一種是過根的，一種是不過根的--那一定是過子樹的根。所以可以對于每一棵樹都統(tǒng)計過根的路徑中長度小于等于K的有多少，然后加起來就是答案。
    2.對于每一棵子樹，找出子樹中所有點到根的距離，排序并統(tǒng)計路徑長度小于等于K的條數(shù)。對于一個有序的序列a，如果有i<j且a[i]+a[j]<=K，那么a[i] + a[i+1~j]<=K，所以可以找出對于一個i滿足條件最大的j或?qū)τ谝粋€j滿足條件的最小的i，進行統(tǒng)計。
    3.這樣統(tǒng)計出來的路徑有些是從某個子樹到根后，又返回原來的子樹，顯然這樣的路徑是不滿足條件的。而這些路徑一定經(jīng)過當前根的兒子，所以為了排除這些多余的路徑，只需要減去所有的在兒子的子樹中過兒子的路徑條數(shù)，當然，這些路徑長度并不是小于等于K了，而是小于等于K-2*根到兒子的邊的長度。
    4.這樣雖然能夠得到解，但是時間復雜度在一條鏈的情況下最壞為O(n^2logn)(n個點，每個點快排)。對于一個無根樹的統(tǒng)計，我們發(fā)現(xiàn)根的選擇是無關(guān)結(jié)果的。所以每次對于一棵子樹我們處理的時候，我們選擇的根不一定剛好就是上一個根的兒子，而可以是當前子樹當中的任意一個點，即每次把子樹看做一個無根圖來處理。而對于一個大小為n的無根樹，一定存在至少一個點是的以這個點作為根的樹的每個兒子的大小都不超過n/2。所以我們每次處理的時候就在當前的無根樹找到一個這樣的點，把它作為當前無根樹的根。這個點叫做樹的重心。這樣的話每次處理節(jié)點的數(shù)目至少會減少一半，所以處理的深度不會超過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