【专题】虚树

这种东西想到要用很容易，关键是建完虚树后怎么做。

虚树题的特征为多次询问且出现$\sum M \le 10^5$一类的数据范围。

如果题目给出的是一张图而不是一棵树，可以思考是否能够结合圆方树等算法转化为虚树。

对于每次询问，将询问的节点和其在原树上的$LCA$单独建出来$dp$即可。

题目

P2495 消耗战题解
P4606 战略游戏题解
P3233 世界树题解
CF1320E Treeland and Viruses 题解
CF639F Bear and Chemistry 题解
sol-loj6184

模版代码

void buildvtr() {
    sort(s + 1, s + k + 1, [](int x, int y) { return id[x] < id[y]; });
    sta[top = 1] = 1, vtr.head[1] = -1, vtr.tot = 0;
    for (int i = 1; i <= k; ++i) {
        if (s[i] == 1) continue;
        int l = lca(sta[top], s[i]);
        while (id[l] <= id[sta[top - 1]]) add_vedge(sta[top - 1], sta[top]), --top;
        if (sta[top] != l) vtr.head[l] = -1, add_vedge(l, sta[top]), sta[top] = l;
        vtr.head[s[i]] = -1, sta[++top] = s[i];
    }
    for (int i = 1; i < top; ++i)
        add_vedge(sta[i], sta[i + 1]);
}