POJ1741--Tree （树的点分治） 求树上距离小于等于k的点对数

时间：2022-06-28 15:15:17
Tree
Time Limit: 1000MS   Memory Limit: 30000K
Total Submissions: 12276   Accepted: 3886

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.

Sample Input

5 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0

Sample Output

8

题意：求树上距离小于等于k的点对数。。

我是用 点的分治做的，，据说还可以用启发式合并做，，附上链接http://blog.csdn.net/asdfgh0308/article/details/39845489。。挖个坑。

定义树的重心 s 为 删除s点后的 最大子树的点数 小于n/2。  那么对于任意满足条件的点对 有两种情况，，

其路径 1要么经过s  2要么不经过s。。

对于1 我们只需要 求出 以s为根的子树的点到s的距离即可。。

对于2  可以递归处理 分解为 多个1。。然后就可以求出来了。。

复杂度为nlogn*logn

  1 #include <set>
  2 #include <map>
  3 #include <cmath>
  4 #include <ctime>
  5 #include <queue>
  6 #include <stack>
  7 #include <cstdio>
  8 #include <string>
  9 #include <vector>
 10 #include <cstdlib>
 11 #include <cstring>
 12 #include <iostream>
 13 #include <algorithm>
 14 using namespace std;
 15 typedef unsigned long long ull;
 16 typedef long long ll;
 17 const int inf = 0x3f3f3f3f;
 18 const double eps = 1e-8;
 19 const int maxn = 1e4+10;
 20 struct Edge
 21 {
 22     int to, len;
 23     Edge (int _x, int _len)
 24     {
 25         to = _x;
 26         len = _len;
 27     }
 28 };
 29 vector<Edge>G[maxn << 1];
 30 int siz[maxn];
 31 bool vis[maxn];
 32 void Get_size(int root, int father)
 33 {
 34     siz[root] = 1;
 35     for (int i = 0; i < G[root].size(); i++)
 36     {
 37         int v = G[root][i].to;
 38         if (v == father || vis[v] == true)
 39             continue;
 40         Get_size(v, root);
 41         siz[root] += siz[v];
 42     }
 43 }
 44 typedef pair<int,int>pii;
 45 pii FindGravity(int root, int father, int t)
 46 {
 47     pii res = make_pair(inf, -1);
 48     int m = 0, sum = 1;
 49     for (int i = 0; i < G[root].size(); i++)
 50     {
 51         int v = G[root][i].to;
 52         if (v == father || vis[v] == true)
 53             continue;
 54         res = min(res, FindGravity(v, root, t));
 55         m = max(m, siz[v]);
 56         sum += siz[v];
 57     }
 58     m = max(m, t-sum);
 59     res = min(res, make_pair(m, root));
 60     return res;
 61 }
 62 void Get_len(int root, int father, int d, vector<int>&len)
 63 {
 64     len.push_back(d);
 65     for (int i = 0; i < G[root].size(); i++)
 66     {
 67         int v = G[root][i].to;
 68         if (v == father || vis[v] == true)
 69             continue;
 70         Get_len(v, root, d+G[root][i].len, len);
 71     }
 72 }
 73 int K;
 74 int cnt_pair(vector<int>&ds)
 75 {
 76     int res = 0;
 77     sort (ds.begin(), ds.end());
 78     int j = ds.size() - 1;
 79     for (int i = 0; i < ds.size(); i++)
 80     {
 81         while (j > i && ds[i] + ds[j] > K)
 82         {
 83             j--;
 84         }
 85         res += (j > i ? j - i : 0);
 86     }
 87     return res;
 88 }
 89 int solve(int root)
 90 {
 91     int ans = 0;
 92     Get_size(root, -1);
 93     int s = FindGravity(root, -1, siz[root]).second;
 94     if (s == -1)
 95         return 0;
 96     vis[s] = true;
 97     for (int i = 0; i < G[s].size(); i++)
 98     {
 99         int v = G[s][i].to;
100         if (vis[v] == true)
101             continue;
102         ans += solve(v);
103     }
104     vector<int>ds;
105     ds.push_back(0);
106     for (int i = 0; i < G[s].size(); i++)
107     {
108         int v = G[s][i].to;
109         if (vis[v] == true)
110             continue;
111         vector<int>rds;
112         Get_len(v, s, G[s][i].len, rds);
113         ans -= cnt_pair(rds);
114         ds.insert(ds.end(), rds.begin(), rds.end());
115     }
116     ans += cnt_pair(ds);
117     vis[s] = false;
118     return ans;
119 }
120 int main()
121 {
122     #ifndef ONLINE_JUDGE
123         freopen("in.txt","r",stdin);
124     #endif
125     int n;
126     while ( scanf ("%d%d", &n, &K), n && K)
127     {
128         int u, v, c;
129         for (int i = 0; i <= n; i++)
130             G[i].clear();
131         for (int i = 0; i < n-1; i++)
132         {
133             scanf ("%d%d%d", &u, &v, &c);
134             G[u].push_back(Edge(v,c));
135             G[v].push_back(Edge(u,c));
136         }
137         printf("%d\n", solve(n/2+1));
138     }
139     return 0;
140 }

 ②第二种姿势，，200ms左右

  1 #include <set>
  2 #include <map>
  3 #include <cmath>
  4 #include <ctime>
  5 #include <queue>
  6 #include <stack>
  7 #include <cstdio>
  8 #include <string>
  9 #include <vector>
 10 #include <cstdlib>
 11 #include <cstring>
 12 #include <iostream>
 13 #include <algorithm>
 14 using namespace std;
 15 typedef unsigned long long ull;
 16 typedef long long ll;
 17 const int inf = 0x3f3f3f3f;
 18 const double eps = 1e-8;
 19 const int maxn = 1e4+10;
 20 struct Edge
 21 {
 22     int to, len, next;
 23 }e[maxn << 1];
 24 int head[maxn], tot, N, K;
 25 void add_edge(int u, int v, int c)
 26 {
 27     e[tot].to = v;
 28     e[tot].len = c;
 29     e[tot].next = head[u];
 30     head[u] = tot++;
 31 }
 32 int siz[maxn],Mtree[maxn];  // Mtree为最大子树的大小 siz为子树的大小
 33 bool vis[maxn];
 34 int center;
 35 void FindGravity(int u, int father, int cnt)  // 查找重心 center
 36 {
 37     siz[u] = 1;
 38     Mtree[u] = 0;
 39     for (int i = head[u]; ~i; i = e[i].next)
 40     {
 41         int v = e[i].to;
 42         if (v == father || vis[v] == true)
 43             continue;
 44         FindGravity(v, u, cnt);
 45         siz[u] += siz[v];
 46         Mtree[u] = max(Mtree[u], siz[v]);
 47     }
 48     Mtree[u] = max(cnt - siz[u], Mtree[u]);
 49     if (Mtree[center] > Mtree[u])
 50         center = u;
 51 }
 52 int S[maxn], dep[maxn], top;
 53 void Get_len(int u, int father, int d)
 54 {
 55     S[top++] = d;
 56     for (int i = head[u]; ~i; i = e[i].next)
 57     {
 58         int v = e[i].to;
 59         if (vis[v] == true || v == father)
 60             continue;
 61       //  dep[v] = dep[u] + e[i].len;
 62         Get_len(v, u, d+e[i].len);
 63     }
 64 }
 65 int Get_cnt(int u, int d)
 66 {
 67     int res = 0;
 68     top = 0;
 69     //dep[u] = d;
 70     Get_len(u, 0, d);
 71     sort (S, S+top);
 72     int j = top - 1;
 73     for (int i = 0; i < top; i++)
 74     {
 75         while (j > i && S[i] + S[j] > K)
 76             j--;
 77         res += (j > i ? j-i : 0);
 78     }
 79     return res;
 80 }
 81 int ans;
 82 void solve(int r)
 83 {
 84     vis[r] = true;
 85     ans += Get_cnt(r, 0);
 86     for (int i = head[r]; ~i; i = e[i].next)
 87     {
 88         int v = e[i].to;
 89         if (vis[v] == true)
 90             continue;
 91         ans -= Get_cnt(v, e[i].len);
 92         center = 0;
 93         FindGravity(v, r, siz[v]);
 94         solve(center);
 95     }
 96 }
 97 void init()
 98 {
 99     tot = 0;
100     Mtree[0] = N;
101     memset(head, -1, sizeof(head));
102     memset(vis, false, sizeof(vis));
103     center = 0;
104 }
105 int main()
106 {
107     #ifndef ONLINE_JUDGE
108         freopen("in.txt","r",stdin);
109     #endif
110     while (scanf ("%d%d", &N,&K), N && K)
111     {
112         init();
113         int u, v, c;
114         for (int i = 0; i < N-1; i++)
115         {
116             scanf ("%d%d%d", &u, &v, &c);
117             add_edge(u, v, c);
118             add_edge(v, u, c);
119         }
120         ans = 0;
121         FindGravity(N/2+1, -1, N);
122         solve(center);
123         printf("%d\n", ans);
124     }
125     return 0;
126 }

 

标签：

相关文章