虚树

[Ir1d]

https://oi-wiki.org/ds/virtual-tree/

[longlongzhu123]

orz学习了！有一个错别字：从小到<大>（在栈的那幅图下面）

[Ir1d]

@longlongzhu123 谢谢！欢迎开一个 pull request 帮忙改一下（

[nanatsuhi]

很棒呢OvO

[cszhengyh]

感觉直接拿另一个邻接表来存虚树就可 没必要删边哇

[avgstuBoboge]

引子题目的数据范围中，貌似没有声明 m 的上界。

[rsdbkhusky]

建立虚树的过程感觉和 Tarjan 求 Lca 有些异曲同工之处。

[lhq666juanlao]

%%%，不过似乎没有虚树规模的复杂度的证明？

[ArthasKonjaku]

虚树规模相当于初始关键点的两倍

[Alphaban07]

树形dp的状态转移左边是dp(v)吧

[Alphaban07]

右边

[SmallTualatin]

虚树建立，可以先按照 dfs 序排序，然后相邻两个做 LCA 算出所有的虚点，把虚点和关键点丢进去一起按照 dfs 序排序，再相邻两个 lca 向后一个连边即可，不用那么麻烦

[SmallTualatin]

另外，虚树大小应该是 O(关键点数) 级别的

[EndlessCheng]

图画得很不错！

[wchengk09]

最后那个 $DP(i)=DP(i)+w(i,v)$ 中， $w(i,v)$ 指的是什么？

[ArthasKonjaku]

指的是两点之间最短路径距离（可以发现两点存在祖先和后代关系，可以利用倍增在log时长内求出）

[JYRowe]

习题可以增加 ABC340G，CF1923E 也可以拿虚树做

[imarkzzz]

使用单调栈实现的，判断逻辑更简单，更贴近常规的单调栈风格。

// Query information
int numNodes, numQueries, numKeyNodes;
int keyNodes[MAX_NODES], isKeyNode[MAX_NODES];

// Virtual tree data
vector<int> virtualTree[MAX_NODES];
int stk[MAX_NODES], top;  // 栈

int buildVirtualTree()
{
    // 将询问点按照 dfs 序排序
    sort(keyNodes + 1, keyNodes + numKeyNodes + 1, [](int x, int y)
         { return dfn[x] < dfn[y]; });

    // 在虚树里，只要保证祖先后代的关系没有改变，就可以随意添加节点
    // 单调栈维护一条虚树上的链
    // 根节点入栈（哨兵节点，简化判断，并且不会影响答案）
    stk[top = 1] = 1;
    if (keyNodes[1] != 1) {
      stk[++top] = keyNodes[1];
    }

    // 按照 dfs 序从小到大添加询问点
    for (int i = 2; i <= numKeyNodes; ++i)
    {
        int lca = findLCA(stk[top], keyNodes[i]);
        // dfn 和 depth 均可
        // while (top > 1 && dfn[stk[top - 1]] >= dfn[lca]) {
        while (top > 1 && depth[stk[top - 1]] >= depth[lca]) {
          // stk[top] 和 keyNodes[i] 不在同一条链
          virtualTree[stk[top - 1]].push_back(stk[top]);
          top -= 1;
        }
        // dfn[stk[top - 1]] < dfn[lca] <= dfn[stk[top]]
        // depth[stk[top - 1]] < depth[lca] <= depth[stk[top]]
        if (lca != stk[top]) {  // 哨兵为根节点 1，所以必然有：top > 1
          // stk[top] 和 keyNodes[i] 不在同一条链
          virtualTree[lca].push_back(stk[top]);
          stk[top] = lca;  // top 出栈，lca 入栈
        }
        // 询问点入栈
        stk[++top] = keyNodes[i];
    }
    // 对最后一条链连边
    while (top > 1)
    {
      virtualTree[stk[top - 1]].push_back(stk[top]);
      top -= 1;
    }
    return 1;  // 返回虚树根节点
}

[imarkzzz]

关键点=询问点+两两的最近公共祖先+[树根]，这样定义比较不容易乱。第一种构造过程不一定会把树根放到虚树，第二种构造过程一定会把树根放到虚树。

[imarkzzz]

原树的树根不必入栈，作为虚树根节点的单调栈版本。单调栈最后出栈的一定是所有关键点中DFS序最小的，即所有节点的LCA。

int buildVirtualTree()
{
    // 将询问点按照 dfs 序排序
    sort(keyNodes + 1, keyNodes + numKeyNodes + 1, [](int x, int y)
         { return dfn[x] < dfn[y]; });

    // 在虚树里，只要保证祖先后代的关系没有改变，就可以随意添加节点
    // 单调栈维护一条虚树上的链
    stk[top = 1] = keyNodes[1];

    // 按照 dfs 序从小到大添加询问点
    for (int i = 2; i <= numKeyNodes; ++i)
    {
        int lca = findLCA(stk[top], keyNodes[i]);
        // dfn 和 depth 均可
        // while (top > 1 && dfn[stk[top - 1]] >= dfn[lca]) {
        while (top > 1 && depth[stk[top - 1]] >= depth[lca]) {
          // stk[top] 和 keyNodes[i] 不在同一条链
          virtualTree[stk[top - 1]].push_back(stk[top]);
          top -= 1;
        }
        // dfn[stk[top - 1]] < dfn[lca] <= dfn[stk[top]]
        // depth[stk[top - 1]] < depth[lca] <= depth[stk[top]]
        if (lca != stk[top]) {
          // stk[top] 和 keyNodes[i] 不在同一条链
          virtualTree[lca].push_back(stk[top]);
          stk[top] = lca;  // top 出栈，lca 入栈
        }
        // 询问点入栈
        stk[++top] = keyNodes[i];
    }
    // 对最后一条链连边
    while (top > 1)
    {
      virtualTree[stk[top - 1]].push_back(stk[top]);
      top -= 1;
    }
    return stk[1];  // 返回虚树根节点
}