11/11
17:49
OI

长链剖分 学习笔记

某套CSP模拟题里有道题用到了长链剖分的思想,补习一下,要是CSP没有挂以后肯定有用(所以不要挂啊OAO!!!)

众所周知树链剖分主要有重,长,实链剖分三种.重的全世界都会,实链剖分就是LCT那个

长链剖分,顾名思义,要选最长的链.在dfs的时候,选择最深的儿子即可


O(1)求k级祖先

这一部分先咕了,考完再说

长链剖分有好的性质:


维护贪心

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

例题

bzoj3252 攻略

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

优化深度有关DP

如果维护的信息只和深度有关,那么可以用长链剖分做到O(n)

具体来说,就是继承重儿子的信息,暴力合并轻儿子,然后每个节点只会被算一次

实现上,可以用指针实现,具体看代码.

例题

CF1009F Dominant Indices

我们令f_{x,i}表示x子树内距离为i点数

f_{x,i} = \sum f_{y,i-1}

我们发现f_xf_y平移了一下得到的,所以可以长链剖分

#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}分别表示距离xi的点数,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}

实现细节很多,康代码

#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;
}