换根树剖 学习笔记

前言

树剖其实在一些情况下是可以换根的，会多一些分讨。

过程

我们以一道题为例。

题意

进行以下操作，维护树结构：

1. 换根
2. 链赋值
3. 查询子树最小值

$1 \leq n, m \leq 10^5$

题解

我们现随便以一个点把树剖了，然后看看怎么应付这些操作。

注意到树上两点之间的简单路径是直接确定的，所以树剖并不影响我们的链操作。

我们在根为 $r$ 时，查询以 $x$ 为根的子树最小值时，分为以下三种情况：

• $x = r$，全局最小值
• $x$ 的子树中不包含 $r$，换不换根的不造成任何影响，之间查线段树上对应区间即可
• $x$ 的子树中包含 $r$，这个是比较复杂的情况。我们需要从全局里面移除 $x$ 包含 $r$ 的那个直接儿子造成的影响，因为这个儿子在当前根下是 $x$ 的父亲。由于我们不能老是这儿子 那儿子叫，于是我们给这个“$x$ 包含 $r$ 的那个直接儿子”取名为“父亲儿子”。首先找父亲儿子不是什么难事，从 $x$ 和 $r$ 里面选低的那个跳高，中途判一下关系，就行了。找到这个父亲儿子之后，我们把这个父亲儿子管辖的区间的左边的区间统计最小值，再把右边的区间统计最小值即可

还剩下一个问题，如何判断 $x$ 的子树里有没有 $r$。这个其实我想了个很复杂的东西，最后发现其实可以判 $\mathsf{dfn}_x < r \leq \mathsf{lst}_x$，其中 $\mathsf{lst}_x$ 表示 $x$ 管辖区间的最后一个点，可以通过 $\mathsf{dfn}_x + \mathsf{size}_x - 1$ 算出，也可以树剖时直接维护。

代码

/* Please submit with C++17! It's best to use C++20 or higher version.
 * No header file and no RBLIB (https://git.rbtr.ee/root/Template).
 * By Koicy (https://koicy.ly)
 * Email n@rbtr.ee
 * I've reached the end of my fantasy.

         __    __                             __         _
   _____/ /_  / /_________  ___              / /______  (_)______  __
  / ___/ __ \/ __/ ___/ _ \/ _ \   ______   / //_/ __ \/ / ___/ / / /
 / /  / /_/ / /_/ /  /  __/  __/  /_____/  / ,< / /_/ / / /__/ /_/ /
/_/  /_.___/\__/_/   \___/\___/           /_/|_|\____/_/\___/\__, /
                               SIGN                         /___*/
#ifndef XCODE
constexpr bool _CONSOLE = false;
#else
constexpr bool _CONSOLE = true;
#endif
#define __NO_MAIN__ false
#define __ENABLE_RBLIB__ true
constexpr bool _MTS = false, SPC_MTS = false;
constexpr char EFILE[] = "";
#define FULL(arg) arg.begin(), arg.end()
#define dor(i, s, e) for (tp i = s, $##i =(s)<(e)?1:-1,$e##i=e;i!=$e##i;i+=$##i)
#define gor(i, s,e)for(tp i=s,$##i=(s)<(e)?1:-1,$e##i=(e)+$##i;i!=$e##i;i+=$##i)

// :/

signed STRUGGLING([[maybe_unused]] unsigned long TEST_NUMBER) {
  struct SEG {
    static tp op(tp l, tp r) { return min(l, r); }
    static tp e() { return INF; }
    static tp mapping(pair<tp, tp> f, tp s) { return f.first < 0 ? s : f.second; }
    static pair<tp, tp> composition(pair<tp, tp> f1, pair<tp, tp> f2) { return max(f1, f2); }
    static pair<tp, tp> id() { return make_pair(-INF, INF); }
  };
  tp n, m; bin >> n >> m;
  vetp dep(n + 1);
  vetp f(n + 1);
  vetp hson(n + 1);
  vetp s(n + 1);
  vetp top(n + 1);
  vetp dfn(n + 1);
  vetp lst(n + 1);
  vetp real(n + 1);
  vector<vector<tp>> e(n + 1);
  for (tp i = 1; i < n; ++i) {
    tp u, v; bin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  lib::Segtree<tp, SEG::op, SEG::e, pair<tp, tp>, SEG::mapping, SEG::composition, SEG::id> o(n + 1);
  auto dfs1 = [&](auto $, tp x) -> void {
    dep[x] = dep[f[x]] + 1;
    s[x] = 1;
    for (auto& i : e[x]) {
      if (i == f[x]) continue;
      f[i] = x;
      $($, i);
      s[x] += s[i];
      if (s[i] > s[hson[x]]) hson[x] = i;
    }
  };
  tp cnt = 0;
  auto dfs2 = [&](auto $, tp x, tp h) -> void {
    real[lst[x] = dfn[x] = ++cnt] = x;
    top[x] = h;
    if (!hson[x]) return;
    $($, hson[x], h); lst[x] = lst[hson[x]];
    for (auto& i : e[x]) {
      if (i != f[x] && i != hson[x]) { $($, i, i); lst[x] = lst[i]; }
    }
  };
  auto opt = [&](tp x, tp y, tp z, tp time) -> void {
    while (top[x] != top[y]) {
      if (dep[top[x]] < dep[top[y]]) swap(x, y);
      o.apply(dfn[top[x]], dfn[x], make_pair(time, z));
      x = f[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    o.apply(dfn[x], dfn[y], make_pair(time, z));
  };
  auto get = [&](tp x, tp y) -> tp {
    while (top[x] != top[y]) {
      if (dep[top[x]] < dep[top[y]]) swap(x, y);
      if (f[top[x]] == y) return top[x];
      x = f[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return hson[x];
  };
  dfs1(dfs1, 1);
  dfs2(dfs2, 1, 1);
  gor(i, 1, n) o.set(dfn[i], bin);
  tp r = bin;
  gor(i, 1, m) {
    tp op = bin;
    if (op == 1) r = bin;
    else if (op == 2) {
      tp l, r, k; bin >> l >> r >> k;
      opt(l, r, k, i);
    } else {
      tp x = bin;
      if (x == r) bin << o.all_prod() << '\n';
      else if (dfn[r] > dfn[x] && dfn[r] <= lst[x]) {
        tp t = get(x, r);
        bin << min(o.prod(1, dfn[t] - 1), o.prod(lst[t] + 1, n)) << '\n';
      } else bin << o.prod(dfn[x], lst[x]) << '\n';
    }
  }
  return 0;
}

void MIST() {
}

// :\ */

例题

• CF916E Jamie and Tree

---

• Category: 学习笔记
• Last update: 2024-06-30 03:15:14^UTC+8
• Tags: 树链剖分