首页 > 代码库 > 关于点分治的理解
关于点分治的理解
【引言】
由于树具有一般的图没有的特点，所以在竞赛中的应用更广。
在一些树上路径问题中，暴力求解时间复杂度过高，往往需要一些更为高效的算法，点分治就是其中之一。
【流程】
1、首先选取一个点，把无根树变成有根树。
那么如何选点呢？ ——树型动规
因为树是递归定义的，所以我们当然希望递归的层数最小。
每次选取的点，要保证与此点相连的结点数最多的连通块的结点数最小，我们把这个点叫做“重心”。
那么找到一颗树的重心有以下算法：
（1）dfs一次，算出以每个点为根的子树大小。
（2）记录以每个结点为根的最大子树的大小。
（3）判断：如果以当前结点为根的最大子树大小比当前根更优，更新当前根。
1 void getroot(int x,int fa)//x表示当前结点，fa表示x的父结点 2 { 3 son[x]=1;F[x]=0;//F数组记录以x为根的最大子树的大小 4 for(int i=Link[x];i;i=e[i].next) 5 if(e[i].y!=fa&&!vis[e[i].y])//避免陷入死循环 6 { 7 getroot(e[i].y,x);//得到子结点信息 8 son[x]+=son[e[i].y];//计算x结点大小 9 F[x]=max(F[x],son[e[i].y]);//更新F数组10 }11 F[x]=max(F[x],sum-son[x]);//sum表示当前树的大小，因为以x为根的情况还要考虑以x的父亲为根的子树大小。12 if(F[x]<F[root])root=x;//更新当前根13 }
2、处理联通块中通过根结点的路径。
3、标记根结点（相当于处理过后，将根结点从子树中删除）。
4、递归处理以当前点的儿子为根的每棵子树。
【算法框架】
1 int solve(int x) 2 { 3 vis[x]=1;//将当前点标记 4 for(int i=Link[x];i;i=e[i].next) 5 if(!vis[e[i].y]) 6 { 7 root=0;//初始化根 8 sum=e[i].y;//初始化sum 9 getroot(x,0);//找连通块的根10 solve(e[i].y);//递归处理下一个连通块11 }12 }13 int main()14 {15 build();//建树16 sum=f[0]=n;//初始化sum和f[0]17 root=0;//初始化root18 getroot(1,0);//找根19 solve(root);//点分治20 }
【例题1】【poj1741】tree
给一颗n个节点的树，每条边上有一个距离v（v<=1000）。定义d(u,v)为u到v的最小距离。给定k值，求有多少点对（u，v）使u到v的距离小于等于k。数据范围：n<=10000,k<2^31
计算答案的方法：这个点延伸出的几棵子树各做一次dfs，记录子树中出现的距离值，对于一棵树的距离值数组，把它排序求一次ans1，再对每棵子树分别求一个自己对自己的ans2，ans1-Σans2即为最后的ans。
参考代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<ctime> 7 #include<algorithm> 8 using namespace std; 9 #define INF 0x7fffffff10 struct node{int y,v,next;}e[20010];11 int n,len,k,root,sum,ans,Link[10010],f[10010],vis[10010],son[10010],d[10010],deep[10010];12 inline int read()13 {14 int x=0,f=1; char ch=getchar();15 while(!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();}16 while(isdigit(ch)) {x=x*10+ch-‘0‘; ch=getchar();}17 return x*f;18 }19 void insert(int x,int y,int v)20 {21 e[++len].next=Link[x];22 Link[x]=len;23 e[len].v=v;24 e[len].y=y;25 }26 void getroot(int x,int fa)27 {28 son[x]=1; f[x]=0;29 for(int i=Link[x];i;i=e[i].next)30 {31 if(e[i].y==fa||vis[e[i].y]) continue;32 getroot(e[i].y,x);33 son[x]+=son[e[i].y];34 f[x]=max(f[x],son[e[i].y]);35 }36 f[x]=max(f[x],sum-son[x]);37 if(f[x]<f[root]) root=x;38 }39 void getdeep(int x,int fa)40 {41 deep[++deep[0]]=d[x];42 for(int i=Link[x];i;i=e[i].next)43 {44 if(e[i].y==fa||vis[e[i].y]) continue;45 d[e[i].y]=d[x]+e[i].v;46 getdeep(e[i].y,x);47 }48 }49 int cal(int x,int v)50 {51 d[x]=v; deep[0]=0;52 getdeep(x,0);53 sort(deep+1,deep+deep[0]+1);54 int l=1,r=deep[0],sum=0;55 while(l<r)56 {57 if(deep[l]+deep[r]<=k) {sum+=r-l; l++;}58 else r--;59 }60 return sum;61 }62 void solve(int x)63 {64 ans+=cal(x,0);//计算答案65 vis[x]=1;66 for(int i=Link[x];i;i=e[i].next)67 {68 if(vis[e[i].y]) continue;69 ans-=cal(e[i].y,e[i].v);//计算不符合题意的答案70 sum=son[e[i].y];71 root=0;72 getroot(e[i].y,0);73 solve(root);74 }75 }76 int main()77 {78 freopen("cin.in","r",stdin);79 freopen("cout.out","w",stdout);80 while(1)81 {82 ans=0,root=0,len=0;83 memset(vis,0,sizeof(vis));84 memset(Link,0,sizeof(Link));85 n=read(); k=read();86 if(n==0&&k==0) break;87 for(int i=1;i<=n-1;i++)88 {89 int x=read(),y=read(),v=read();90 insert(x,y,v); insert(y,x,v);91 }92 f[0]=INF; sum=n;93 getroot(1,0);94 solve(root);95 printf("%d\n",ans);96 }97 return 0;98 }
【例题2】【bzoj2152】聪聪可可
聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。
计算答案的方法：与上一题类似，在计算路径长度时对3取模，用t[0],t[1],t[2]分别记录模为0、1、2的情况，那么显然答案就是t[1]*t[2]*2+t[0]*t[0]
参考代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<ctime> 7 #include<algorithm> 8 using namespace std; 9 #define MAXN 2001010 struct node{int y,v,next;}e[MAXN*2];11 int n,len,root,sum,ans,t[5],Link[MAXN],f[MAXN],vis[MAXN],son[MAXN],d[MAXN];12 inline int read()13 {14 int x=0,f=1; char ch=getchar();15 while(!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();}16 while(isdigit(ch)) {x=x*10+ch-‘0‘; ch=getchar();}17 return x*f;18 }19 int gcd(int a,int b) {return b==0?a:gcd(b,a%b);}20 void insert(int x,int y,int v)21 {22 e[++len].next=Link[x];23 Link[x]=len;24 e[len].y=y;25 e[len].v=v;26 }27 void getroot(int x,int fa)28 {29 son[x]=1; f[x]=0;30 for(int i=Link[x];i;i=e[i].next)31 {32 if(e[i].y==fa||vis[e[i].y]) continue;33 getroot(e[i].y,x);34 son[x]+=son[e[i].y];35 f[x]=max(f[x],son[e[i].y]);36 }37 f[x]=max(f[x],sum-son[x]);38 if(f[x]<f[root]) root=x;39 }40 void getdeep(int x,int fa)41 {42 t[d[x]]++;43 for(int i=Link[x];i;i=e[i].next)44 {45 if(e[i].y==fa||vis[e[i].y]) continue;46 d[e[i].y]=(d[x]+e[i].v)%3;47 getdeep(e[i].y,x);48 }49 }50 int cal(int x,int v)51 {52 t[0]=t[1]=t[2]=0; d[x]=v;53 getdeep(x,0);54 return t[1]*t[2]*2+t[0]*t[0];55 }56 void solve(int x)57 {58 ans+=cal(x,0); vis[x]=1;59 for(int i=Link[x];i;i=e[i].next)60 {61 if(vis[e[i].y]) continue;62 ans-=cal(e[i].y,e[i].v);63 root=0; sum=son[e[i].y];64 getroot(e[i].y,0);65 solve(root);66 }67 }68 int main()69 {70 //freopen("cin.in","r",stdin);71 //freopen("cout.out","w",stdout);72 n=read();73 for(int i=1;i<n;i++)74 {75 int x=read(),y=read(),v=read()%3;76 insert(x,y,v); insert(y,x,v);77 }78 sum=n; f[0]=n;79 getroot(1,0);80 solve(root);81 int t=gcd(ans,n*n);82 printf("%d/%d\n",ans/t,n*n/t);83 return 0;84 }
【例题3】【bzoj2599】Race
给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.数据范围：N<=200000, K<=1000000
我的做法：开一个100W的数组t,t[i]表示权值为i的路径最少边数
找到重心分成若干子树后， 得出一棵子树的所有点到根的权值和x，到根a条边，用t[k-x]+a更新答案，全部查询完后
然后再用所有a更新t[x]
这样可以保证不出现点分治中的不合法情况
把一棵树的所有子树搞完后再遍历所有子树恢复T数组，如果用memset应该会比较慢
参考代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<ctime> 7 #include<algorithm> 8 using namespace std; 9 #define MAXN 200100 10 #define INF 1000000000 11 struct node{int y,next,v;}e[MAXN*2]; 12 int n,m,len,root,sum,ans,Link[MAXN],son[MAXN],vis[MAXN],t[MAXN*5],dis[MAXN],d[MAXN],f[MAXN]; 13 char buf[1<<15],*fs,*ft; 14 inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin)),fs==ft)?0:*fs++;} 15 inline int read() 16 { 17 int x=0,f=1; char ch=getc(); 18 while(!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getc();} 19 while(isdigit(ch)) {x=x*10+ch-‘0‘; ch=getc();} 20 return x*f; 21 } 22 void insert(int x,int y,int v){e[++len].next=Link[x]; Link[x]=len; e[len].y=y; e[len].v=v;} 23 void getroot(int x,int fa) 24 { 25 int ff=1; son[x]=1; 26 for(int i=Link[x];i;i=e[i].next) 27 if(e[i].y!=fa&&!vis[e[i].y]) 28 { 29 getroot(e[i].y,x); 30 son[x]+=son[e[i].y]; 31 if(son[e[i].y]>sum/2) ff=0; 32 } 33 if(sum-son[x]>sum/2) ff=0; 34 if(ff) root=x; 35 } 36 /*void getroot(int x,int fa) 37 { 38 son[x]=1;f[x]=0; 39 for(int i=Link[x];i;i=e[i].next) 40 if(e[i].y!=fa&&!vis[e[i].y]) 41 { 42 getroot(e[i].y,x); 43 son[x]+=son[e[i].y]; 44 f[x]=max(f[x],son[e[i].y]); 45 } 46 f[x]=max(f[x],sum-son[x]); 47 if(f[x]<f[root])root=x; 48 }*/ 49 void cal(int x,int fa) 50 { 51 if(dis[x]<=m) ans=min(ans,d[x]+t[m-dis[x]]); 52 for(int i=Link[x];i;i=e[i].next) 53 if(e[i].y!=fa&&!vis[e[i].y]) 54 { 55 d[e[i].y]=d[x]+1; 56 dis[e[i].y]=dis[x]+e[i].v; 57 cal(e[i].y,x); 58 } 59 } 60 void add(int x,int fa,int flag) 61 { 62 if(dis[x]<=m) 63 { 64 if(flag) t[dis[x]]=min(t[dis[x]],d[x]); 65 else t[dis[x]]=INF; 66 } 67 for(int i=Link[x];i;i=e[i].next) 68 if(e[i].y!=fa&&!vis[e[i].y]) 69 add(e[i].y,x,flag); 70 } 71 void work(int x) 72 { 73 vis[x]=1; t[0]=0; 74 for(int i=Link[x];i;i=e[i].next) 75 if(!vis[e[i].y]) 76 { 77 d[e[i].y]=1; dis[e[i].y]=e[i].v; 78 cal(e[i].y,0); 79 add(e[i].y,0,1); 80 } 81 for(int i=Link[x];i;i=e[i].next) 82 if(!vis[e[i].y]) add(e[i].y,0,0); 83 for(int i=Link[x];i;i=e[i].next) 84 if(!vis[e[i].y]) 85 { 86 sum=son[e[i].y]; root=0; 87 getroot(e[i].y,0); 88 work(e[i].y); 89 } 90 } 91 int main() 92 { 93 //freopen("cin.in","r",stdin); 94 //freopen("cout.out","w",stdout); 95 n=read(); m=read(); 96 for(int i=1;i<=m;i++)t[i]=n; 97 for(int i=1;i<n;i++) 98 { 99 int x=read(),y=read(),v=read();100 x++; y++;101 insert(x,y,v); insert(y,x,v);102 }103 sum=ans=f[0]=n;104 getroot(1,0);105 work(root);106 if(ans==n) printf("-1\n");107 else printf("%d\n",ans);108 return 0;109 }
关于点分治的理解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。