[关闭]
@XLM 2017-09-08T03:05:03.000000Z 字数 3500 阅读 324

树链剖分

学习 图论 树结构

为什么要有这个东西


总是有这样或者那样找事的题目
在题目里，我们要在树上不断地修改路径，查询路径
就算这是一棵树，如果不做任何处理，修改O(1)，查询O(depth(u)+depth(v))。
这种复杂度是我们无法承受的。

不如树剖

树剖是什么啊

树剖，就是树链剖分。顾名思义，就是将树以轻重链方式分开

Q：诶诶，分开干什么啊好好的树多可爱啊
A: 可爱可是不经cha啊

口述无凭，不如看道题
我们要搞事情(MC)啦(并不)

看完题回来了吗？如果你还不想MC想搞点更有意义滴事情你就往下看

不多说，都在酒代码里

  1. #include<cstdio>
  2. #include<cmath>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<algorithm>
  6. #include<vector>
  7. //#define XLM 
  8. using namespace std;
  9. const int maxn=10010;
  11. /*
  12.       树链剖分是通过将树上边通过不重不漏的方式hash到线段树上从而方便地进行查询的方法。
  13.       比如，我们想要查询x--y之间的路径上的边（当然，点也可以）的权值的最小值（或最大值），
  14.       这时候如果暴力的先求出LCA再按边查询，这样复杂度最坏便是O(depth[x]+depth[y])，复杂度远远超出一般要求(O(logn))
  15.       这时我们的想法便是：可不可以将一些边放到一起查询？
  16.       此时将树分为轻重链的树剖应运而生
  17.     */
  19. //树剖部分
  20. struct tree_edge{
  21.     int x,y,val;
  22.     void read(){
  23.         scanf("%d%d%d",&x,&y,&val);
  24.     }
  25. };
  26. tree_edge e[maxn];
  27.     //上面是用来存树边的结构体，用来方便对于每一条边的查询以及一会的建树
  29. vector <int> G[maxn];//存图
  31. int dep[maxn],id[maxn],son[maxn],val[maxn],top[maxn],siz[maxn],fa[maxn];
  32. //dep:每个节点的深度 id:即dfn—节点的dfs序 son:节点的重儿子的编号 fa:节点父节点的编号
  33. //val:存取关于节点的权值的信息以助于线段树查询 top:一条重链最上端的节点的编号
  34. //siz:以一个节点为根节点向下的子树的节点数
  36. void dfs_1(int u,int f,int depth){//第一次DFS，目的为了求出dep,siz,fa,son
  37.     dep[u]=depth;
  38.     siz[u]=1;
  39.     son[u]=0;
  40.     fa[u]=f;//记录当前节点状态
  41.     for (int i=0;i<G[u].size();i++){
  42.         int to=G[u][i];
  43.         if (to==f) continue;//保证不回头
  44.         dfs_1(to,u,depth+1);//递归查询子节点
  45.         siz[u]+=siz[to];
  46.         if (siz[son[u]]<siz[to]) son[u]=to;//重儿子就是儿子中siz数最大的儿子，因此枚举每一个儿子就找到了
  47.     }
  48. }
  50.     /*我们在树链剖分中，第一次的dfs是为了求出一个节点的位置信息和儿子父亲关系。经过第一次的dfs我们找出了重儿子，现在进行第二次dfs，用来找重链。
  51.      * 重链是什么？就是节点和其重儿子，重儿子的重儿子等……以及他们之间的边组成的链。我们把单独没有重儿子的叶子节点也叫做一条重链
  52.      * 这些重链能够保证每个节点都被其所覆盖，而且保证不重复覆盖
  53.      */
  55. int cnt=0;//dfs_clock
  56. void dfs_2(int u,int tp){//第二次dfs，目的求出top和id数组
  57.     top[u]=tp;
  58.     id[u]=++cnt;
  59.     if (son[u]) dfs_2(son[u],tp);//如果该节点有重儿子，证明该节点的重儿子与该节点在同一条重链上
  60.     for (int i=0;i<G[u].size();i++){//进行轻儿子(与重儿子相对)的访问，即访问处理一条新链
  61.         int to=G[u][i];
  62.         if (to==fa[u]||to==son[u]) continue;//防止走回头路以及访问到重儿子
  63.         dfs_2(to,to);
  64.     }
  65. }
  67. void init(int n){//预处理出边
  68.     for (int i=1;i<=n;i++){
  69.         if (dep[e[i].x] < dep[e[i].y]) swap(e[i].x,e[i].y);
  70.         val[id[e[i].x]]=e[i].val;
  71.     }
  72. }
  73. //那么为什么我们经过这样处理的边就能够通过线段树查询呢
  74. //首先，我们在DFS时采取了优先查询每一个点的重儿子，这让一条重链上的所有点的DFN必定是连续的
  75. //这样就产生了一个效果，就是说我们一条重链上的所有点的编号，都是连续的
  76. //既然你连续了，我就勉为其难的用线段树cha你好啦
  78. //线段树部分，此部分不再加叙述
  80. struct segment{
  81.     int l,r,val;
  82. };
  83. segment seg[4*maxn+10];
  85. void pushup(int x){
  86.     seg[x].val=max(seg[x<<1].val,seg[x<<1|1].val);
  87. }
  89. void build(int l,int r,int o){
  90.     seg[o].l=l,seg[o].r=r;
  91.     if (l==r){
  92.         seg[o].val=val[l];
  93.         return;
  94.     }
  95.     int mid=(l+r)>>1;
  96.     build(l,mid,o<<1);
  97.     build(mid+1,r,o<<1|1);
  98.     pushup(o);
  99. }
  101. void update(int pos,int x,int o){
  102.     int l=seg[o].l,r=seg[o].r;
  103.     if (l==r){
  104.         seg[o].val=x;
  105.         return;
  106.     }
  107.     int mid=(l+r)>>1;
  108.     if (pos<=mid) update(pos,x,o<<1);
  109.     if (pos>mid) update(pos,x,o<<1|1);
  110.     pushup(o);
  111. }
  113. int query(int L,int R,int o){
  114.     int l=seg[o].l,r=seg[o].r;
  115.     if (L<=l&&r<=R) return seg[o].val;
  116.     int ans=0,mid=(l+r)>>1;
  117.     if (L<=mid) ans=max(ans,query(L,R,o<<1));
  118.     if (R>mid) ans=max(ans,query(L,R,o<<1|1));
  119.     return ans;
  120. }
  122. void Clear(int n){
  123.     for (int i=1;i<=n;i++) G[i].clear();
  124. }
  126.     /*树链剖分的查询部分
  127.      * 我们现在有两个点查询他们之间的信息
  128.      * 因为他们之间的路径是唯一的(树的性质)，那我们不如查询u到LCA和v到LCA
  129.      */
  132. int Qtree(int u,int v){
  133.     int top_1=top[u],top_2=top[v];
  134.     int ans=0;
  135.     while (top_1!=top_2){
  136.         if (dep[top_1] < dep[top_2]) swap(top_1,top_2),swap(u,v);//调换顺序方便查询
  137.         ans=max(ans,query(id[top_1],id[u],1));
  138.         //查询u到u重链的顶端
  139.         u=fa[top[u]],top_1=top[u];
  140.     }
  141.     if (u==v) return ans;
  142.     //如果他们在一条重链上，我们就查完了
  143.     if (dep[u] > dep[v]) swap(u,v);
  144.     ans=max(ans,query(id[son[u]],id[v],1));
  145.     // 如果没查完，那现在两个点必是父亲儿子关系，更简单了
  146.     return ans;
  147. }
  149. int main(){
  150.     freopen("qtree.in","r",stdin);
  151.     freopen("qtree.out","w",stdout);
  152.     int t;
  153.     t=1;
  154.     while (t--){
  155.         int n;scanf("%d",&n);
  156.         for (int i=1;i<n;i++){
  157.             e[i].read();
  158.             G[e[i].x].push_back(e[i].y);
  159.             G[e[i].y].push_back(e[i].x);
  160.         }
  161.         cnt=0;
  162.         dfs_1(1,0,1);dfs_2(1,1);
  163.         init(n);
  164.         build(1,cnt,1);
  165.         char buf[100];
  166.         while (~scanf("%s",buf) && buf[0]!='D'){
  167.             int x,y;
  168.             scanf("%d%d",&x,&y);
  169.             if (buf[0]=='Q') printf("%d\n",Qtree(x,y));
  170.             if (buf[0]=='C') update(id[e[x].x],y,1);
  171.         }
  172.         Clear(n);//记得清空数组
  173.     }
  174.     return 0;
  175. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注