Tree POJ-1741（点分治+树形DP）

题意：

给一棵树，问有多少条边的长度大于$K$。

思路：

对于一个点$x$，处理出所有其他点到它的距离，$n^2$找出经过它的所有长度加起来大于$K$的点对的数量。

但是找到的这些点对中存在不经过点$x$的点对，则减去这些点对的数量，若$v$是$x$的子节点，$w$是$v$到$x$的距离，则减去距离点$v$和大于$K-2*w$的点对的数量。

然后在树上删去点$x$。

为了降低复杂度，每次选择重心删去，保证删去后所有联通块的点的最大值最小。

代码：

  1 //#include<bits/stdc++.h>
  2 #include <set>
  3 #include <map>
  4 #include <stack>
  5 #include <cmath>
  6 #include <queue>
  7 #include <cstdio>
  8 #include <string>
  9 #include <vector>
 10 #include <cstring>
 11 #include <iostream>
 12 #include <algorithm>
 13 
 14 #define ll long long
 15 #define pll pair<ll,ll>
 16 #define pii pair<int,int>
 17 #define bug printf("*********
")
 18 #define FIN freopen("input.txt","r",stdin);
 19 #define FON freopen("output.txt","w+",stdout);
 20 #define IO ios::sync_with_stdio(false),cin.tie(0)
 21 #define ls root<<1
 22 #define rs root<<1|1
 23 #define pb push_back
 24 
 25 using namespace std;
 26 const int inf = 2e9 + 7;
 27 const ll Inf = 1e18 + 7;
 28 const int maxn = 2e4 + 5;
 29 const int mod = 1e9 + 7;
 30 
 31 struct node
 32 {
 33     int v, w, next;
 34 }edge[maxn<<1];
 35 
 36 int n, k;
 37 int root, minn, cnt;
 38 int dis[maxn], siz[maxn], f[maxn];
 39 int head[maxn],tot;
 40 int ans;
 41 
 42 void init()
 43 {
 44     tot = 0, ans = 0;
 45     memset(head, -1, sizeof head);
 46     memset(f, 0, sizeof f);
 47 }
 48 
 49 void add(int u, int v, int w)
 50 {
 51     edge[tot].v = v, edge[tot].w = w;
 52     edge[tot].next = head[u];
 53     head[u] = tot++;
 54 }
 55 
 56 int get_size(int x, int fa)//以x为根的儿子数
 57 {
 58     siz[x] = 1;
 59     for (int i = head[x]; i != -1; i = edge[i].next)
 60     {
 61         int v = edge[i].v;
 62         if (v == fa || f[v])    continue;
 63         siz[x] += get_size(v, x);
 64     }
 65     return siz[x];
 66 }
 67 
 68 void get_root(int x, int num, int fa)//找重心(最大的儿子最小)
 69 {
 70     int maxx = num - siz[x];
 71     for (int i = head[x]; i != -1; i = edge[i].next)
 72     {
 73         int v = edge[i].v;
 74         if (v == fa || f[v])    continue;
 75         maxx = max(maxx, siz[v]);
 76         get_root(v, num, x);
 77     }
 78     if (maxx < minn)
 79     {
 80         minn = maxx;
 81         root = x;
 82     }
 83 }
 84 
 85 void get_dis(int x, int d, int fa)//获取以x为根的距离
 86 {
 87     dis[++cnt] = d;
 88     for (int i = head[x]; i != -1; i = edge[i].next)
 89     {
 90         int v = edge[i].v, w = edge[i].w;
 91         if (v == fa || f[v])    continue;
 92         get_dis(v, d + w, x);
 93     }
 94 }
 95 
 96 int work(int x, int d)
 97 {
 98     cnt = 0;
 99     get_dis(x, d, 0);
100     sort(dis + 1, dis + 1 + cnt);
101     int res = 0, l = 1, r = cnt;
102     while (l < r)
103     {
104         while (l<r && dis[l] + dis[r]>k)    r--;
105         res += r - l;
106         l++;
107     }
108     return res;
109 }
110 
111 void dfs(int x)
112 {
113     minn = inf;
114     get_size(x, 0);
115     get_root(x, siz[x], 0);
116     ans += work(root, 0);
117     f[root] = 1;//去除这个点
118     for (int i = head[root]; i != -1; i = edge[i].next)
119     {
120         int v = edge[i].v, w = edge[i].w;
121         if (f[v])    continue;
122         ans -= work(v, w);//减去不需要经过root的情况
123         dfs(v);
124     }
125 }
126 
127 int main()
128 {
129     while (~scanf("%d %d", &n, &k) && n && k)
130     {
131         init();
132         for (int i = 1; i < n; ++i)
133         {
134             int u, v, w;
135             scanf("%d %d %d", &u, &v, &w);
136             add(u, v, w), add(v, u, w);
137         }
138         dfs(1);
139         printf("%d
", ans);
140     }
141 }