点分治

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

传送门（洛谷）

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

ContractedBlock.gif ExpandedBlockStart.gif

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

有注释讲解版

ContractedBlock.gif ExpandedBlockStart.gif

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

无注释纯洁版

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

发表评论

表情：
评论列表 （有 0 条评论，453人围观）

还没有评论，来说两句吧...

相关阅读

    相关 点分治-模板

    可能一步步克服恐惧的过程就是成功，所以只管面对恐惧，不思考结果， 24分钟敲模板，这是点分治第一次敲的这么顺利，纪念一下。 洛谷：2634.求距离是三的倍数的点对数

    ﹏ヽ暗。殇╰゛Y﹏ヽ暗。殇╰゛Y/ 0 赞/ 144 阅读

    相关 点分治初步

    　　点分治是一种常用于处理树上点对关系的分治算法。   一、算法介绍 　　提到点分治，我们先来看一道例题：[洛谷P3806 【模板】点分治1][P3806 _1]

    ﹏ヽ暗。殇╰゛Y﹏ヽ暗。殇╰゛Y/ 0 赞/ 335 阅读

    相关 （点）分治学习笔记

    哗我看了一下好像没有很详细专门讲分治的blog？那就主要先学一下点分治吧，其他的……等我记得把C++一本通带到机房来再说吧先咕着啦 > 写在前面 > > 刷题进度 > >

    迷南。迷南。/ 0 赞/ 393 阅读

    相关 点分治

      [传送门][Link 1]（洛谷） UPDATE:关于代码中时间复杂度的更正——在代码中每一次都要通过遍历一遍询问来得到答案，所以时间复杂度是O(NMlogN), !

    - 日理万妓- 日理万妓/ 0 赞/ 454 阅读

    相关 Codeforces 1101D 点分治

    题意：有一颗树，每个点有一个点权，边权都是1，问路径上的所有点的gcd不是1的最长路径是多少？ 思路：之前补这道题的时候，用分解质因数 + 树形DP做的，其实用点分治可以更暴

    Myth丶恋晨Myth丶恋晨/ 0 赞/ 343 阅读

    相关 [笔记]点分治

    基本思路：点分治，是一种针对可带权树上简单路径统计问题的算法。对于一个节点，只解决经过这棵子树的根节点的路径，对于子节点问题下推子树。 //当初的主要问题是vis[]

    ゝ一纸荒年。ゝ一纸荒年。/ 0 赞/ 420 阅读

    相关 点分治学习笔记

    点分治 关于点分治，其实思想是非常好理解的，类比在数列上或是在平面上的分治算法（如归并排序，平面最近点对等），我们可以从字面上理解该算法： > 以一个点为界限，将一棵树

    秒速五厘米秒速五厘米/ 0 赞/ 394 阅读