重链剖分, 树上路径问题大杀器

首先, 什么是树链剖分

数组, 要进行修改查询是非常方便的, 一眼线段树.

但是树并不是.

看一下我们目前已有的树上修改查询技术.

• 树上差分
  只能修改, 最后才能查询, 不然就只能很慢的单点查询,
• DFS 序 + 线段树
  只能进行子树操作, 不能进行路径操作.
• BFS 序 + 线段树
  只能进行连边操作, 而且除了菊花图都会被暴力卡爆.

上面只有树上差分是在树上修改, DFS 序和 BFS 序都相当于把树用方法砍成数组.

现在我们想要一种新的方法, 可以把树变成数组, 还能进行路径操作. (因为大多数题都是路径/子树操作)

这就是树链剖分.

树链剖分有很多种, 但是算法竞赛常用的只有重链剖分, 长链剖分, 还有一个我不知道算不算的实链剖分 LCT.

这次讲重链剖分, LCT 等过段时间Defad学会了再说, 长链剖分太FW了不讲.

重链剖分是怎么剖的

图大概4202年9月就做好了, 但是刚刚才开始写文.

第一遍 DFS, 根据子树大小确定哪个儿子是重儿子.

既然是 DFS, 那我们从根开始看.

\(5\) 有两个儿子, \(4\) 和 \(7\), 那我们先看 \(4\).

\(4\) 有两个儿子, \(3\) 和 \(1\), 那我们先看 \(1\).

\(1\) 是叶子, 显然 \(1\) 的子树大小是 \(1\).

回到 \(4\), 现在 \(4\) 的儿子里 \(3\) 还没有子树大小, 那么最大的就是 \(1\), 所以现在重儿子是 \(1\).

再看 \(3\), \(3\) 有两个儿子, \(2\) 和 \(6\), 那我们先看 \(2\).

\(2\) 是叶子, 显然 \(2\) 的子树大小是 \(1\).

回到 \(3\), 现在 \(3\) 的儿子里 \(6\) 还没有子树大小, 那么最大的就是 \(2\), 所以现在重儿子是 \(2\).

再看 \(6\), \(6\) 是叶子, 显然 \(6\) 的子树大小是 \(1\).

回到 \(3\), \(6\) 的子树大小没有比 \(2\) 的大, 所以重儿子还是 \(2\).

\(3\) 的子树大小是 \(2\) 的和 \(6\) 的加起来再加上 \(3\) 自己, 就是 \(3\).

回到 \(4\), \(3\) 的子树大小比 \(1\) 的大, 所以重儿子是 \(3\), \(4\) 的子树大小就是 \(5\).

回到 \(5\), 现在 \(4\) 的儿子里 \(7\) 还没有子树大小, 那么最大的就是 \(4\), 所以现在重儿子是 \(4\).

再看 \(7\), 我就不看了, \(7\) 的子树大小是 \(2\).

回到 \(5\), \(7\) 的子树大小没有比 \(4\) 的大, 所以重儿子还是 \(4\).

第二遍 DFS, 优先看重儿子, 后看其他儿子, 确定 DFS 序, 顺便把每个重儿子往祖宗上连链, 记录链顶.

这个似乎没做图, 但是大概那样.

\(5 - 4 - 3 - 2 ~|~ 6 ~|~ 1 ~|~ 7 - 8\)

void dfs1(int x, int f, int d) {
  fa[x] = f;
  dp[x] = d;
  sz[x] = 1;
  edge *k = e[x];
  while (k != NULL) {
    if (k->y == f) {
      k = k->nxt;
      continue;
    }
    dfs1(k->y, x, d + 1);
    sz[x] += sz[k->y];
    if (sz[sn[x]] < sz[k->y]) {
      sn[x] = k->y;
    }
    k = k->nxt;
  }
}

void dfs2(int x, int t) {
  tp[x] = t;
  dfn[x] = ++*dfn;
  nfd[*dfn] = x;
  if (sn[x]) {
    dfs2(sn[x], t);
  }
  edge *k = e[x];
  while (k != NULL) {
    if (dfn[i->y]) {
      k = k->nxt;
      continue;
    }
    dfs2(i->y, i->y);
    k = k->nxt;
  }
  tr[x] = *dfn - dfn[x];
}

再把 DFS 序放到线段树上

最底下就是每个 \(dfn\) 对应的点.

\(dfn_{x}\) 表示 \(x\) 的 DFS 序, \(dfn\) 对应 \(x\) 表示把 DFS 序找回 \(x\), 一般用两个数组 \(dfn\) 和 \(rev\) 记录, 但是Defad用 \(dfn\) 和 \(nfd\).

于是我们可以进行路径操作和子树操作, 当然子树操作直接用 \(dfn\) 和子树大小即可, 讲一下路径操作.

首先, 树剖求 LCA

这个比路径操作简单, 但又是路径操作的基础, 所以先讲一下.

在 \(x\) 和 \(y\) (求这俩的 LCA) 找一个链顶深度较大的往上跳到链顶的父亲, 一直到链顶相同了, 链顶相同之后找个深度小的就是 LCA.

int fnd_lca(int x, int y) {
  while (tp[x] ^ tp[y]) {
    if (dep[tp[x]] < dep[tp[y]]) {
      x ^= y;
      y ^= x;
      x ^= y;
    }
    x = fa[tp[x]];
  }
  return dep[x] < dep[y] ? x : y;
}

路径操作

我们刚才求 LCA 的时候跳了哪些, 直接加起来就是路径和啊, 路径加也就很简单了.

其他的操作也差不多.

void chg(int x, int y, ll z) {
  while (tp[x] ^ tp[y]) {
    if (dep[tp[x]] < dep[tp[y]]) {
      swap(x, y);
    }
    chg(1, 1, nn, dfn[tp[x]], dfn[x], z);
    x = fa[tp[x]];
  }
  if (dep[x] > dep[y]) {
    swap(x, y);
  }
  chg(1, 1, nn, dfn[x], dfn[y], z);
}

ll qry(int x, int y) {
  ll s = 0LL;
  while (tp[x] ^ tp[y]) {
    if (dep[tp[x]] < dep[tp[y]]) {
      swap(x, y);
    }
    s += qry(1, 1, nn, dfn[tp[x]], dfn[x]);
    x = fa[tp[x]];
  }
  if (dep[x] > dep[y]) {
    swap(x, y);
  }
  s += qry(1, 1, nn, dfn[x], dfn[y]);
  return s;
}

例题

VJudge LuoGu

板子.

习题

VJudge NewCoder

推推式子就好了, 甚至写了题解题解 ICPC 2019 SH 区域赛 F 树上简单问题.