[关闭]
@xzyxzy 2018-08-17T11:01:39.000000Z 字数 1587 阅读 1443

点分治&动态点分治

数据结构

作业部落

评论地址


点分治

一、板子

鉴于没有人会看我的博客学习点分治,所以就不详细解说算法了,提供一个板子逼着自己背下来
板子:[luogu3806]【模板】点分治1

求树上是否存在距离为的路径,多组询问

点分治支持以下函数
Getroot Getdis Calc solve

1.找重心

  1. void Getroot(int x,int fa)
  2. {
  3. siz[x]=1;mx[x]=0;
  4. for(int i=head[x];~i;i=a[i].next)
  5. {
  6. int R=a[i].to;
  7. if(R==fa||vis[R]) continue;
  8. Getroot(R,x);
  9. siz[x]+=siz[R];
  10. mx[x]=max(mx[x],siz[R]);
  11. }
  12. mx[x]=max(mx[x],sum-siz[x]);
  13. if(mx[x]<mx[root]) root=x;
  14. }

2.把树上距离存进临时数组

  1. void Getdis(int x,int fa)
  2. {
  3. dis[++cnt]=dep[x];
  4. for(int i=head[x];~i;i=a[i].next)
  5. {
  6. int R=a[i].to;
  7. if(vis[R]||R==fa) continue;
  8. dep[R]=dep[x]+a[i].w;
  9. Getdis(R,x);
  10. }
  11. }

3.点分治不同题的区别就在于Calc函数

  1. void Calc(int x,int d,int op)
  2. {
  3. cnt=0;
  4. dep[x]=d;
  5. Getdis(x,0);
  6. sort(dis+1,dis+cnt+1);
  7. for(int i=1;i<=M;i++)
  8. {
  9. int l=1,r=cnt;
  10. while(l<r)
  11. if(dis[l]+dis[r]>K[i]) r--;
  12. else
  13. {
  14. if(dis[l]+dis[r]==K[i])
  15. for(int k=r;dis[k]==dis[r]&&k>=l;k--)
  16. Yes[i]+=op;
  17. l++;
  18. }
  19. }
  20. }

4.递归计算,分层找重心

  1. void Solve(int x)
  2. {
  3. Calc(x,0,1);
  4. vis[x]=1;int tt=sum;
  5. for(int i=head[x];~i;i=a[i].next)
  6. {
  7. int R=a[i].to;
  8. if(vis[R]) continue;
  9. Calc(R,a[i].w,-1);
  10. sum=siz[R]>siz[x]?tt-siz[x]:siz[R];//siz要注意了————Cwen
  11. root=0;
  12. Getroot(R,x);Solve(root);
  13. }
  14. }

5.函数中的调用

  1. int main()
  2. {
  3. root=0;mx[0]=sum=N;
  4. Getroot(1,0);Solve(root);
  5. }

注意有些题不能容斥

二、用处

在我所做过的题中,他可以用来求解树上路径问题
1.长为(小于)的路径条数(以及这条路径的最少边数)
2.长为三的倍数的路径条数
3.路径点权之积的字典序最小点对

动态点分治

区别在于递归时要记录上级重心,由此产生的父子关系构成点分树
于是在点分树上维护很多很多东西就可以支持动态修改了
大家看看这题-幻想乡战略游戏(动态维护带权重心)

题单

点分治

动态点分治

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注