poj 1741 树分治

题意：

　　求树上距离不超过k的点对数

解决：

　　很经典的树分治

　　先不考虑树退化的情况。

　　对每个节点u，假设u有x个子节点，v1 v2 v3 .. vx，求出以u为根的子树上，所有不属于同一个v节点的，且距离不大于k的点对数。

　　且递归下去就是答案，无重无缺。

　　至于如何求上述的点对数量，

　　假设A = 以u为根节点的子树上所有的距离不大于k的点对数

　　　　B = 以u为根节点的子树上，同时属于u的某个同一个子节点v的，且距离不大于k的点对数

　　则 A - B 即为答案

　　下面加上，考虑树退化的问题，每次在dfs的时候，找到当前u为根的子树的重心，作为根去处理即可。

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <vector>
  5 
  6 const int MAXN = 1e4+10;
  7 const int MAXM = MAXN<<2;
  8 
  9 struct Edge{
 10     int u, v, w, next;
 11     Edge(int _u, int _v, int _w, int _next)
 12     {
 13         u = _u;
 14         v = _v;
 15         w = _w;
 16         next = _next;
 17     }
 18     Edge(){}
 19 }edge[MAXM];
 20 int tot, head[MAXN];
 21 int n, k;
 22 int siz[MAXN];
 23 int max_sub[MAXN];
 24 int dist[MAXN];
 25 bool vis[MAXN];
 26 int max_siz, root;
 27 std::vector<int> ve;
 28 int res;
 29 
 30 
 31 void inline addEdge(int u, int v, int w)
 32 {
 33     edge[++tot] = Edge(u, v, w, head[u]);
 34     head[u] = tot;
 35 }
 36 
 37 void init()
 38 {
 39     tot = 1;
 40     res = 0;
 41     memset(head, 0, sizeof head);
 42     memset(vis, false, sizeof vis);
 43 }
 44 
 45 
 46 void getRoot(int u, int fa_node, int root_now)
 47 {
 48     max_sub[u] = std::max(max_sub[u], siz[root_now] - siz[u]);
 49     if (max_siz > max_sub[u]) {
 50         max_siz = max_sub[u];
 51         root = u;
 52     }
 53     for (int i = head[u]; i > 0; i = edge[i].next) {
 54         int v = edge[i].v;
 55         if (v == fa_node || true == vis[v])
 56             continue;
 57         getRoot(v, u, root_now);
 58     }
 59 }
 60 
 61 void getSize(int u, int fa_node)
 62 {
 63     siz[u] = 1, max_sub[u] = 0;
 64     for (int i = head[u]; i > 0; i = edge[i].next) {
 65         int v = edge[i].v;
 66         if (v == fa_node || true == vis[v])
 67             continue;
 68         getSize(v, u);
 69         siz[u] += siz[v];
 70         max_sub[u] = std::max(max_sub[u], siz[v]);
 71     }
 72 }
 73 
 74 void getDist(int u, int fa_node, int d)
 75 {
 76     ve.push_back(d);
 77     for (int i = head[u]; i > 0; i = edge[i].next) {
 78         int v = edge[i].v, w = edge[i].w;
 79         if (v == fa_node || true == vis[v])
 80             continue;
 81         getDist(v, u, d+w);
 82     }
 83 }
 84 
 85 int calc(int u, int d)
 86 {
 87     ve.clear();
 88     getDist(u, -1, d);
 89     std::sort(ve.begin(), ve.end());
 90     int ans = 0;
 91     int l = 0, r = ve.size() - 1;
 92     while (l <= r) {
 93         if (ve[l] + ve[r] <= k) {
 94             ans += (r - l);
 95             ++l;
 96         }
 97         else
 98             --r;
 99     }
100     return ans;
101 }
102 
103 void dfs(int u)
104 {
105     getSize(u, -1);
106     max_siz = n;
107     getRoot(u, -1, u);
108     res += calc(root, 0);
109     vis[root] = true;
110     for (int i = head[root]; i > 0; i = edge[i].next) {
111         int v = edge[i].v, w = edge[i].w;
112         if (true == vis[v])
113             continue;
114         res -= calc(v, w);
115         dfs(v);
116     }
117 }
118 
119 int main()
120 {
121     while (~scanf("%d%d", &n, &k), (n||k)) {
122         init();
123         for (int i = 1, u, v, w; i <= n-1; ++i) {
124             scanf("%d%d%d", &u, &v, &w);
125             addEdge(u, v, w);
126             addEdge(v, u, w);
127         }
128         dfs(1);
129         printf("%d
", res);
130     }
131 }

View Code