「笔记」虚树

写在前面

以前写的太简略了,重新来总结一下。
如果您是初学者建议配合阅读 虚树 - OI Wiki 上的图示阅读。

概念

对于树 \(T=(V,E)\),给定关键点集 \(S\subseteq V\),则可定义虚树 \(T'=(V',E')\)。
对于点集 \(V'\subseteq V\),使得 \(u\in V'\) 当且仅当 \(u\in S\),或 \(\exist x,y\in S,\operatorname{lca}(x,y)=u\)。
对于边集,\((u,v)\in E'\),当且仅当 \(u,v\in V'\),且 \(u\) 为 \(v\) 在 \(V'\) 中深度最深的祖先。

个人理解:
仅保留关键点及其 \(\operatorname{lca}\),缩子树成边,仅保留分叉点,可能删去一些不包含关键点的子树。
压缩了树的信息,同时也丢失了部分树的信息。
一个分叉点会合并至少两个关键点,虚树节点数最多为 \(2k-1\) 个。节点数变为了 \(O(k)\) 级别。

关键点集 \(S = \{2, 6, 8, 9\}\) 的虚树如图中红色部分所示。

「笔记」虚树

算法

建树考虑增量法,每次向虚树中添加一个关键点。考虑先求得 关键节点 的 dfs 序,按照 dfs 序添加关键节点。这样可以保证相邻两个关键点的 \(\operatorname{lca}\) 深度不小于不相邻关键点的深度。

考虑单调栈维护虚树最右侧的链(上一个关键点与根的链),单调栈中节点深度递增,栈顶一定为上一个关键点。钦定 1 号节点为根,先将其压入栈中。
每加入一个关键点 \(a_i\),令 \(\operatorname{lca}(a_{i-1},a_i)=w\)。将栈顶 \(\operatorname{dep}_x > \operatorname{dep}_w\) 的弹栈,加入 \(w,a_i\),即为新的右链。特别地,若栈顶存在 \(\operatorname{dep}_x=\operatorname{dep}_w\),不加入 \(w\) 节点。
在此过程中维护每个节点的父节点,在弹栈时进行连边并维护信息,即得虚树。单次建虚树复杂度 \(O(kw)\) 级别,其中 \(w\) 为单次求 \(\operatorname{lca}\) 的复杂度。

代码

其中 \(\operatorname{Cut}\) 为封装后的树链剖分。

namespace VT { //Virtual Tree
  #define dep Cut::dep
  const int kMaxNode = kN;
  int top, node[kMaxNode], st[kMaxNode]; //栈
  int tag[kMaxNode]; //标记是否为关键点
  std::vector <int> newv[kMaxNode]; //虚树
  bool CMP(int fir_, int sec_) { //按 dfs 序比较
    return Cut::dfn[fir_] < Cut::dfn[sec_];
  }
  void Push(int u_) { //向虚树中加入 u_
    int lca = Cut::Lca(u_, st[top]);
    for (; dep[st[top - 1]] > dep[lca]; -- top) {
      newv[st[top - 1]].push_back(st[top]);
    }
    if (lca != st[top]) {
      newv[lca].push_back(st[top]); -- top;
      if (lca != st[top]) st[++ top] = lca;
    }
    if (st[top] != u_) st[++ top] = u_;
  }
  void Build(int siz_) {
    for (int i = 1; i <= siz_; ++ i) {
      node[i] = read();
      tag[node[i]] = 1;
    }
    std::sort(node + 1, node + siz_ + 1, CMP);
    st[top = 0] = 1;
    for (int i = 1; i <= siz_; ++ i) Push(node[i]);
    for (; top; -- top) newv[st[top - 1]].push_back(st[top]);
  }
}

例题

「SDOI2011」消耗战

给定一棵 \(n\) 个节点的树,边有边权。
给定 \(m\) 次询问,每次给定 \(k\) 个关键点,要求切除一些边,使得 \(k\) 个关键点与编号为 \(1\) 的点不连通。
最小化切除的边的权值之和。
\(2\le n\le 2.5\times 10^5\),\(1\le m\le 5\times 10^5\),\(\sum k \le 5\times 10^5\),\(1\le k\le n\),边权值 \(w\le 10^5\)。
2S,512MB。

首先想到一个简单的 DP。对于单次查询,设 \(f_u\) 为令以 \(u\) 为根的子树中的所有关键点 与 \(u\) 不连通的最小代价。
转移时枚举 \(u\) 的子节点,有状态转移方程:

\[f_{u} = \sum_{v\in son_u} \begin{cases} w(u,v) &(v\text{ is a key node})\\ \min\{w(u,v), f_v\} &\text{otherwise} \end{cases}\]

单次查询复杂度 \(O(n)\),总复杂度 \(O(nm)\),无法通过本题。

发现关键点集较小,不含任何关键点的子树显然无用,考虑建立虚树。
发现使得一个关键点 \(u\) 与根不相连的最小代价为根到关键点路径上最短的边长,设其为 \(\operatorname{val}_u\),在 dfs 时顺便维护。对于建立的虚树,有新的状态转移方程:

\[f_{u} = \sum_{v\in son'_u} \begin{cases} \operatorname{val}(u,v) &(v\text{ is a key node})\\ \min\{\operatorname{val}(u,v), f_v\} &\text{otherwise} \end{cases}\]

总复杂度 \(O(\sum k)\) 级别,可以通过本题。
对于本题,还可以删除以关键点作为祖先的关键点 进行进一步的优化。正确性显然,因为一定要使得其祖先与根不相连。

//知识点:虚树
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <vector>
#define LL long long
const int kMaxn = 2e5 + 5e4 + 10;
const int kMaxm = 5e5 + 10;
const LL kInf = 1e15 + 2077;
//=============================================================
int n, m, edge_num, head[kMaxn], v[kMaxm << 1], w[kMaxm << 1], ne[kMaxm << 1];
std :: vector <int> newv[kMaxn];
int top, node[kMaxn], st[kMaxn];
bool tag[kMaxn];
LL minw[kMaxn];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void GetMin(LL &fir, LL sec) {
  if (sec < fir) fir = sec;
}
void AddEdge(int u_, int v_, int w_) {
  v[++ edge_num] = v_, w[edge_num] = w_;
  ne[edge_num] = head[u_], head[u_] = edge_num;
}
namespace TCC { //TreeChainCut
  int fa[kMaxn], dep[kMaxn], size[kMaxn], son[kMaxn], top[kMaxn];
  int dfn_num, dfn[kMaxn];
  void Dfs1(int u_, int fa_) {
    fa[u_] = fa_;
    size[u_] = 1;
    dep[u_] = dep[fa_] + 1;
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i], w_ = w[i];
      if (v_ == fa_) continue;
      minw[v_] = std :: min(minw[u_], (LL) w_);
      Dfs1(v_, u_);
      size[u_] += size[v_];
      if (size[v_] > size[son[u_]]) son[u_] = v_;
    }
  }
  void Dfs2(int u_, int top_) {
    top[u_] = top_;
    dfn[u_] = ++ dfn_num;
    if (son[u_]) Dfs2(son[u_], top_);
    for (int i = head[u_]; i; i = ne[i]) {
      if (v[i] == son[u_] || v[i] == fa[u_]) continue;
      Dfs2(v[i], v[i]);
    }
  }
  int Lca(int u_, int v_) {
    for (; top[u_] != top[v_]; u_ = fa[top[u_]]) {
      if (dep[top[u_]] < dep[top[v_]]) std :: swap(u_, v_);
    }
    return (dep[u_] < dep[v_]) ? u_ : v_;
  }
}
bool CMP(int fir, int sec) {
  return TCC::dfn[fir] < TCC::dfn[sec];
}
LL Dfs(int u_) {
  LL sum = 0;
  for (int i = 0, size = newv[u_].size(); i < size; ++ i) {
    sum += Dfs(newv[u_][i]);
  }
  newv[u_].clear();
  if (tag[u_]) {
    tag[u_] = false;
    return minw[u_];
  }
  return std::min(minw[u_], sum);
}
#define dep (TCC::dep)
void Push(int u_) {
  int lca = TCC::Lca(u_, st[top]);
    for (; dep[st[top - 1]] > dep[lca]; -- top) {
      newv[st[top - 1]].push_back(st[top]);
    }
    if (lca != st[top]) {
      newv[lca].push_back(st[top]); -- top;
      if (lca != st[top]) st[++ top] = lca;
    }
    st[++ top] = u_;
}
//=============================================================
int main() {
  n = read();
  for (int i = 1; i < n; ++ i) {
    int u_ = read(), v_ = read(), w_ = read();
    AddEdge(u_, v_, w_), AddEdge(v_, u_, w_);
  }
  minw[1] = kInf;
  TCC::Dfs1(1, 0), TCC::Dfs2(1, 1);
  
  m = read();
  for (int i = 1; i <= m; ++ i) {
    int k = read();
    for (int j = 1; j <= k; ++ j) {
      node[j] = read();
      tag[node[j]] = true;
    }
    std :: sort(node + 1, node + k + 1, CMP);

    st[top = 0] = 1;
    for (int j = 1; j <= k; ++ j) Push(node[j]);
    for (; top; -- top) newv[st[top - 1]].push_back(st[top]);
    printf("%lld\n", Dfs(1));
  }
  return 0; 
}

「HEOI2014」大工程

我个人十分痛恨这种多合一的题目。
*这简直野蛮至极*

给定一棵 \(n\) 个节点的树,边权均为 1。
给定 \(m\) 次询问,每次给定 \(k\) 个关键点,求 \(k\) 个点对之间的路径长度和、最短路径长度、最长路径长度。
\(1\le n\le 10^6\),\(1\le m\le 5\times 10^4\),\(\sum k \le 2\times n\)。
2S,256MB。

先建立虚树,维护各点的深度,之后简单 DP。
第 2、3 问简单维护子树内关键点到根的最长链/最短链即可,考虑如何做第 1 问。
设 \(f_u\) 表示以 \(u\) 为根的子树内关键点对的路径长度之和,\(g_u\) 表示以 \(u\) 为根的子树内关键节点到 \(u\) 的距离之和,\(\operatorname{size}_u\) 表示以 \(u\) 为根的子树内关键节点的个数。
转移时分路径在子树内/跨越根节点讨论,则有显然的转移方程:

\[\begin{aligned} f_u &= \sum_{v\in son'_u} f_v + (g_v + \operatorname{size}_v\times \operatorname{dis}(u, v))\times (\operatorname{size}_u - \operatorname{size}_v)\\ g_u &= \sum_{v\in son'_u} g_v + \operatorname{size}_v \times \operatorname{dis}(u,v)\\ \operatorname{size}_u &= [u\text{ is a key node}] + \sum_{v\in son'_u} \operatorname{size}_v \end{aligned}\]

其中 \(\operatorname{dis}(u,v) = \operatorname{dep}_v - \operatorname{dep}_u\)。
代码实现中使用了树链剖分,总复杂度 \(O(\sum k\log n)\) 级别。

细节比较多。

//知识点:虚树
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <vector>
#define LL long long
const int kN = 1e6 + 10;
const LL kInf = 1e15 + 2077;
//=============================================================
int n, q, k;
int e_num, head[kN], v[kN << 1], ne[kN << 1];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Chkmax(LL &fir, LL sec) {
  if (sec > fir) fir = sec;
}
void Chkmin(LL &fir, LL sec) {
  if (sec < fir) fir = sec;
}
void Add(int u_, int v_) {
  v[++ e_num] = v_, ne[e_num] = head[u_], head[u_] = e_num;
}
namespace Cut {
  const int kMaxNode = kN;
  int fa[kMaxNode], dep[kMaxNode], siz[kMaxNode];
  int dfn_num, dfn[kN], son[kMaxNode], top[kMaxNode];
  void Dfs1(int u_, int fa_) {
    fa[u_] = fa_, dfn[u_] = ++ dfn_num, siz[u_] = 1, dep[u_] = dep[fa_] + 1;
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      if (v_ == fa_) continue;
      Dfs1(v_, u_);
      if (siz[v_] > siz[son[u_]]) son[u_] = v_;
      siz[u_] += siz[v_];
    }
  }
  void Dfs2(int u_, int top_) {
    top[u_] = top_;
    if (son[u_]) Dfs2(son[u_], top_);
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      if (v_ != son[u_] && v_ != fa[u_]) Dfs2(v_, v_);
    }
  }
  int Lca(int u_, int v_) {
    for (; top[u_] != top[v_]; u_ = fa[top[u_]]) {
      if (dep[top[u_]] < dep[top[v_]]) std::swap(u_, v_);
    }
    return dep[u_] < dep[v_] ? u_ : v_;
  }
}
namespace VT { //Virtual Tree
  #define dep Cut::dep
  const int kMaxNode = kN;
  int top, node[kMaxNode], st[kMaxNode], tag[kMaxNode];
  LL f1[kMaxNode], f2[kMaxNode], f3[kMaxNode];
  LL sumdis[kMaxNode], maxdis[kMaxNode], mindis[kMaxNode], siz[kMaxNode];
  std::vector <int> newv[kMaxNode];
  bool CMP(int fir_, int sec_) {
    return Cut::dfn[fir_] < Cut::dfn[sec_];
  }
  void Push(int u_) {
    int lca = Cut::Lca(u_, st[top]);
    for (; dep[st[top - 1]] > dep[lca]; -- top) {
      newv[st[top - 1]].push_back(st[top]);
    }
    if (lca != st[top]) {
      newv[lca].push_back(st[top]); -- top;
      if (lca != st[top]) st[++ top] = lca;
    }
    if (st[top] != u_) st[++ top] = u_;
  }
  void Build(int siz_) {
    for (int i = 1; i <= siz_; ++ i) {
      node[i] = read();
      tag[node[i]] = 1;
    }
    std::sort(node + 1, node + siz_ + 1, CMP);
    st[top = 0] = 1;
    for (int i = 1; i <= siz_; ++ i) Push(node[i]);
    for (; top; -- top) newv[st[top - 1]].push_back(st[top]);
  }
  void Dfs(int u_) {
    f1[u_] = f3[u_] = 0, f2[u_] = kInf;
    sumdis[u_] = 0, maxdis[u_] = tag[u_] ? 0 : -kInf, mindis[u_] = tag[u_] ? 0 : kInf;
    siz[u_] = tag[u_];
    for (int i = 0, lim = newv[u_].size(); i < lim; ++ i) {
      int v_ = newv[u_][i];
      LL dis = dep[v_] - dep[u_];
      Dfs(v_);
      siz[u_] += siz[v_];
      sumdis[u_] += sumdis[v_] + siz[v_] * dis;
      Chkmin(mindis[u_], mindis[v_] + dis);
      Chkmax(maxdis[u_], maxdis[v_] + dis);
      Chkmin(f2[u_], f2[v_]);
      Chkmax(f3[u_], f3[v_]);
    }
    LL maxv = -1, maxvv = -1, minv = kInf, minvv = kInf;
    if (tag[u_]) maxv = minv = 0;
    for (int i = 0, lim = newv[u_].size(); i < lim; ++ i) {
      int v_ = newv[u_][i];
      LL dis = dep[v_] - dep[u_];
      f1[u_] += f1[v_] + (sumdis[v_] + siz[v_] * dis) * (siz[u_] - siz[v_]);
      if (maxdis[v_] + dis >= maxv) maxvv = maxv, maxv = maxdis[v_] + dis;
      else if (maxdis[v_] + dis > maxvv) maxvv = maxdis[v_] + dis;
      if (mindis[v_] + dis <= minv) minvv = minv, minv = mindis[v_] + dis;
      else if (mindis[v_] + dis < minvv) minvv = mindis[v_] + dis;
    }
    if (minv != kInf && minvv != kInf) Chkmin(f2[u_], minv + minvv);
    if (maxv != -1 && maxvv != -1) Chkmax(f3[u_], maxv + maxvv);
    tag[u_] = 0;
    newv[u_].clear();
  }
  void Solve(int siz_) {
    Build(siz_);
    Dfs(1);
    printf("%lld %lld %lld\n", f1[1], f2[1], f3[1]);
  }
}

//=============================================================
int main() {
  n = read();
  for (int i = 1; i < n; ++ i) {
    int u_ = read(), v_ = read();
    Add(u_, v_), Add(v_, u_);
  }
  Cut::Dfs1(1, 0), Cut::Dfs2(1, 1);
  int q = read();
  while (q --) {
    k = read();
    VT::Solve(k);
  }
  return 0; 
}

写在最后

鸣谢:

虚树 - OI Wiki

上一篇:LCA算法——倍增


下一篇:最近公共祖先(lca)学习笔记