POJ1741 Tree（树的点分治）

时间：2022-11-28 04:22:39

题目给一棵边带权的树，统计路径长度<=k的点对数。

楼教主男人八题之一，分治算法在树上的应用。

一开始看论文看不懂，以为重心和距离那些是一遍预处理得来的。。感觉上不敢想每棵子树都求一遍重心和距离——那样时间复杂度怎么会只有O(nlogn)？

后来想通了，真的是对于每颗子树都把其所有结点单独提取出来，而且这么做就是O(nlogn)！

  • 首先每次都选择重心进行分治，这样最多大概处理logn层，每一层都包含若干棵子树；
  • 考虑每一层的每棵子树要提取的结点个数的和：第一层：n，第二层：n-1(第一层子树个数)，第三层：n-(第一层子树个数+第二层子树个数)……不妨就认为每一层都有n个结点的信息要处理，而有logn层，所以其实总共就只有nlogn个（次）结点要处理；
  • 对于每一层每棵子树求重心的时间复杂度是线性的，而每层n个结点，最多logn层，所以求重心时间的复杂度就是O(nlogn)；
  • 对于这道题子树要计算的信息是各个结点到根的距离，然后对其排序并在线性时间复杂度统计点对数目，其处理每棵子树时间复杂度是O(xlogx)，x为该子树结点个数；不妨设某层各个子树结点个数为a、b、c……，而a+b+c+……=n，则aloga+blogb+clogc<=nlogn，共logn层，所以处理所有层所有子树信息的时间复杂度就是O(nlog2n)；
  • 故这一题用点分治的时间复杂度是O(nlog2n)！

写这一题，捋清思路后分了好几个函数逐一实现，感觉框架挺清晰的，提交之后就1A还是很爽的。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 #define INF (1<<30)
  6 #define MAXN 11111
  7 
  8 struct Edge{
  9     int v,w,next;
 10 }edge[MAXN<<1];
 11 int NE,head[MAXN];
 12 void addEdge(int u,int v,int w){
 13     edge[NE].v=v; edge[NE].w=w; edge[NE].next=head[u];
 14     head[u]=NE++;
 15 }
 16 
 17 int n,k,ans;
 18 bool vis[MAXN];
 19 
 20 int centre,minimum,size[MAXN];
 21 void getSize(int u,int fa){
 22     size[u]=1;
 23     for(int i=head[u]; i!=-1; i=edge[i].next){
 24         int v=edge[i].v;
 25         if(v==fa || vis[v]) continue;
 26         getSize(v,u);
 27         size[u]+=size[v];
 28     }
 29 }
 30 void getCentre(int u,int fa,int &tot){
 31     int res=tot-size[u];
 32     for(int i=head[u]; i!=-1; i=edge[i].next){
 33         int v=edge[i].v;
 34         if(v==fa || vis[v]) continue;
 35         res=max(res,size[v]);
 36         getCentre(v,u,tot);
 37     }
 38     if(minimum>res){
 39         minimum=res;
 40         centre=u;
 41     }
 42 }
 43 
 44 int a[MAXN],b[MAXN],an,bn;
 45 void dfs(int u,int fa,int dist){
 46     a[an++]=b[bn++]=dist;
 47     for(int i=head[u]; i!=-1; i=edge[i].next){
 48         int v=edge[i].v;
 49         if(v==fa || vis[v]) continue;
 50         dfs(v,u,dist+edge[i].w);
 51     }
 52 }
 53 int count(int *c,int &cn){
 54     sort(c,c+cn);
 55     int res=0,i=0,j=cn-1;
 56     while(i<j){
 57         while(i<j && c[i]+c[j]>k) --j;
 58         res+=j-i;
 59         ++i;
 60     }
 61     return res;
 62 }
 63 
 64 void conquer(int u){
 65     an=0; a[an++]=0;
 66     for(int i=head[u]; i!=-1; i=edge[i].next){
 67         int v=edge[i].v;
 68         if(vis[v]) continue;
 69         bn=0;
 70         dfs(v,u,edge[i].w);
 71         ans-=count(b,bn);
 72     }
 73     ans+=count(a,an);
 74 }
 75 void divide(int u){
 76     getSize(u,u); minimum=INF; getCentre(u,u,size[u]);
 77     u=centre;
 78     vis[u]=1;
 79     conquer(u);
 80     for(int i=head[u]; i!=-1; i=edge[i].next){
 81         int v=edge[i].v;
 82         if(vis[v]) continue;
 83         divide(v);
 84     }
 85 }
 86 
 87 int main(){
 88     int a,b,c;
 89     while(scanf("%d%d",&n,&k),(n||k)){
 90         NE=0;
 91         memset(head,-1,sizeof(head));
 92         for(int i=1; i<n; ++i){
 93             scanf("%d%d%d",&a,&b,&c);
 94             addEdge(a,b,c); addEdge(b,a,c);
 95         }
 96         ans=0;
 97         memset(vis,0,sizeof(vis));
 98         divide(1);
 99         printf("%d\n",ans);
100     }
101     return 0;
102 }

 

标签：

相关文章