Description
Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k. Write a program that will count how many pairs which are valid for a given tree.
Input
The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l. The last test case is followed by two zeros.
Output
For each test case output the answer on a single line.
题目大意：给一个带边权的树，问有多少对点满足dist(i,j)<=k
思路：可以参考2009年的国家集训队论文《分治算法在树的路径问题中的应用》——漆子超。
代码（188MS）：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int MAXN = 10010; 8 const int MAXE = 20010; 9 const int INF = 0x7fff7fff; 10 11 int head[MAXN], size[MAXN], maxSize[MAXN]; 12 int list[MAXN], cnt; 13 bool del[MAXN]; 14 int to[MAXE], next[MAXE], cost[MAXE]; 15 int n, k, ecnt; 16 17 void init() { 18 memset(head, -1, sizeof(head)); 19 memset(del, 0, sizeof(del)); 20 ecnt = 0; 21 } 22 23 void add_edge(int u, int v, int c) { 24 to[ecnt] = v; cost[ecnt] = c; next[ecnt] = head[u]; head[u] = ecnt++; 25 to[ecnt] = u; cost[ecnt] = c; next[ecnt] = head[v]; head[v] = ecnt++; 26 } 27 28 void dfs1(int u, int f) { 29 size[u] = 1; 30 maxSize[u] = 0; 31 for(int p = head[u]; ~p; p = next[p]) { 32 int &v = to[p]; 33 if(v == f || del[v]) continue; 34 dfs1(v, u); 35 size[u] += size[v]; 36 maxSize[u] = max(maxSize[u], size[v]); 37 } 38 list[cnt++] = u; 39 } 40 41 int get_root(int u, int f) { 42 cnt = 0; 43 dfs1(u, f); 44 int ret, maxr = INF; 45 for(int i = 0; i < cnt; ++i) { 46 int &x = list[i]; 47 if(max(maxSize[x], size[u] - size[x]) < maxr) { 48 ret = x; 49 maxr = max(maxSize[x], size[u] - size[x]); 50 } 51 } 52 return ret; 53 } 54 55 void dfs2(int u, int f, int dis) { 56 list[cnt++] = dis; 57 for(int p = head[u]; ~p; p = next[p]) { 58 int &v = to[p]; 59 if(v == f || del[v]) continue; 60 dfs2(v, u, dis + cost[p]); 61 } 62 } 63 64 int calc(int a, int b) { 65 int j = b - 1, ret = 0; 66 for(int i = a; i < b; ++i) { 67 while(list[i] + list[j] > k && i < j) --j; 68 ret += j - i; 69 if(j == i) break; 70 } 71 return ret; 72 } 73 74 int ans = 0; 75 76 void work(int u, int f) { 77 int root = get_root(u, f); 78 del[root] = true; 79 int last = 0; cnt = 0; 80 for(int p = head[root]; ~p; p = next[p]) { 81 int &v = to[p]; 82 if(del[v]) continue; 83 dfs2(v, root, cost[p]); 84 sort(list + last, list + cnt); 85 ans -= calc(last, cnt); 86 last = cnt; 87 } 88 list[cnt++] = 0; 89 sort(list, list + cnt); 90 ans += calc(0, cnt); 91 for(int p = head[root]; ~p; p = next[p]) { 92 int &v = to[p]; 93 if(del[v]) continue; 94 work(v, root); 95 } 96 } 97 98 int main() { 99 while(scanf("%d%d", &n, &k) != EOF) {100 if(n == 0 && k == 0) break;101 init();102 for(int i = 1; i < n; ++i) {103 int u, v, c;104 scanf("%d%d%d", &u, &v, &c);105 add_edge(u, v, c);106 }107 ans = 0;108 work(1, 0);109 printf("%d\n", ans);110 }111 }