[点分治系列] 静态点分
2019-11-18杂谈搜奇网59°c
A+ A-没错...我就是要讲点分治。这个东西底本学过的,当时学得不好...本日模仿赛又考这个东西效果写不出来。
因而博主特地又去学了学这个东西,此次相对要搞懂了...【复赛倒计时:11天】
——正片最先——
点分是一个用来处理树上途径问题、间隔问题的算法。说直接点实在就是分治头脑在树上的表现和运用。
起首是分治的要领,既然是树上问题,天然就是对树举行分治。
我们关于一棵树,选定一个点作为它的根,将这个点与其子树拆开,然后对它的子树也举行雷同的操纵,然后应用子树统计答案。一般来说,点分更像一种头脑,而不是一个算法,固然你也能够把它当算法来学。
关于怎样选根来分树,其他dalao的博客已讲得异常清晰仔细了,每次选定一棵树的重心,然后分它,如许能够做到
O(nlogn)的优异时候复杂度。
关于求重心,做法就是一个size统计。
这里照样引见一下吧(许多博客都只贴一个代码...):
关于一个节点x,若我们把其删除,本来的树就会变成多少部份,我们设maxsubtree(x)示意删除x后剩下的最大子树的大小,若我们找到一个x,使得maxsubtree(x)最小,x就是这棵树的重心。
给出求重心的代码:
void getroot(int x,int fa){ siz[x]=1;son[x]=0; for(int i=head[x];i;i=nxt(i)){ int y=to(i); if(y==fa||vis[y])continue; getroot(y,x); siz[x]+=siz[y]; if(siz[y]>son[x])son[x]=siz[y]; } if(Siz-siz[x]>son[x])son[x]=Siz-siz[x]; if(son[x]<maxx)maxx=son[x],root=x; }
因而我们就晓得怎样拆树了,背面的东西就不难了。
update: 19.11.5 关于上面的代码加一些诠释,Siz示意当前在求重心的这一棵树的大小,root用来纪录重心
我们来说怎样统计信息
起首我们要统计与每一次找到的重心有关的途径,我们用dis[x]示意目标点(重心)到x的间隔。
给出getdis的代码:
void getdis(int x,int fa,int d){//d示意x到目标点的间隔 dis[++top]=d;//我们只须要晓得每个点到目标点的间隔就行,不必晓得这个点是哪一个 for(int i=head[x];i;i=nxt(i)){ int y=to(i); if(y==fa||vis[y])continue; getdis(y,x,d+val(i)); } }
有了dis数组后,我们就能够很轻松的取得途径的长度了。
比方,我们已知x到重心的间隔是m,y到重心的间隔是n,那x到y的间隔就是m+n,能够仔细的读者已发明锅了。
假如x到y的途径都在一棵子树内,我们就会有一段间隔被反复盘算了,如许我们获得的途径就是不对的。
给一张图邃晓一下:
如图,蓝色的代表x到重心的途径,赤色的代表y到重心的途径,我们能够获得dis[x]=3,dis[y]=2。
假如根据前面说的盘算体式格局,x到y的途径长度应该是5了,然则并非,我们的途径长度是3。
缘由就是,绿色的那一段,我们根本不走,我们不经由它。
因而我们要处理这类不正当途径。晓得一切途径,又晓得不正当途径,应用容斥道理,我们能够获得:
正当途径=一切途径 - 不正当途径。
如许我们divide的代码就出来了:
void divide(int x){ vis[x]=1;//保证我们每次divide的x都是当前这棵树的重心,所以标记x已divide过了 solve(x,0,1);//盘算这棵树以x为重心的一切途径答案 int totsiz=Siz;//这棵树的大小 for(int i=head[x];i;i=nxt(i)){ int y=to(i); if(vis[y])continue; solve(y,val(i),0);//求不正当途径 maxx=inf,root=0;//初始化 Siz=siz[y]>siz[x]?totsiz-siz[x]:siz[y];//更新siz getroot(y,x);//求出以y为根的子树 divide(root);//以y为根的子树分治下去 } }
我们看一看去除不正当途径的代码:
solve(y,val(i),-1);
思索发明:
一切不正当途径都是在统一棵子树中的途径,我们要减去它。
先往下看完solve再回来看这里。
我们进入到solve中,起首是getdis,以x为目标点猎取dis。然则我们要猎取的是间隔为val(i)的dis。
这就使得dis[y]=val(i),所以以y为根的子树中的一切dis值就即是dis[y]+它们到y的间隔,然后由于dis[y]是x到y的间隔,
所以我们就求出了以y为根的子树中一切点到x的间隔。
现实一点的邃晓就是,y到目标点的间隔是dis[y]=val(i),y的子树中的点到x的间隔就是它们到y的间隔+dis[y],所以跑一遍能够求出y的子树中一切点到x的间隔。
然后就是solve函数了:
我们这里的solve以模板题:【模板】点分治1 为例,差别问题我们solve的东西差别。
起首一定能够想到一个O(n^2)的做法的,确切能够水过去这一题。
然则我毕竟是在写博客...所以,O(nlogn)做法送上...
我们这么想,我们须要统计途径长为k的点对个数,那我们只需肯定了一个点x,另一个点的dis[y]就应该是k-dis[x],我们只须要二分找k-dis[x]就好了。
void solve(int x,int d,int avl){//avl(available)示意此次盘算获得的答案是不是正当 top=0;//清空dis数组 getdis(x,0,d);//猎取到当前这棵树到x的间隔为d的一切dis int cnt=0; sort(dis+1,dis+top+1);//排好序预备二分 dis[0]=-1;//第一个dis设置为新鲜的数轻易下面比较 for(int i=1;i<=top;i++){//把一切间隔雷同的点放进一个桶内里轻易操纵 if(dis[i]==dis[i-1]) bucket[cnt].amount++;//本来桶的个数+1 else bucket[++cnt].dis=dis[i],bucket[cnt].amount=1;//新开一个桶 } for(int i=1;i<=m;i++){ if(query[i]%2==0)//假如k是偶数的话,我们零丁斟酌一下间隔为k/2那些点,它们能够相互配对形生长为k的途径 for(int j=1;j<=cnt;j++) if(bucket[j].dis==query[i]/2)//假如间隔是k/2 ans[i]+=(bucket[j].amount-1)*bucket[j].amount/2*avl; //组合计数,假定我们有x个间隔为k/2的点,就有(x-1)*x/2个点对间隔为k,也就是我们能够配出这么多个差别点对 //实在就是C(x,2)->x!/((x-2)!*2)->(x-1)*x/2 for(int j=1;j<=cnt&&bucket[j].dis<query[i]/2;j++){
//接着罗列<k/2的间隔,然后我们二分找>2的间隔配对,防止反复(点对(u,v)和(v,u)是等价的),即是k/2的我们前面算过了,所以一切状况都斟酌到了 int l=j+1,r=cnt; while(l<=r){ int mid=(l++r)>>1; if(bucket[j].dis+bucket[mid].dis==query[i]){ ans[i]+=bucket[j].amount*bucket[mid].amount*avl; //组合计数纪录答案,假定我们有x个间隔为m的点,y个间隔为k-m的点,我们就有x*y个差别的点对(分类相乘) break;//这一轮二分完了,下一轮 } if(bucket[j].dis+bucket[mid].dis>query[i])r=mid-1;//大了,往小的二分 else l=mid+1;//小了,往大的二分 } } } }
这么细致都看不懂我就教不了了...
接下来就给出一切代码吧...(我晓得你们只想看这个/doge)
#include<bits/stdc++.h> #define N 100010 #define lint long long #define inf 0x7fffffff using namespace std; int vis[N],son[N],Siz,maxx,siz[N]; int root,head[N],tot,n,m,dis[N],top,query[N],ans[N]; lint k; struct Bucket{ int dis,amount; }bucket[N]; struct Edge{ int nxt,to,val; #define nxt(x) e[x].nxt #define to(x) e[x].to #define val(x) e[x].val }e[N<<1]; inline int read(){ int data=0,w=1;char ch=0; while(ch!='-' && (ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')w=-1,ch=getchar(); while(ch>='0' && ch<='9')data=data*10+ch-'0',ch=getchar(); return data*w; } inline void addedge(int f,int t,int val){ nxt(++tot)=head[f];to(tot)=t;val(tot)=val;head[f]=tot; } void getroot(int x,int fa){ siz[x]=1;son[x]=0; for(int i=head[x];i;i=nxt(i)){ int y=to(i); if(y==fa||vis[y])continue; getroot(y,x); siz[x]+=siz[y]; if(siz[y]>son[x])son[x]=siz[y]; } if(Siz-siz[x]>son[x])son[x]=Siz-siz[x]; if(son[x]<maxx)maxx=son[x],root=x; } void getdis(int x,int fa,int d){ dis[++top]=d; for(int i=head[x];i;i=nxt(i)){ int y=to(i); if(y==fa||vis[y])continue; getdis(y,x,d+val(i)); } } void solve(int rt,int d,int avl){//avl(available)示意此次盘算获得的答案是不是正当 top=0;//清空dis数组 getdis(rt,0,d);//猎取到当前这棵树的rt的间隔为d的一切dis int cnt=0; sort(dis+1,dis+top+1);//排好序预备二分 dis[0]=-1;//第一个dis设置为新鲜的数轻易下面比较 for(int i=1;i<=top;i++){//把一切间隔雷同的点放进一个桶内里轻易操纵 if(dis[i]==dis[i-1]) bucket[cnt].amount++;//本来桶的个数+1 else bucket[++cnt].dis=dis[i],bucket[cnt].amount=1;//新开一个桶 } for(int i=1;i<=m;i++){ if(query[i]%2==0)//假如k是偶数的话,我们零丁斟酌一下间隔为k/2那些点,它们能够相互配对形生长为k的途径 for(int j=1;j<=cnt;j++) if(bucket[j].dis==query[i]/2)//假如间隔是k/2 ans[i]+=(bucket[j].amount-1)*bucket[j].amount/2*avl; //组合计数,假定我们有x个间隔为k/2的点,就有(x-1)*x/2个点对间隔为k,也就是我们能够配出这么多个差别点对 //实在就是C(x,2)->x!/((x-2)!*2)->(x-1)*x/2 for(int j=1;j<=cnt&&bucket[j].dis<query[i]/2;j++){//接着罗列<k/2的间隔,然后我们二分找>2的间隔配对 int l=j+1,r=cnt; while(l<=r){ int mid=(l+r)>>1; if(bucket[j].dis+bucket[mid].dis==query[i]){ ans[i]+=bucket[j].amount*bucket[mid].amount*avl; //组合计数纪录答案,假定我们有x个间隔为m的点,y个间隔为k-m的点,我们就有x*y个差别的点对(分类相乘) break;//这一轮二分完了,下一轮 } if(bucket[j].dis+bucket[mid].dis>query[i])r=mid-1;//大了,往小的二分 else l=mid+1;//小了,往大的二分 } } } } void divide(int x){ vis[x]=1; solve(x,0,1);//正当的算进去 int totsiz=Siz; for(int i=head[x];i;i=nxt(i)){ int y=to(i); if(vis[y])continue; solve(y,val(i),-1);//不正当的算出来减掉 maxx=inf,root=0; Siz=siz[y]>siz[x]?totsiz-siz[x]:siz[y]; getroot(y,x); divide(root); } } int main(){ n=read();m=read(); for(int i=1;i<n;i++){ int x=read(),y=read(),z=read(); addedge(x,y,z);addedge(y,x,z); } for(int i=1;i<=m;i++)query[i]=read(); maxx=inf;root=0;Siz=n; getroot(1,0); divide(root); for(int i=1;i<=m;i++){ if(ans[i]>0)puts("AYE"); else puts("NAY"); } return 0; }
这份代码不仅求出了是不是有途径长为k的答案存在,还求出了途径长为k的点对个数。
不须请求个数的话你就改一改solve,如许常数会小一点,跑得更快,然则这一题我更想给你们讲讲思绪,学会闻一知十...末了照样那句话,我个人并不认为点分是一种算法,它更多表现的是分治的头脑在树上的运用。
实在你会发明,许多高端的数据结构、算法之类的,都是由基本的算法头脑衍生出来的泛用性更强的东西。
懂了基本的算法头脑,你不只能够轻松的学会种种高阶算法,以至能够本身造出解题的算法。
比方图论内里的dijkstra最短路算法,不就是贪婪吗?再比方线段树,不就是分治吗?
一些看起来很高等,听起来很难的东西,只需你弄邃晓了个中的实质,你在叹息发明者的伶俐同时,本身也就收成到了个中包含的学问和基本头脑的运用要领。进修不是死学...只要弄邃晓了它的事情道理和体式格局,你才算是控制了它,仅仅是能够用它来做题,那问题变变形,你就一脸懵了。