虚树

OI Wiki 上有详细的图解,这里就不赘述做法了。

简单说一下思想。

虚树就是将询问中涉及到的点从原树中拿出来,重新建树。这样就保证虚树中只涉及询问的点以及这些点的 $LCA$。从而起到控制复杂度的作用。

代码

// 以1为根节点,只有单向边
int stk[maxn], top;
vector<int> g[maxn];
void clean(int u) {
  for (auto &v : g[u]) clean(v);
  g[u].clear();
}
inline void addEdge(int u, int v) { g[u].push_back(v); }
void build(vector<int> &ps) {
  clean(1);
  sort(ps.begin(), ps.end(),
       [&](const int &a, const int &b) { return dfn[a] < dfn[b]; });
  stk[top = 1] = 1;
  for (auto &u : ps) {
    if (u == 1) continue;
    int fa = lca(u, stk[top]);
    if (fa != stk[top]) {
      while (dfn[fa] < dfn[stk[top - 1]]) {
        addEdge(stk[top - 1], stk[top]);
        --top;
      }
      addEdge(fa, stk[top--]);
      if (dfn[fa] > dfn[stk[top]]) stk[++top] = fa;
    }
    stk[++top] = u;
  }
  for (int i = 1; i < top; i++) addEdge(stk[i], stk[i + 1]);
}

例题 luogu2495

最后修改:2020 年 07 月 30 日 10 : 24 PM