首页 > 代码库 > POJ 1741 Tree 树分治（点分治）
POJ 1741 Tree 树分治（点分治）
题意：给你一颗带边权树，问你其中 dis（v,u） <= k 的对数
解题思路：
首先推荐大家看 09年国家集训队漆子超 的论文
看到这题 我们可以有三种思路
第一种是枚举起点，遍历整颗树找对数 时间复杂度 为 O（n^2），空间复杂度为 O（n）
第二种是树形dp的思想 每个节点用 长度为 K 数组维护 ，递归求解 时间复杂度为 O（n ^k）空间复杂度 为 O（n）
第三种就是我们要用到的点分治的思想。
这种思想的具体思路是 先找到一个 根 对这个根进行 深搜， 找出 根到 其所有子节点的距离D[I]
分两种情况，第一种是 点对不经过 这个 根 ，那么递归子节点就行
第二种情况就是 点经过这个根 ，这里又分两种情况
那么其中 D[i] + D[j] <= K 为我们所求
但是 D[i] + D[j] <= K 的情况中 有可能 i 和 j 是属于 根的同一颗子树的，所以要去除掉这种情况，
可以知道 这两种情况可以调用一个函数计数，具体的方法就是 对 D[i] 排序 ，首尾双递推。 这里时间复杂度为 N×logn（对与第二种，我们可以用全局数组，每次处理一个子节点的一段）
找完这个根以后我们需要 删除 这个 根 ，继续 寻找子树就行。对与每一颗子树，我们要使得时间复杂度尽可能低的话，我们需要找到这颗子数的重心为根。
那这样递归层数就变成了 logn 总时间复杂度为 N×lognxlogn
解题代码：
1 // File Name: poj1741.cpp 2 // Author: darkdream 3 // Created Time: 2014年10月05日 星期日 09时49分58秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 #define maxn 10005 26 using namespace std; 27 int n , m ; 28 struct node{ 29 int ne; 30 int dis; 31 node(int _ne,int _dis) 32 { 33 ne = _ne; 34 dis = _dis; 35 } 36 }; 37 vector<node> mp[maxn]; 38 int dn = 0; 39 int vis[maxn]; 40 int dis[maxn]; 41 int sum[maxn]; 42 int mx[maxn]; 43 44 int getsize(int k , int la) 45 { 46 sum[k] = 1; 47 mx[k] = 0; 48 int num = mp[k].size(); 49 for(int i = 0;i < num ;i ++) 50 { 51 if(!vis[mp[k][i].ne] && mp[k][i].ne != la) 52 { 53 getsize(mp[k][i].ne,k); 54 mx[k] = max(sum[mp[k][i].ne],mx[k]); 55 sum[k] += sum[mp[k][i].ne]; 56 } 57 } 58 } 59 int root; 60 int mxv; 61 void getroot(int k ,int la,int tans) 62 { 63 int tt = max(tans - sum[k] ,mx[k]); 64 if(tt < mxv) 65 { 66 // printf("****%d\n",k); 67 mxv = tt; 68 root = k ; 69 } 70 int num = mp[k].size(); 71 for(int i = 0 ;i < num ;i ++) 72 { 73 if(!vis[mp[k][i].ne] && mp[k][i].ne != la) 74 { 75 getroot(mp[k][i].ne,k,tans); 76 } 77 } 78 } 79 void getdis(int k , int la,int tdis) 80 { 81 dis[dn] = tdis; 82 dn ++ ; 83 int num = mp[k].size(); 84 for(int i = 0 ;i < num ;i ++) 85 { 86 if(mp[k][i].ne != la && !vis[mp[k][i].ne]) 87 { 88 getdis(mp[k][i].ne,k,tdis + mp[k][i].dis); 89 } 90 } 91 } 92 int getans(int l ,int r ) 93 { 94 sort(dis+l,dis+r); 95 int ans = 0 ; 96 r = r-1; 97 while(r > l) 98 { 99 if(dis[l] + dis[r] <= m)100 {101 ans += r - l ; 102 l ++ ;103 }else {104 r-- ;105 }106 }107 return ans;108 }109 int solve(int k)110 {111 // printf("%d**\n",k);112 root = k ; 113 getsize(k,0);114 mxv = 1e9;115 getroot(k,0,sum[k]);116 k = root;117 //printf("%d %d\n",k,sum[k]);118 dn = 1 ; 119 dis[0] = 0;120 int tans = 0 ; 121 int j ;122 int num = mp[k].size();123 for(int i = 0 ;i < num ;i ++)124 {125 if(!vis[mp[k][i].ne])126 {127 j = dn;128 getdis(mp[k][i].ne,k,mp[k][i].dis);129 tans += getans(j,dn);130 // printf("%d %d %d\n",tans,j,dn);131 }132 }133 int ans = getans(0,dn) - tans;134 /* printf("ans = %d\n",ans);135 for(int i = 0 ;i < dn ;i++)136 printf("%d ",dis[i]);137 printf("\n");138 printf("ans = %d\n",ans);139 */140 vis[k] = 1; //删除这个点141 142 for(int i = 0 ;i < num ;i ++)143 {144 if(!vis[mp[k][i].ne])145 {146 ans += solve(mp[k][i].ne);147 }148 }149 return ans;150 }151 int main(){152 //freopen("out","r",stdin);153 while(scanf("%d %d",&n,&m) != EOF)154 {155 if(n == 0 && m == 0 )156 break;157 int u,v,w;158 for(int i = 1;i <= n;i ++)159 mp[i].clear();160 for(int i = 1;i < n;i ++)161 {162 scanf("%d %d %d",&u,&v,&w);163 mp[u].push_back(node(v,w));164 mp[v].push_back(node(u,w));165 }166 memset(vis,0,sizeof(vis));167 printf("%d\n",solve(1));168 }169 return 0;170 }
POJ 1741 Tree 树分治（点分治）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。