[关闭]
@Junlier 2018-08-21T17:16:56.000000Z 字数 2501 阅读 2048

点分治

图论——点分治
嗯，蒟蒻我刚学的就记录一下
以洛谷的tree为模板讲解：洛谷题目传送门

树的重心

了解点分治之前，首先要知道什么是重心(要用到)
简单来说，就是子树最小的那个节点，我们需要O(n)地找到他来保证复杂度

  1. void get_root(rg int now,rg int fm)
  2. {
  3.     size[now]=1;rg int num=0;//size[]记录子树大小，num[]为当前的最大子树
  4.     for(rg int i=hd[now];i;i=ljl[i].nxt)//遍历
  5.     {
  6.         rg int qw=ljl[i].to;
  7.         if(qw==fm||vis[qw])continue;//先不管这个vis[]
  8.         get_root(qw,now);
  9.         size[now]+=size[qw];
  10.         num=max(num,size[qw]);
  11.     }
  12.     num=max(num,tot-size[now]);//tot是总点数
  13.                                //tot-size[now]是父亲那边(不是儿子)的“子树”大小
  14.     if(Max>num)Max=num,root=now;//是否更新
  15. }

个人认为这里还是比较简单的，自己画个图简单明了了

点分树

找到重心后把重心删掉，变成两个连通块，再分别找重心，把重心与之前找的重心相连边，不断递归建成一棵新树，就是点分树
&&优点：严格log层(不信自己验证)
这道题暂时不要用，但是是点分治的一个重要知识点……

点分治

首先了解几个特点(暂时不用理解，等下自然就懂)

  • 边建边算
  • 常见问题：
    1.是否存在……的路径
    2.满足……的路径有几条
  • 只要点分治之后的处理是线性的，那么总的复杂度一定是nlogn(只要你不瞎搞)

以tree这道题为例，找到一个重心就处理一定过重心的那条路径的答案，别问我为什么，反正这样是对的，而且时间优秀，不会算重//=_=
嗯，这里有点长了，不想写了，所以安利一波机房大佬的博客理解吧，一时半会真的讲不清，至少我问了很久才懂(主要是不想画图来讲解了，画图就很容易理解了)

YCB blog

code还是不少

  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<iomanip>
  7. #include<algorithm>
  8. #include<ctime>
  9. #include<queue>
  10. #include<stack>
  11. #include<vector>
  12. #define rg register
  13. #define il inline
  14. #define lst long long
  15. #define ldb long double
  16. #define N 40050
  17. using namespace std;
  18. const int Inf=1e9;
  20. int n,K,cnt,tot,ans;
  21. int Max,root,le,ri;
  22. struct EDGE{
  23.     int to,nxt,v;
  24. }ljl[N<<1];
  25. int hd[N];
  26. int size[N],vis[N];
  27. int Q[N],dis[N];
  29. il int read()
  30. {
  31.     rg int s=0,m=0;rg char ch=getchar();
  32.     while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
  33.     while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  34.     return m?-s:s;
  35. }
  37. il void add(rg int p,rg int q,rg int o)
  38. {
  39.     ljl[++cnt]=(EDGE){q,hd[p],o};hd[p]=cnt;
  40. }
  42. void get_root(rg int now,rg int fm)
  43. {
  44.     size[now]=1;rg int num=0;
  45.     for(rg int i=hd[now];i;i=ljl[i].nxt)
  46.     {
  47.         rg int qw=ljl[i].to;
  48.         if(qw==fm||vis[qw])continue;
  49.         get_root(qw,now);
  50.         size[now]+=size[qw];
  51.         num=max(num,size[qw]);
  52.     }
  53.     num=max(num,tot-size[now]);
  54.     if(Max>num)Max=num,root=now;
  55. }
  57. void get_dis(rg int now,rg int fm)
  58. {
  59.     Q[++ri]=dis[now];
  60.     for(rg int i=hd[now];i;i=ljl[i].nxt)
  61.     {
  62.         rg int qw=ljl[i].to;
  63.         if(vis[qw]||qw==fm)continue;
  64.         dis[qw]=dis[now]+ljl[i].v;
  65.         get_dis(qw,now);
  66.     }
  67. }
  69. il int Query(rg int now,rg int base)
  70. {
  71.     rg int res=0;
  72.     ri=0;dis[now]=base;
  73.     le=1;get_dis(now,0);
  74.     sort(Q+1,Q+ri+1);
  75.     while(le<=ri)
  76.     {
  77.         if(Q[le]+Q[ri]<=K)res+=ri-le,le++;
  78.         else ri--;
  79.     }
  80.     return res;
  81. }
  83. void divide(rg int now,rg int fm)
  84. {
  85.     ans+=Query(now,0);vis[now]=1;
  86.     rg int all=tot;
  87.     for(rg int i=hd[now];i;i=ljl[i].nxt)
  88.     {
  89.         rg int qw=ljl[i].to;
  90.         if(qw==fm||vis[qw])continue;
  91.         ans-=Query(qw,ljl[i].v);
  92.         tot=size[now]>size[qw]?size[qw]:all-size[qw];Max=Inf;
  93.         get_root(qw,0),divide(qw,0);
  94.     }
  95. }
  97. int main()
  98. {
  99.     n=read();
  100.     for(rg int i=1;i<n;++i)
  101.     {
  102.         rg int p=read(),q=read(),o=read();
  103.         add(p,q,o),add(q,p,o);
  104.     }
  105.     K=read();
  106.     tot=n,Max=Inf;
  107.     get_root(1,0);
  108.     divide(root,0);
  109.     printf("%d\n",ans);
  110.     return 0;
  111. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注