Two basic problems

1.将树从x到y结点最短路径上所有节点的值都加上
树上差分，O(n+m）
2.询问x到y结点最短路径上所有节点的值之和
lca的大水题，先用倍增等算法求lca，然后注意lca不要重复计算

Who wants it？

如果两个问题结合起来，边修改边询问（在线）呢？
每次询问之前都要重新跑一遍dfs计算，t到飞起
那么在线询问树中路径上点权和边权的和就需要树链剖分啦

What‘s it？

树剖是通过轻重边剖分将树分割成多条链，并尽可能使较长的链的长度大，先然后利用数据结构来维护这些链上的相关信息。
这

明确概念

重儿子：父亲节点的所有儿子中子树结点数目最多（size最大）的结点
轻儿子：父亲节点中除了重儿子以外的儿子
重边：父亲结点和重儿子连成的边
轻边：父亲节点和轻儿子连成的边
重链：由多条重边连接而成的路径
轻链：由多条轻边连接而成的路径

(感谢锣鼓好图）
红点即链头，黑边即重边，黑链即重链

过程

dfslook(int u)维护基本结构信息：
以儿子v为根的子树的节点数量size[v]
儿子v的父亲fa[v]=u;
v的深度deep[v]=deep[u]+1
重儿子hson[u]

void dfslook(int u, int f) {
  size[u] = 1;
  int maxsz = 0;
  for (int p = head[u]; p; p = a[p].next) {
    int v = a[p].v;
    if (v == f) continue;
    fa[v] = u;
    deep[v] = deep[u] + 1;
    dfslook(v, u);
    size[u] += size[v];
    if (size[v] > size[hson[u]]) hson[u] = v;
  }
}

dfscut(int u, int tpu)剖分
设现在访问的点是u，u所在重链的顶端为tpu
记录每个点的dfs序rank[u]
记录每个dfs序对应的点id[dfs_clock]（这两个变量可能跟大多数板子是反的，因为个人理解：id表示你的身份）
记录u的顶端tp[u]=tpu，
先选择u的重儿子hson[u]，把u所在的重链标记出来，
然后在对剩下的儿子v dfs，得到多个新的重链，且这些重链的顶端都是v
注意每个子树内的节点的dfs序也是连续的

void dfscut(int u, int tpp) {
  rnk[u] = ++dfs_clock;
  id[dfs_clock] = u;
  tp[u] = tpp;

  if (hson[u]) dfscut(hson[u], tpp);
  for (int p = head[u]; p; p = a[p].next) {
    int v = a[p].v;
    if (v == fa[u] || v == hson[u]) continue;
    //不能在走一遍重儿子！！！！！！！！！！
    dfscut(v, v);
  }
}

为什么要在第二遍标记dfs序呢？

因为这样就可以保证一条（重）链上的点的编号都是连续的

这样一棵树就被剖分成了若干个重链，且每条重链上的dfs序都是连续的
对所有的链维护一个数据结构，就可以进行区间的操作
刚才说了，每条链上的点都是连续的，而区间维护的数据结构有个前提就是数据的编号连续
（常用线段树）
考虑路径两端在不在一个链中，直接判断链头相不相同即可
1）在
直接维护或查询
2）不在
移动到上面的链，形成第一种情况，每次对走过的路径进行操作

直到链头相同，即两个点在同一条链上，即1）的情况

树链剖分的两个性质：

1，如果(u, v)是一条轻边，那么size(v) < size(u)/2；

2，从根结点到任意结点的路所经过的轻重链的个数必定都小于logn（还不会证明）
可以证明，树链剖分的时间复杂度为O(nlog^2n)

那树链剖分用了哪些思想呢？

要维护树上的数据，通常需要考虑大量结构信息（正如dfslook所统计的那样）
将树上的维护转化为无结构的链上的维护就非常方便了
一条链的数据编号连续，就可以对单条链进行维护
链之间的结构关系（比如连接两条链的边是谁）知道，就可以跨链维护
dfs每次没有回溯地走到底形成了一条链，这条链上的dfs序自然是连续的，所以就考虑用dfs序来对链上的点标号拉
让尽可能多的点在一条链上，那么查询的时候才能尽量减少拆分次数啊

luogu模板

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200004;
#define lson 2 * o
#define rson 2 * o + 1
int n, m, rt, ha, e, head[maxn], rnk[maxn], id[maxn], hson[maxn], size[maxn],
    fa[maxn], deep[maxn], tp[maxn], dfs_clock,w[maxn];
struct node {
  int v, next;
} a[200001];
void insert(int u, int v) {
  a[++e].v = v;
  a[e].next = head[u];
  head[u] = e;
}
struct line_tree {
  int base[maxn], sumv[4 * maxn], addv[4 * maxn];
  int ql, qr;

  void mark(int o, int l, int r, int vo) {
    sumv[o] += vo * (r - l + 1) % ha;
    addv[o] += vo % ha;
    sumv[o] %= ha, addv[o] %= ha;
  }
  void pushdown(int o, int l, int r) {
    int mid = (l + r) / 2;
    mark(lson, l, mid, addv[o]);
    mark(rson, mid + 1, r, addv[o]);
    addv[o]=0;
  }
  void build(int o, int l, int r) {
    int mid = l + (r - l) / 2;
    if (l == r) {
      sumv[o] = base[l];
      return;
    }
    build(lson, l, mid);
    build(rson, mid + 1, r);
    sumv[o] = (sumv[lson] + sumv[rson])%ha;
  }
  void add(int o, int l, int r, int v) {
    if (l == r) {
      sumv[o] += v % ha;
      sumv[o] %= ha;
      return;
    }
    if (ql <= l && r <= qr) {
      mark(o, l, r, v);
      return;
    }
    int mid = (l + r) / 2;
    pushdown(o, l, r);
    if (ql <= mid) add(lson, l, mid, v);
    if (mid + 1 <= qr) add(rson, mid + 1, r, v);
    sumv[o] = (sumv[lson] + sumv[rson]) % ha;
    sumv[o] %= ha;
  }
  int query(int o, int l, int r) {
    int ans = 0;
    if (ql <= l && r <= qr) return sumv[o];
    int mid = (l + r) / 2;
    pushdown(o, l, r);
    if (ql <= mid) ans += query(lson, l, mid) % ha, ans %= ha;
    if (mid + 1 <= qr) ans += query(rson, mid + 1, r)%ha, ans %= ha;
    return ans;
  }
  void setq(int l, int r) { ql = l, qr = r; }
} tree;


/*树链剖分主要过程*/

void dfslook(int u, int f) {
  size[u] = 1;
  int maxsz = 0;
  for (int p = head[u]; p; p = a[p].next) {
    int v = a[p].v;
    if (v == f) continue;
    fa[v] = u;
    deep[v] = deep[u] + 1;
    dfslook(v, u);
    size[u] += size[v];
    if (size[v] > size[hson[u]]) hson[u] = v;
  }
}
void dfscut(int u, int tpp) {
  rnk[u] = ++dfs_clock;
  id[dfs_clock] = u;
  tp[u] = tpp;

  if (hson[u]) dfscut(hson[u], tpp);
  for (int p = head[u]; p; p = a[p].next) {
    int v = a[p].v;
    if (v == fa[u] || v == hson[u]) continue;
    //不能在走一遍重儿子！！！！！！！！！！
    dfscut(v, v);
  }
}


/*跨链维护主要过程*/

int getsumroad(int x, int y) {
  int ans = 0;
  while (tp[x] != tp[y]) {
    if (deep[tp[x]] > deep[tp[y]]) swap(x, y);
    tree.setq(rnk[tp[y]], rnk[y]);
    ans += tree.query(1, 1, n)%ha;
    ans%=ha;
    y = fa[tp[y]];
//跳到两条链的“交点“
  }
  if (deep[x] > deep[y]) swap(x, y);
  tree.setq(rnk[x], rnk[y]);
  ans+=tree.query(1, 1, n) % ha;

  ans %= ha;
  return ans;
}
void addsumroad(int x, int y, int z) {
  z%=ha;//!!!!
  while (tp[x] != tp[y]) {
    if (deep[tp[x]] > deep[tp[y]]) swap(x, y);
    tree.setq(rnk[tp[y]], rnk[y]);
    tree.add(1, 1, n, z);
    y = fa[tp[y]];
  }
  if (deep[x] > deep[y]) swap(x, y);
  tree.setq(rnk[x], rnk[y]);
  tree.add(1, 1, n, z);
}
int main() {
  cin >> n >> m >> rt >> ha;
  int u, v;
  for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
  for (int i = 1; i <= n - 1; i++) {
    scanf("%d%d", &u, &v);
    insert(u, v), insert(v, u);
  }
  dfslook(rt, 0);
  dfscut(rt, rt);
  for(int i=1;i<=n;i++)tree.base[i]=w[id[i]];
  tree.build(1, 1, n);
  int k, s, t, z;
  for (int i = 1; i <= m; i++) {
    scanf("%d", &k);
    if (k == 1) {
      scanf("%d%d%d", &s, &t, &z);
      addsumroad(s, t, z);
    } else if (k == 2) {
      scanf("%d%d", &s, &t);
      cout << getsumroad(s, t) << endl;

    } else if (k == 3) {
      scanf("%d%d", &s, &z);
      tree.setq(rnk[s], rnk[s] + size[s] - 1);
      tree.add(1, 1, n, z);
    } else if (k == 4) {
      scanf("%d", &s);
      tree.setq(rnk[s], rnk[s] + size[s] - 1),
      cout << tree.query(1, 1, n) << endl;
    }
  }

}

树状数组

带根号复杂度数据结构（一）

发表评论取消回复