Powered by:NEFU AB_IN

文章目录

• 树链剖分
• • 介绍
  • 前置知识
  • 主要思想
  • 代码解析
  • 例题
  • • 题意
    • 思路
    • 代码

树链剖分

• 介绍

  把“树”“剖分”成“链”

• 前置知识

  • 线段树
  • 树的 d f s dfs dfs序

• 主要思想

  我在这简单记录一下主要思想

  学习博客：树链剖分CSDN博客

  学习视频：树链剖分学习

  基本题型如下

  • 操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
  • 操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和
  • 操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z
  • 操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和

  需要维护树上的路径，比如根据 d f s dfs dfs序的 4 − 8 4-8 4−8都加上一个数，为了可以简化成 l o g log log的操作，可以用加法线段树来维护，把这颗树拆成一条一条链

  • 重儿子：当前父节点中孩子数量最多的，也就是每一层只有一个重儿子

  • 轻儿子：除重儿子外的其他子节点

  • 重边：每个节点与其重儿子间的边

  • 轻边：每个节点与其轻儿子间的边

  • 重链：重边连成的链

  • 轻链：轻边连成的链

    

  比如上图，蓝色点就是轻儿子，红色点就是重儿子

  按重儿子递归就可以产生有序数列，比如上图，就可以按照重链 1 − 2 − 3 − 4 1-2-3-4 1−2−3−4，至于为什么 1 1 1是轻儿子，我觉得在 d f s 2 dfs2 dfs2中一开始设立 t o p top top比较方便，就把 1 1 1放在了轻儿子的地位上

  现在如果要求 4 − 8 4-8 4−8链上的和，那么无非就是两条链，一条 1 − 2 − 3 − 4 1-2-3-4 1−2−3−4，一条 1 − 8 1-8 1−8，核心思想就是比 4 4 4和 8 8 8谁的 t o p top top重，谁就优先跳，解释的话我简单来说，就是 t o p top top重的肯定在下面，那么往上跳就越和另一个 t o p top top聚拢，跟另一个 t o p top top一样了就更好操作，这个操作也可以用来求 l c a lca lca

  那么 8 8 8是轻儿子，他的 t o p top top就是他自己； 4 4 4是重儿子，他的 t o p top top是 1 1 1，那么可以看出 8 8 8的 t o p top top深，让 8 8 8跳，记下 8 − 8 8-8 8−8的和，然后 8 8 8变成他自己的父节点 1 1 1，这时候 4 4 4和 8 8 8的 t o p top top相同了，就可以直接用线段树求 1 − 4 1-4 1−4的和

• 代码解析

  首先对于一个树，我们用链式前向星先建树

  const int N = 1e6 + 10;
  struct Edge
  {
      int v, ne;
  } e[N << 2];
  int h[N];
  int cnt;
  void add(int u, int v)
  {
      e[cnt].v = v;
      e[cnt].ne = h[u];
      h[u] = cnt++;
  }
  void init()
  {
      memset(h, -1, sizeof(h));
      cnt = 0;
  }
  

  其次，需要先对这个树进行一次 d f s dfs dfs，目的是为了标记重儿子，轻儿子，每个点的父节点以及每个点的深度

  int pre[N], sizx[N], son[N], deep[N];
  void dfs1(int u, int fa)
  {
      pre[u] = fa;
      deep[u] = deep[fa] + 1;
      sizx[u] = 1; // 初始u节点的子节点数量为1
      int maxson = -1;
      for (int i = h[u]; ~i; i = e[i].ne)
      {
          int v = e[i].v;
          if (v != fa) // 如果子节点不是父节点时递归
          {
              dfs1(v, u);
              sizx[u] += sizx[v]; // 父节点的子节点个数加上子节点统计的数量
              if (maxson < sizx[v])
              {
                  maxson = sizx[v];
                  son[u] = v; // 记录u的重儿子是v
              }
          }
      }
  }
  

  dfs1(1, 0) // 1的父节点是0
  

  处理好数据之后，第二遍 d f s dfs dfs根据重链标记 d f s dfs dfs序，并标记每个节点的 t o p top top

  int cnx; // dfs2 pool
  int dfn[N], top[N], a[N];
  void dfs2(int u, int t) // 因dfs1已经标记了重儿子，按重儿子递归，然后标记每个儿子的头
  {
      top[u] = t;
      dfn[u] = ++cnx;
      a[cnx] = w[u]; // 用a数组记录，下标为dfs序，值为次节点的初始值
      if (!son[u]) // 如果没有重儿子就返回
          return;
      dfs2(son[u], t); // 有就递归下去
      for (int i = h[u]; ~i; i = e[i].ne)
      {
          int v = e[i].v;
          if (v != pre[u] && v != son[u]) // 不能是父节点，也不能是重儿子，那么就是轻儿子
          {
              dfs2(v, v); //标记轻儿子，轻儿子的头就是它本身
          }
      }
  }
  

  dfs2(1, 1) // 1的top为1
  

  下面就是线段树的部分，因为接下来会有个例题，是线段树的区间加法+单点查询，所以就写这个了

  struct xds
  {
      int l, r, p, lazy;
  } tr[N << 2];
  
  void pushdown(int k)
  {
      if (tr[k].lazy)
      {
          tr[k << 1].p += tr[k].lazy;
          tr[k << 1 | 1].p += tr[k].lazy;
          tr[k << 1].lazy += tr[k].lazy;
          tr[k << 1 | 1].lazy += tr[k].lazy;
          tr[k].lazy = 0;
      }
  }
  
  void build(int k, int l, int r)
  {
      tr[k].l = l;
      tr[k].r = r;
      tr[k].lazy = 0;
      if (l == r)
      {
          tr[k].p = a[l];
          return;
      }
      int mid = l + r >> 1;
      build(k << 1, l, mid);
      build(k << 1 | 1, mid + 1, r);
  }
  
  void modify(int k, int ql, int qr, int w)
  {
      if (tr[k].l >= ql && tr[k].r <= qr)
      {
          tr[k].p += w;
          tr[k].lazy += w;
          return;
      }
      pushdown(k);
      int mid = tr[k].l + tr[k].r >> 1;
      if (ql <= mid)
          modify(k << 1, ql, qr, w);
      if (qr > mid)
          modify(k << 1 | 1, ql, qr, w);
  }
  
  int query(int k, int pos) //单点查询
  {
      if (tr[k].l == tr[k].r)
      {
          return tr[k].p;
      }
      pushdown(k);
      int mid = tr[k].l + tr[k].r >> 1;
      if (mid >= pos)
          query(k << 1, pos);
      else
          query(k << 1 | 1, pos);
  }
  
  

  build(1, 1, n)
  

  线段树写好了，那么就可以进行真正的树链剖分了

  void mtre(int x, int y, int z)
  {
      while (top[x] != top[y]) // 一直递归到top不同
      {
          if (deep[top[x]] < deep[top[y]]) // 挑选头重的（即深度大），优先进行操作
          {
              swap(x, y);
          }
          modify(1, dfn[top[x]], dfn[x], z); // 利用线段树，操作这一个链，（是对dfs序进行操作，而不是节点标号）
          x = pre[top[x]];                   // x变成x的父节点
      }
      if (deep[x] > deep[y])
      { // 头相同了，说明在同一条链上，这时挑个头轻的
          swap(x, y);
      }
      modify(1, dfn[x], dfn[y], z);
  }
  

• 例题

• HDU 3966 Aragorn’s Story

  • 题意

    给你一棵树，给你三种操作， u u u到 v v v 结点之间的结点加上 w w w，减去 w w w ，查询结点 u u u的权值？

  • 思路

    裸的树链剖分题，看操作就可以知道

  • 代码

    /*
     * @Author: NEFU AB_IN
     * @Date: 2021-09-04 18:43:00
     * @FilePath: \Vscode\ACM\Project\ShuLianPaoFen\hdu3966.cpp
     * @LastEditTime: 2021-09-04 20:10:16
     */
    #include <bits/stdc++.h>
    using namespace std;
    #define LL long long
    #define MP make_pair
    #define SZ(X) ((int)(X).size())
    #define IOS                      \
        ios::sync_with_stdio(false); \
        cin.tie(0);                  \
        cout.tie(0);
    #define DEBUG(X) cout << #X << ": " << X << endl;
    typedef pair<int, int> PII;
    
    const int N = 1e6 + 10;
    struct Edge
    {
        int v, ne;
    } e[N << 2];
    int h[N];
    int cnt;
    void add(int u, int v)
    {
        e[cnt].v = v;
        e[cnt].ne = h[u];
        h[u] = cnt++;
    }
    void init()
    {
        memset(h, -1, sizeof(h));
        memset(son, 0, sizeof son);
        cnx = 0;
        cnt = 0;
    }
    int w[N];
    int pre[N], sizx[N], son[N], deep[N];
    int dfn[N], top[N], a[N];
    int cnx; // dfs2 pool
    
    void dfs1(int u, int fa)
    {
        pre[u] = fa;
        deep[u] = deep[fa] + 1;
        sizx[u] = 1;
        int maxson = -1;
        for (int i = h[u]; ~i; i = e[i].ne)
        {
            int v = e[i].v;
            if (v != fa)
            {
                dfs1(v, u);
                sizx[u] += sizx[v];
                if (maxson < sizx[v])
                {
                    maxson = sizx[v];
                    son[u] = v;
                }
            }
        }
    }
    
    void dfs2(int u, int t)
    {
        top[u] = t;
        dfn[u] = ++cnx;
        a[cnx] = w[u];
        if (!son[u])
            return;
        dfs2(son[u], t);
        for (int i = h[u]; ~i; i = e[i].ne)
        {
            int v = e[i].v;
            if (v != pre[u] && v != son[u])
            {
                dfs2(v, v);
            }
        }
    }
    
    struct xds
    {
        int l, r, p, lazy;
    } tr[N << 2];
    
    void pushdown(int k)
    {
        if (tr[k].lazy)
        {
            tr[k << 1].p += tr[k].lazy;
            tr[k << 1 | 1].p += tr[k].lazy;
            tr[k << 1].lazy += tr[k].lazy;
            tr[k << 1 | 1].lazy += tr[k].lazy;
            tr[k].lazy = 0;
        }
    }
    
    void build(int k, int l, int r)
    {
        tr[k].l = l;
        tr[k].r = r;
        tr[k].lazy = 0;
        if (l == r)
        {
            tr[k].p = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(k << 1, l, mid);
        build(k << 1 | 1, mid + 1, r);
    }
    
    void modify(int k, int ql, int qr, int w)
    {
        if (tr[k].l >= ql && tr[k].r <= qr)
        {
            tr[k].p += w;
            tr[k].lazy += w;
            return;
        }
        pushdown(k);
        int mid = tr[k].l + tr[k].r >> 1;
        if (ql <= mid)
            modify(k << 1, ql, qr, w);
        if (qr > mid)
            modify(k << 1 | 1, ql, qr, w);
    }
    
    int query(int k, int pos) //单点查询
    {
        if (tr[k].l == tr[k].r)
        {
            return tr[k].p;
        }
        pushdown(k);
        int mid = tr[k].l + tr[k].r >> 1;
        if (mid >= pos)
            query(k << 1, pos);
        else
            query(k << 1 | 1, pos);
    }
    
    void mtre(int x, int y, int z)
    {
        while (top[x] != top[y])
        {
            if (deep[top[x]] < deep[top[y]]) 
            {
                swap(x, y);
            }
            modify(1, dfn[top[x]], dfn[x], z); 
            x = pre[top[x]];                   
        }
        if (deep[x] > deep[y])
        { 
            swap(x, y);
        }
        modify(1, dfn[x], dfn[y], z);
    }
    
    signed main()
    {
        IOS int n, m, q;
        while (cin >> n >> m >> q)
        {
            init();
            for (int i = 1; i <= n; ++i)
            {
                cin >> w[i];
            }
            for (int i = 1; i <= m; ++i)
            {
                int u, v;
                cin >> u >> v;
                add(u, v);
                add(v, u);
            }
            dfs1(1, 0);
            dfs2(1, 1);
            build(1, 1, n);
            while(q --){
                char c;
                cin >> c;
                if(c == 'I'){
                    int u, v, w;
                    cin >> u >> v >> w;
                    mtre(u, v, w);
                }
                if(c == 'D'){
                    int u, v, w;
                    cin >> u >> v >> w;
                    mtre(u, v, -w);
                }
                if(c == 'Q'){
                    int u;
                    cin >> u;
                    cout << query(1, dfn[u]) << '\n';
                }
            }
        }
        return 0;
    }
    

重写了一遍线段树，感觉这版的线段树比较好写，就是别忘了查询和更新时都需要进行 p u s h d o w n pushdown pushdown的操作

还有边写边用快捷键进行格式化文档，可以看上去更美观一些。。。

完结。