POJ 1741 Tree（树的分治）

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 #include <cstdio>
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <cstring>
  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
", ans);
110     }
111 }

View Code