点分治

- 日理万妓 2021-12-13 05:04 306阅读 0赞

[传送门][Link 1]（洛谷）

UPDATE:关于代码中时间复杂度的更正——在代码中每一次都要通过遍历一遍询问来得到答案，所以时间复杂度是O(NMlogN),

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //代码详解：最后会放出没有注释的纯净版
      2 #include<iostream>
      3 #include<cstdio>
      4 using namespace std;
      5 /*
      6     点（淀）分（粉）治（质）
      7     按照分治的思想对一个大问题瓜分成几个小问题，然后通过对子问题的求解
      8     以及对子问题合并的方式，得到最后all of the question's answers
      9     这个模板根据洛谷的点分治的模板题写的，原题是一道经典的关于树的点分治 
     10     前置姿势：
     11     1.图论基本常识
     12     2.树的相关内容
     13     3.求树的重心
     14     4.简单的分治的思想（可参考归并排序）
     15 */
     16 
     17 /*
     18     接下来就是针对这道模板题的一个分析了
     19     原题意：给定一棵有n个点的树，询问树上距离为k的点对是否存在。
     20     首先，每个结果都是满足可加性的，即在某个区间里成立的点对，放在整个范围里也是成立的
     21     所以我们明显的想到了分治（并不）————把问题划分成子问题求解
     22     然后再分析具体的内容：
     23         1.没有规定根，为了计算方便，我们可以自己规定一个根——root
     24         2.树上两点间的距离，即为两点之间路径的长度，两点之间关系可仅分为在OR不在一个子树里，故而
     25           树上两点之间的路径就是经过root的与经过root子树中的root的路径，对于前者的距离，我们可用dis[x]+dis[y]
     26           对于后者，我们可以把这个问题放在root的子树里再分析，此时距离也会变为dis'[x]+dis'[y]
     27         3.对于子树的划分方式，由2.与点分治的合并可知，你分了多少子问题和你的时间复杂度是息息相关的
     28           所以我们应该找到一个比较完美的方法去划分层数，保证即使当树退化成一个链的时候，也可以是层数尽量的少
     29           所以此时经（前）验（人）告诉我们我们应该找树的重心。
     30           当找到树的重心时，即使是一条链，它最后的层数不会超过logn层
     31     此时，我们可知求此算法时间复杂度为O(NlogN)——>求两点间距离要扫整棵树N*分层数logN
     32 */
     33 
     34 namespace the_Death{
     35     inline int read(){
     36         int f=1,x=0;char c=getchar();
     37         while(c<'0'||c>'9'){
         if(c=='-') f=-1;c=getchar();}
     38         while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
     39         return f*x;
     40     }
     41     const int INF=1e7+10,maxn=100010;
     42     int head[maxn],rem[maxn],vis[maxn],judge[maxn];
     43     int maxp[maxn],size[maxn],dis[maxn],test[maxn];
     44     int ask[1010],sum,root,ans,q[maxn],n,m,tot,x,y,z;
     45     struct ziji{
         int ver,dis,nxt;}mn[maxn<<1];
     46     //sum->当前子树总节点数，size[i]->以x为根节点的子树大小
     47     //maxp[i]->删去i后的子树中，最大一颗的大小（求重心）
     48     //则树的重心就是maxp[]值最小的那个节点
     49     //rem[i]->当前子树中，i号节点到子树的root的距离
     50     //judge[i]->在子树中，是否有某个节点与该子树的root距离为i
     51     //ask[]->询问的记录,test[i]->标记第i个询问是否被满足
     52     //其余的都是与题目有关的基本变量以及存图用的常用变量
     53     #define ver(i) mn[i].ver
     54     #define dis(i) mn[i].dis
     55     #define nxt(i) mn[i].nxt
     56     inline void add(int x,int y,int z){
     57         ver(++tot)=y,nxt(tot)=head[x],
     58         head[x]=tot;dis(tot)=z;
     59     }
     60     inline void getroot(int x,int fa){
     61         //通过DP的方式得到树的重心。NOTICE：最好用DP方式去求树的重心
     62         size[x]=1,maxp[x]=0;
     63         for(register int i=head[x];i;i=nxt(i)){
     64             int y=ver(i);
     65             if(y==fa||vis[y]) continue;
     66             getroot(y,x);size[x]+=size[y];
     67             //递归得到子树大小再取和就是以x为根的树的大小
     68             maxp[x]=max(maxp[x],size[y]);
     69             //更新x的maxp[]
     70         }
     71         maxp[x]=max(maxp[x],sum-size[x]);
     72         if(maxp[x]<maxp[root]) root=x;
     73         //根据重心定义可知：重心就是使得划分出来的子树的最大节点数最小的位置
     74         //所以如果这个点可划分出来的最大点数比原本找到的最大点数小，x就为root
     75     }
     76     inline void getdis(int x,int fa){
     77         //找在子树中的距离
     78         rem[++rem[0]]=dis[x];
     79         //rem[0]相当于一个计数器，记录你到第几个节点了
     80         //废物利用.JPG(麻麻再也不用担心我分不清垃圾种类啦)
     81         for(register int i=head[x];i;i=nxt(i)){
     82             int y=ver(i);
     83             if(y==fa||vis[y]) continue;
     84             dis[y]=dis[x]+dis(i);getdis(y,x);
     85         }
     86     }
     87     inline void calc(int x){
     88         int p=0;//作为整个x为根的树中出现过的dis的计数
     89         for(register int i=head[x];i;i=nxt(i)){
     90             int y=ver(i);
     91             if(vis[y]) continue;
     92             rem[0]=0,dis[y]=dis(i);
     93             getdis(y,x);//找到每个子树之中的dis
     94             for(register int j=rem[0];j;j--)//遍历当前子树的dis
     95                 for(register int k=1;k<=m;++k)//遍历每一个询问
     96                     if(ask[k]>=rem[j])
     97                         test[k]|=judge[ask[k]-rem[j]];
     98                 //如果(ask[k]-rem[j])长的路径存在的话，就标记一下第k个询问
     99                 //rem[j]表示rem[j]长的路径肯定存在，你只要找另一半就可以了
    100             for(register int j=rem[0];j;j--)
    101                 q[++p]=rem[j],judge[rem[j]]=1;
    102             //保存一下出现的dis
    103         }
    104         for(register int i=1;i<=p;i++) judge[q[i]]=0;
    105         //每次处理完一棵树之后要清空。由于要清空次数太多，用memset会TLE
    106     }
    107     inline void solve(int x){
    108         vis[x]=judge[0]=1;calc(x);
    109         for(register int i=head[x];i;i=nxt(i)){
    110             //对每一个子树进行分治
    111             int y=ver(i);if(vis[y]) continue;
    112             sum=size[y];maxp[root=0]=INF;
    113             getroot(y,0);solve(root);
    114             //在子树中找重心并且递归处理
    115         }
    116     }
    117     int main(){
    118         n=read();m=read();
    119         for(register int i=1;i<n;i++){
    120             x=read();y=read();z=read();
    121             add(x,y,z);add(y,x,z);
    122         }
    123         for(register int i=1;i<=m;i++) ask[i]=read();
    124         //标记询问
    125         maxp[root]=sum=n;//标记首次的重心
    126         getroot(1,0);solve(root);
    127         for(register int i=1;i<=m;i++){
    128             if(test[i]) puts("AYE");
    129             else puts("NAY");
    130         }
    131         system("pause");
    132     }
    133 }
    134 int main(){
    135     the_Death::main();return 0;
    136 }

有注释讲解版

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<cstdio>
     3 using namespace std;
     4 namespace the_Death{
     5     inline int read(){
     6         int f=1,x=0;char c=getchar();
     7         while(c<'0'||c>'9'){
         if(c=='-') f=-1;c=getchar();}
     8         while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
     9         return f*x;
    10     }
    11     const int INF=1e7+10,maxn=100010;
    12     int head[maxn],rem[maxn],vis[maxn],judge[maxn];
    13     int maxp[maxn],size[maxn],dis[maxn],test[maxn];
    14     int ask[1010],sum,root,ans,q[maxn],n,m,tot,x,y,z;
    15     struct ziji{
         int ver,dis,nxt;}mn[maxn<<1];
    16     #define ver(i) mn[i].ver
    17     #define dis(i) mn[i].dis
    18     #define nxt(i) mn[i].nxt
    19     inline void add(int x,int y,int z){
    20         ver(++tot)=y,nxt(tot)=head[x],
    21         head[x]=tot;dis(tot)=z;
    22     }
    23     inline void getroot(int x,int fa){
    24         size[x]=1,maxp[x]=0;
    25         for(register int i=head[x];i;i=nxt(i)){
    26             int y=ver(i);
    27             if(y==fa||vis[y]) continue;
    28             getroot(y,x);size[x]+=size[y];
    29             maxp[x]=max(maxp[x],size[y]);
    30         }
    31         maxp[x]=max(maxp[x],sum-size[x]);
    32         if(maxp[x]<maxp[root]) root=x;
    33     }
    34     inline void getdis(int x,int fa){
    35         rem[++rem[0]]=dis[x];
    36         for(register int i=head[x];i;i=nxt(i)){
    37             int y=ver(i);
    38             if(y==fa||vis[y]) continue;
    39             dis[y]=dis[x]+dis(i);getdis(y,x);
    40         }
    41     }
    42     inline void calc(int x){
    43         int p=0;
    44         for(register int i=head[x];i;i=nxt(i)){
    45             int y=ver(i);
    46             if(vis[y]) continue;
    47             rem[0]=0,dis[y]=dis(i);
    48             getdis(y,x);
    49             for(register int j=rem[0];j;j--)
    50                 for(register int k=1;k<=m;++k)
    51                     if(ask[k]>=rem[j])
    52                         test[k]|=judge[ask[k]-rem[j]];
    53             for(register int j=rem[0];j;j--)
    54                 q[++p]=rem[j],judge[rem[j]]=1;
    55          }
    56         for(register int i=1;i<=p;i++) judge[q[i]]=0;
    57     }
    58     inline void solve(int x){
    59         vis[x]=judge[0]=1;calc(x);
    60         for(register int i=head[x];i;i=nxt(i)){
    61             int y=ver(i);if(vis[y]) continue;
    62             sum=size[y];maxp[root=0]=INF;
    63             getroot(y,0);solve(root);
    64         }
    65     }
    66     int main(){
    67         n=read();m=read();
    68         for(register int i=1;i<n;i++){
    69             x=read();y=read();z=read();
    70             add(x,y,z);add(y,x,z);
    71         }
    72         for(register int i=1;i<=m;i++) ask[i]=read();
    73         maxp[root]=sum=n;
    74         getroot(1,0);solve(root);
    75         for(register int i=1;i<=m;i++){
    76             if(test[i]) puts("AYE");
    77             else puts("NAY");
    78         }
    79         system("pause");
    80     }
    81 }
    82 int main(){
    83     the_Death::main();return 0;
    84 }

无注释纯洁版

转载于:https://www.cnblogs.com/fallen-down/p/11173654.html

[Link 1]: https://www.luogu.org/problemnew/show/P3806
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211210/3b1045f11cf64c7f96f775ada3f0127d.png