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

点分治&动态点分治

数据结构

作业部落

评论地址

点分治

一、板子

鉴于没有人会看我的博客学习点分治，所以就不详细解说算法了，提供一个板子逼着自己背下来
板子：[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.路径点权之积的字典序最小点对

动态点分治

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

题单

点分治

动态点分治

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