写在前面

以前写的太简略了，重新来总结一下。
如果您是初学者建议配合阅读 虚树 - 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