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 }

时间: 10-05

POJ 1741 Tree 树分治(点分治)的相关文章

POJ 1741 Tree(树的点分治,入门题)

Tree Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 21357   Accepted: 7006 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 in

Poj 1741 Tree (树的分治)

题目链接: Poj 1741 Tree 这个题目Tle的好苦啊,原来一直是树的重心没找对,Tle好长时间,终于对了,好感动,先贴个代码. 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 10010; 8 struct node 9 { 10 int

POJ 1741 Tree(树分治)

去网上搜题解大多数都是说论文,搜了论文看了看,写的确实挺好,直接复制过来. 不过代码中有些细节还是要注意的,参考这篇http://blog.sina.com.cn/s/blog_6d5aa19a0100o73m.html一段 设X为满足i<j且Depth[i]+Depth[j]<=K的数对(i,j)的个数设Y为满足i<j,Depth[i]+Depth[j]<=K且Belong[i]=Belong[j]数对(i,j)的个数那么我们要统计的量便等于X-Y 求X.Y的过程均可以转化为以下

POJ 1741 Tree 树形DP(分治)

链接:id=1741">http://poj.org/problem?id=1741 题意:给出一棵树,节点数为N(N<=10000),给出N-1条边的两点和权值,给出数值k,问树上两点最短距离小于k的点对有多少个. 思路:拿到题的第一反应是LCA问题,只是细一想询问次数极限情况能够达到10000*5000次.即使用Tarjan也是超时没商议的. 2009年国家队论文提供了树的分治思想,对于本题就是树的分治的点分治的应用.每次找到能使含节点最多的子树的节点最少的根分而治之,相同方式分

【POJ 1741】 Tree (树的点分治)

Tree 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)

POJ 1741 Tree ——(树分治)

思路参考于:http://blog.csdn.net/yang_7_46/article/details/9966455,不再赘述. 复杂度:找树的重心然后分治复杂度为logn,每次对距离数组dep排序复杂度为nlogn,而找重心的复杂度为dfs的复杂度--O(n),因此总的复杂度为O(nlognlogn). 因为第一次写树分治,留个代码: 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h>

数据结构(树,点分治):POJ 1741 Tree

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 e

POJ 1741 Tree (树的分治,树的重心)

题意:给一棵树,n个节点,给定一个数k,求任意满足dist(a,b)<=k的点对的数量. 思路: 这道题的思路比较简单,但是细节很多. 此题可以用分治法,如何分治? (1)如果path(a,b)不经过根,那么肯定在根的某棵子树下,递归解决. (2)如果path(a,b)经过根,那么肯定在根的不同子树下,处理它. 怎样处理?如果知道了每棵子树中的节点到根的距离,暂且将每棵子树的节点分到每个独立的桶里.每个节点都可以和其他桶里的点组成点对,只要距离<=k的话就满足要求了.逐个算可能超时了,用个简单

POJ 1741 Tree(树分治|ltc男人八题)

 题意:求树上距离小于等于K的点对有多少个. 思路:这道题很容易想到树分治,对于当前的根节点来说,任意两个结点之间要么过根结点,要么在一棵子树中. 那么我们dfs一次求出所有点到根结点的距离,然后用o(n)的时间判定有多少节点对符合,(判断方法稍后说) 但是这样有很多在一颗子树中的节点对我们会求重复,我们需要减去在一棵子树中结点对小于等于k的数量,也就是说,我们这一步求的是在不同子树中距离小于等于k的节点对的个数. 接下来说判定方法,将每个点到根结点的距离排序,用两个指针指向队首和队尾,当结