• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

虚拟树学习笔记:一镜花一月 一树虚点


Recommended Posts

Virtual Tree

揭开华丽的外衣,关注问题的本质。

这就是虚拟树在做的事情,所以虚拟树不是虚拟的,而是伪原树最真实的部分,所以应该叫‘真实树’。在实际问题中回答完问题后往往稍纵即逝,所以给人的感觉是稍纵即逝的错觉。现实中很多敢说真话的人就像这种虚拟树一样消失了,这可能也是人们称之为‘虚拟树’的原因。

定义

一棵树,多次查询,每次查询给出一些关键点,需要遍历整棵树才能找到答案,但是所有查询的关键点总数是有限的。

此时可以每次关于关键点建立原树的虚拟树,只保留与关键点个数同阶的节点个数,遍历虚拟树得到查询结果。

结合一个经典问题研究虚拟树。

SDOI2011 消耗战

把它简化成一个带边权重的树,每次求根节点和\(k\)个关键点断开所需的代价最小。

简单的方法是,每个点\(i\)都有一个值\(f_i\ ),该值指示从\(i\)断开\(i\)子树中所有关键点的最小成本,以及在每个决策中是否断开\(i\)到其每个子的边。总复杂度\(O(nm)\。

接下来,介绍了虚拟树的方法。第一,根节点也被设置为关键点,因为查询的就是它。假设我们只提出了成对的关键点和关键点的LCA,其余的点全部删除。未被删除的点连接到其最近的未被删除的祖先,边权重是两点之间的路径的最小边权重。那么这棵树就是原树围绕给定的关键点构建的虚拟树。我们从这棵树上得到的答案与从原树上得到的答案是等价的。

很容易发现,在关键点之外的虚拟树上,每增加一个点,这个点至少要有两个带关键点的子树,它的出现至少要合并两个带关键点的连通块。因此,如果有\(x\)个关键点,则至多\(x-1\)个附加点将被添加到虚拟树中,因此虚拟树的大小与关键点的数量相同。

虚树的建立

其实我没写过,但是听说过虚拟树的建造方法,看看能不能根据印象变出来。

如果要建立一棵虚拟树,需要预先对每个点的DFS顺序进行预处理。根据虚拟树的定义,很容易发现虚拟树中每个节点的DFS顺序是原树中DFS顺序的相对顺序。

所以考虑增量构造,按照DFS顺序对重点进行排序。假设已经建立了第一个\(i\)关键点的虚拟树,那么需要添加下面的关键点。我们希望将新添加的关键点和第一个\(i\)关键点的LCA添加到虚拟树中。因为后面的关键点的DFS阶增加,它们和已经增加的\(x\))点的LCA的DFS阶也必须是单调的。因为LCA是最低的共同祖先,无论如何它都是第(x)个关键点的祖先,一个点的祖先的DFS顺序是单调的,也就是这些祖先的深度是单调的。

根据暴力构造的定义,成对计算LCA,将这些点在DFS中排序,直接构造一棵树。如果有\(k\)个关键点,则复杂度为\(o(k ^ 2 \ logn)\)。

所以假设在\(x\)和\(x\)后面加的一个点的LCA深度是\(D\),那么\(x\)深度大于\(D\)的祖先永远不会充当后面那个点和\(x\)的LCA。所以每加一个点处理一个就简单了。枚举前面的所有关键点,将LCA添加到虚拟树中,弹出比LCA更深的所有点。如果有\(k\)个关键点,这个的复杂度是\(O(k (n k\log n))\),看起来更差。

当找到第(I)个关键点时,已经连接的点的单调堆叠不是从根节点到第(I)个关键点的路径。这是因为对于所有的第一个\(i-1\)关键点,都会弹出比it和\(i\)的LCA更深的祖先。换句话说,就是

我们可以尝试不维护所有栈,全局只维护一个栈,也就是这条路径。加点\(I ^ 1 \)时,设它和第\(i\)个关键点的LCA为\(u\)。弹出栈中从\(u\)到关键点\(i\)的路径并按下。).对于插入的关键点,它们带关键点\(i 1\)的LCA不会比\(u\)深,所以它们带关键点\(i 1\)的LCA就是它们带\(u\)的LCA,也就是它们带关键点\(i\)的LCA。每次插入虚拟树时,只需添加\(u\)即可。如果有\(k\)个关键点,那么这个的复杂度是\(O(k\log n n)\)。

重新审视我们的流程,发现维护这条路径只是为了边权,根本不需要维护这条路径。有用的是堆栈中添加到虚拟树的所有点。我们每弹出一个点,就用各种树数据结构计算路径信息作为边权,也就是。

可. 假设求路径信息的复杂度是 \(t\), 有 \(k\) 个关键点, 那么复杂度可以优化到 \(O(k(\log n + t))\).

代码实现

我们用倍增求 LCA, 顺便求路径最小值. 可以做到 \(O((n + \sum k)\log n)\). 代码还是很清晰的, 调完了样例就过了, 好久没有一遍过的感觉了.

这是我第一次写虚树, 所以代码还没有那么成熟.

unsigned m, n;
unsigned A, B, C, D, t;
unsigned Cnt(0), Ans(0), Tmp(0);
struct Tree {
  vector<pair<Tree*, unsigned> > E;
  Tree* Fa[19];
  unsigned Min[19], Dep, DFSr;
  inline void DFS() {
    DFSr = ++Cnt, memset(Min + 1, 0x3f, 72);
    for (unsigned i(0); Fa[i]; ++i)
      Fa[i + 1] = Fa[i]->Fa[i], Min[i + 1] = min(Min[i], Fa[i]->Min[i]);
    for (auto i:E) if(Fa[0] != i.first) 
      i.first->Dep = Dep + 1, i.first->Fa[0] = this, i.first->Min[0] = i.second, i.first->DFS();
  }
  inline unsigned Qry(Tree* Ac) {
    Tree* x(this);
    unsigned Rt(0x3f3f3f3f);
    for (unsigned i(17); ~i; --i)
      if((x->Fa[i]) && (x->Fa[i]->Dep >= Ac->Dep)) Rt = min(Rt, x->Min[i]), x = x->Fa[i];
    return Rt;
  }
}T[250005];
inline Tree* LCA(Tree* x, Tree* y) {
  if(x->Dep < y->Dep) swap(x, y);
  for (unsigned i(17); ~i; --i) 
    if((x->Fa[i]) && (x->Fa[i]->Dep >= y->Dep)) x = x->Fa[i];
  if(x == y) return x;
  for (unsigned i(17); ~i; --i)
    if(x->Fa[i] != y->Fa[i]) x = x->Fa[i], y = y->Fa[i];
  return x->Fa[0];
}
struct Node {
  vector<Node*> Son;
  Tree* Ori;
  unsigned long long f;
  unsigned ToFa;
  inline const char operator< (const Node& x) const {return Ori->DFSr < x.Ori->DFSr;}
  inline void AddSon(Node* x) {
    Son.push_back(x);
    x->ToFa = x->Ori->Qry(this->Ori);
  }
  inline void DFS() {
    for (auto i:Son) i->DFS(), f += min((unsigned long long)i->ToFa, i->f);
  }
}N[250005], *Stack[250005], *CntN(N), **STop(Stack);
signed main() {
  n = RD();
  for (unsigned i(1); i < n; ++i) {
    A = RD(), B = RD(), C = RD();
    T[A].E.push_back({T + B, C});
    T[B].E.push_back({T + A, C});
  }
  T[1].Min[0] = 0x3f3f3f3f, T[1].Dep = 1, T[1].DFS(), m = RD();
  for (unsigned i(1); i <= m; ++i) {
    while (CntN > N) (CntN--)->Son.clear();
    A = RD(), CntN = A + N + 1, STop = Stack;
    for (unsigned j(1); j <= A; ++j) 
      N[j].f = 0x3f3f3f3f3f3f3f3f, N[j].Ori = T + RD(), N[j].Son.clear(), N[j].ToFa = 0;
    N[++A].Ori = T + 1, N[A].f = 0, sort(N + 1, N + A + 1), *(++STop) = N + 1;
    for (unsigned j(2); j <= A; ++j) {
      Tree* Lca(LCA(N[j].Ori, N[j - 1].Ori));
      while((STop > Stack + 1) && ((*(STop - 1))->Ori->Dep >= Lca->Dep))
        (*(STop - 1))->AddSon(*STop), --STop;
      Tree* Top((*STop)->Ori);
      if (Top == Lca) {*(++STop) = N + j; continue;}
      Node* Cur(++CntN);
      Cur->Ori = Lca, Cur->f = 0;
      if (Top->Dep > Lca->Dep) Cur->AddSon(*(STop--));
      *(++STop) = Cur, *(++STop) = N + j;
    }
    while (STop > Stack + 1) (*(STop - 1))->AddSon(*STop), --STop;
    N[1].DFS();
    printf("%llu\n", N[1].f);
  }
  return Wild_Donkey;
}
Link to comment
Share on other sites