长链剖分 学习笔记

发表于 更新于 分类于 阅读次数：

某套CSP模拟题里有道题用到了长链剖分的思想,补习一下,要是CSP没有挂以后肯定有用(所以不要挂啊OAO!!!) 众所周知树链剖分主要有重,长,实链剖分三种.重的全世界都会,实链剖分就是LCT那个 长链剖分,顾名思义,要选最长的链.在dfs的时候,选择最深的儿子即可

O(1)求k级祖先

这一部分先咕了,考完再说 update 2020： 准退役，但是至少没退役，来更新一下 长链剖分有一个极好的性质：任何一个点$k$级祖先，在的链长$ \geq k$。 证明：一条链显然。不在一条链，如果不足$k$，剖分时就会选这条$k$的链。 于是可以用以下步骤完成： 记录每个数的最高位$1$，记录每个点向上$2^k$到哪，记录每条长为$k$的链的链头向上或向下$k$个点。 询问的时候先把询问最高位跳上去，发现所在链长度一定$ > $剩下没跳的部分，就可以找到了。

维护贪心

模拟赛里见到的就是类似这个题的…

例题

bzoj3252 攻略 我们可以发现贪心选最优是正确的,把长链剖分的深度改称链权值和剖分,贪心选$k$大即可

优化深度有关DP

如果维护的信息只和深度有关,那么可以用长链剖分做到$O(n)$ 具体来说,就是继承重儿子的信息,暴力合并轻儿子,然后每个节点只会被算一次 实现上,可以用指针实现,具体看代码.

例题

CF1009F Dominant Indices 我们令$f_{x,i}$表示$x$子树内距离为$i$点数 $$f_{x,i} = \sum f_{y,i-1}$$ 我们发现$f_x$是$f_y$平移了一下得到的,所以可以长链剖分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>

inline int rd() {
  int a = 1, b = 0; char c = getchar();
  while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return a ? b : -b;
}

const int N = 1e6 + 233;

int n, dep[N], son[N], *f[N], tmp[N], *pt = tmp, ans[N];
std::vector<int> G[N];

void dfs1(int x, int fa) {
  for (int y : G[x]) if (y != fa) {
    dfs1(y, x);
    if (dep[y] > dep[son[x]])
      son[x] = y;
  }
  dep[x] = dep[son[x]] + 1;
}

void dfs2(int x, int fa) {
  f[x][0] = 1;
  if (son[x]) {
    f[son[x]] = f[x] + 1;
    dfs2(son[x], x);
    ans[x] = ans[son[x]] + 1;
  }
  for (int y : G[x]) if (y != fa && y != son[x]) {
    f[y] = pt; pt += dep[y];
    dfs2(y, x);
    for (int j = 1; j <= dep[y]; ++j) {
      f[x][j] += f[y][j - 1];
      if ((j < ans[x] && f[x][j] >= f[x][ans[x]])
           (j > ans[x] && f[x][j] > f[x][ans[x]]))
        ans[x] = j;
    }
  }
  if (f[x][ans[x]] == 1)
    ans[x] = 0;
}

int main() {
  n = rd();
  for (int i = 1; i < n; ++i) {
    int x = rd(), y = rd();
    G[x].push_back(y);
    G[y].push_back(x);
  }
  dfs1(1, 0);
  f[1] = pt;
  pt += dep[1];
  dfs2(1, 0);
  for (int i = 1; i <= n; ++i)
    printf("%d\n", ans[i]);
  return 0;
}

[POI2014]HOT-Hotels 考虑在三个点LCA计算贡献. 我们先统计两个点,再加入一个点即可进行计算 令$f_{x,i},g_{x,i}$分别表示距离$x$为$i$的点数,$x$子树内距离他们的$lca$距离为$d$,$lca$距离$x$距离为$d-i$的点对数量. 那么考虑$x$点扩展子树$y$,计算答案.答案可以由$x$内选一个/两个,$y$内选两个/一个点得到 $$ans += g_{x,0} + \sum f_{x,i}g_{y,i-1} + f_{y,i-1}g_{x,i}$$ $$g_{x,i}+ = g_{y,i+1} + f_{x,i} f_{y,i-1} $$ $$f_{x,i} += f_{y,i-1}$$ 实现细节很多,康代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>

inline int rd() {
  int a = 1, b = 0; char c = getchar();
  while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return a ? b : -b;
}

const int N = 1e5 + 233;

int n, len[N], son[N];

struct Graph {
  int to, nxt;
} G[N * 2];

int head[N], tot;

inline void addedge(int x, int y) {
  G[++tot].to = y, G[tot].nxt = head[x],
  head[x] = tot;
}

void dfs1(int x, int fa) {
  for (int i = head[x]; i; i = G[i].nxt) {
    int y = G[i].to;
    if (y != fa) {
      dfs1(y, x);
      if (len[y] > len[son[x]])
        son[x] = y;
    }
  }
  len[x] = len[son[x]] + 1;
}

long long *f[N], *g[N], tmp[N * 10], *pt = tmp, ans;

void dfs2(int x, int fa) {
  if (son[x]) {
    f[son[x]] = f[x] + 1;
    g[son[x]] = g[x] - 1;
    dfs2(son[x], x);
  }
  f[x][0] = 1;
  ans += g[x][0];
  for (int i = head[x]; i; i = G[i].nxt) {
    int y = G[i].to;
    if (y != fa && y != son[x]) {
      f[y] = pt, pt += len[y] * 2;
      g[y] = pt, pt += len[y] * 2;
      dfs2(y, x);
      for (int j = 0; j < len[y]; ++j) {
        if (j > 0)
          ans += f[x][j - 1] * g[y][j];
        ans += g[x][j + 1] * f[y][j];
      }
      for (int j = 0; j < len[y]; ++j) {
        g[x][j + 1] += f[x][j + 1] * f[y][j];
        if (j > 0)
          g[x][j - 1] += g[y][j];
        f[x][j + 1] += f[y][j];
      }
    }
  }
}

int main() {
  n = rd();
  for (int i = 1; i < n; ++i) {
    int x = rd(), y = rd();
    addedge(x, y);
    addedge(y, x);
  }
  dfs1(1, 0);
  f[1] = pt, pt += len[1] * 2;
  g[1] = pt, pt += len[1] * 2;
  dfs2(1, 0);
  printf("%lld\n", ans);
  return 0;
}