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

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

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

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