日历
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 |
|
统计
- 随笔 - 20
- 文章 - 1
- 评论 - 40
- 引用 - 0
导航
常用链接
留言簿(3)
随笔档案
文章档案
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
题目叙述: 给出一个有n个节点的树, 一个整数k. 定义dist(u, v)为节点u, v间的距离. 求这棵树中有多少节点对(u, v)满足dist(u, v)<=k. (n<=10000)
-------------------------------------------
对于这样一个数据范围,显然O(n^2)的直接算是会超时的。
大体的思路是: 1.一个树中的路径可以分为两种:一种是过根的,一种是不过根的--那一定是过子树的根。所以可以对于每一棵树都统计过根的路径中长度小于等于K的有多少,然后加起来就是答案。 2.对于每一棵子树,找出子树中所有点到根的距离,排序并统计路径长度小于等于K的条数。对于一个有序的序列a,如果有i<j且a[i]+a[j]<=K,那么a[i] + a[i+1~j]<=K,所以可以找出对于一个i满足条件最大的j或对于一个j满足条件的最小的i,进行统计。 3.这样统计出来的路径有些是从某个子树到根后,又返回原来的子树,显然这样的路径是不满足条件的。而这些路径一定经过当前根的儿子,所以为了排除这些多余的路径,只需要减去所有的在儿子的子树中过儿子的路径条数,当然,这些路径长度并不是小于等于K了,而是小于等于K-2*根到儿子的边的长度。 4.这样虽然能够得到解,但是时间复杂度在一条链的情况下最坏为O(n^2logn)(n个点,每个点快排)。对于一个无根树的统计,我们发现根的选择是无关结果的。所以每次对于一棵子树我们处理的时候,我们选择的根不一定刚好就是上一个根的儿子,而可以是当前子树当中的任意一个点,即每次把子树看做一个无根图来处理。而对于一个大小为n的无根树,一定存在至少一个点是的以这个点作为根的树的每个儿子的大小都不超过n/2。所以我们每次处理的时候就在当前的无根树找到一个这样的点,把它作为当前无根树的根。这个点叫做树的重心。这样的话每次处理节点的数目至少会减少一半,所以处理的深度不会超过logn。这样就把总的时间复杂度降到了O(nlognlogn)。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 7 #define MAXN 10000 8 #define MAXM MAXN*2 9![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 10 using namespace std; 11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 12 int n,K; 13 int Count = 0; 14 int begin[MAXN+1],end[MAXM+1],next[MAXM+1],cost[MAXM+1]; 15![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void AddEdge(int a,int b,int c) { 16 Count++; 17 next[Count] = begin[a]; 18 begin[a] = Count; 19 end[Count] = b; 20 cost[Count] = c; 21 } 22 void Solve(); 23![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void Init() { 24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while (true) { 25 scanf("%d%d",&n,&K); 26 if (n == 0 && K == 0) 27 break; 28 else 29 Solve(); 30 } 31 } 32![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 33![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 34 bool hash[MAXN+1]; 35 int size[MAXN+1]; 36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int GetSize(int x,int fa) { 37 size[x] = 1; 38 for (int now = begin[x]; now; now = next[now]) 39 if (!hash[end[now]] && end[now]!=fa) 40 size[x] += GetSize(end[now],x); 41 return size[x]; 42 } 43![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 44![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int GetBestRoot(int x) { 45 GetSize(x,0); 46![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while (true) { 47 int MaxSize = 0,id = 0; 48 for (int now = begin[x]; now; now = next[now]) 49 if (!hash[end[now]] && MaxSize < size[end[now]]) 50 MaxSize = size[id = end[now]]; 51 if (MaxSize <= (size[x] >> 1)) 52 break; 53 size[x] -= size[id], size[id] += size[x], x = id; 54 } 55 return x; 56 } 57 int dist[MAXN+1]; 58 int cnt; 59![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void GetDist(int x,int fa,int d) { 60 if (d>K) return; 61 dist[++cnt] = d; 62 for (int now = begin[x]; now; now = next[now]) 63 if (!hash[end[now]] && end[now] != fa) 64 GetDist(end[now],x,d + cost[now]); 65 } 66![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int cmp(const void *a,const void *b) { 67 return (*(int *)a) - (*(int *)b); 68 } 69![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int dfs(int x) { 70 x = GetBestRoot(x); 71 hash[x] = true; 72 int ret = 0; 73 for (int now = begin[x]; now; now = next[now]) 74 if (!hash[end[now]]) 75 ret += dfs(end[now]); 76 cnt = 0; 77 GetDist(x,0,0); 78 qsort(dist+1,cnt,sizeof(dist[0]),cmp); 79 80 81 int l = 1, r = cnt; 82![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while (l<r) { 83 if (dist[l] + dist[r]<=K) ret += r-l, l++; 84 else r--; 85 } 86 for (int now = begin[x]; now; now = next[now]) 87![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if (!hash[end[now]]) { 88 int limit = K - cost[now] * 2; 89 cnt = 0; 90 GetDist(end[now],0, 0); 91 qsort(dist+1,cnt,sizeof(dist[0]),cmp); 92 int l = 1, r = cnt; 93![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while (l<r) { 94 if (dist[l] + dist[r]<=limit) ret -= r-l, l++; 95 else r--; 96 } 97 } 98 hash[x] = false; 99 return ret; 100 } 101![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 102![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void Solve() { 103 Count = 0; 104 memset(begin,0,sizeof(begin)); 105 int t1,t2,t3; 106![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for (int i = 1; i<n; i++) { 107 scanf("%d%d%d",&t1,&t2,&t3); 108 AddEdge(t1,t2,t3); 109 AddEdge(t2,t1,t3); 110 } 111 printf("%d\n",dfs(1)); 112 } 113![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 114![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() { 115 Init(); 116 return 0; 117 } 118![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
评论:
-
# re: 男人8题之 Tree (pku 1741)[未登录]
Posted @ 2010-01-05 21:38
树形dp+归并排序的方法,lz的代码如果用vector能更简洁
dp[i][j]表示以i为根的子树长度为j的点对数 回复 更多评论
-
# re: 男人8题之 Tree (pku 1741)
Posted @ 2010-01-07 10:47
@forestkeeper
可能子树的长度很长,你的那种方法空间和时间都无法承受啊! 回复 更多评论
-
# re: 男人8题之 Tree (pku 1741)
Posted @ 2010-01-09 11:11
@TimTopCoder
恩,没A过那题,去A下。。。 回复 更多评论
-
# re: 男人8题之 Tree (pku 1741)
Posted @ 2010-03-15 15:26
受益匪浅, 非常感谢!!!
回复 更多评论
|