虚树

简介

对于这样一类题目：给定一棵 $n$ 点树，有 $q$ 个询问，每个询问关于树上 $k_i$ 个点， $n,q,\sum k \leq 10^5$

朴素做法 $O(qn)$

由于一些题目的特殊，发现求解只需保留树的结构，故可以重构一棵虚树

虚树包含了所有的 $k$ 个关键点和它们两两之间的 LCA，这样可以保证这虚树的节点个数 $< 2k$，保证了复杂度

构造

先求出原树节点的 dfs 序，把关键点按 dfs 序排序

为了方便，原树直接按 dfs 序编号

假设保留根节点，正在处理 第 $i$ 个关键点 $h[i]$，$l=\mathrm{lca}(h[i-1], h[i])$

需要注意的是入栈点还没有连边，出栈才连

• 红色节点为关键点
• 紫色为入栈关键点
• 蓝色为入栈非关键点
• 灰色为出栈点

用栈来维护一条从根到 $h[i-1]$ 的链，考虑如何加入 $h[i]$

• $h[i-1] = l$
• $h[i-1] \neq l$

对于第一种情况，直接加入栈即可

对于第二种情况，$l$ 肯定是在链上的点，但不一定在栈中存在

由于是按 dfs 序一个一个建构虚树，发现栈中 dep<dep[l] 的节点都得出栈，连边

直到倒数第二个点 dep > dep[l]，将栈顶出栈，加入 $l$，在 $l$ 和它之间连边，然后再将 $h[i]$ 入栈

这里有一种特殊情况 dep[栈顶] == dep[l]，此时直接加入 $h[i]$ 即可

std::sort(h + 1, h + 1 + m, cmp_dfn);
if (h[1] != rt) stk[sz++] = h[1]; // 防止重复加
rep(i, 2, m) {
      int lca = ::lca(h[i], stk[sz - 1]);
      if (lca == stk[sz - 1])
          stk[sz++] = h[i];
      else {
          while (sz - 2 >= 0 && dep[stk[sz - 2]] >= dep[lca]) { // 注意取等
              addedge(stk[sz - 2], stk[sz - 1]);
              sz--;
          }
          if (stk[sz - 1] != lca) {
              addedge(lca, stk[sz - 1]);
              stk[sz - 1] = lca;
          }
          stk[sz++] = h[i];
      }
  }
// 不要忘了最后加边
rep(i, 0, sz - 2) addedge(stk[i], stk[i + 1]);

然后？

倍增是必备的技巧，因为缩边的需要

「HNOI2014」世界树

「SDOI2011」消耗战