傲慢让别人无法来爱我, 偏见让我无法去爱别人

定义

…这玩意真是没啥好说的…就是有一种树上问题 每次询问和很多点都有关系, 但是这些点数的总和不会很大, 然后我们就要搞一个和这些点的和相关的算法

虚树说白了还是信息的压缩 把与询问无关的东西统统略掉:

  • 保留询问点: 因为你要回答询问
  • 保留询问点之间的LCA: 因为你要保留这棵树的一些结构上的性质

然后就直接在新树上想怎么搞怎么搞就完事了

构造

构建一次虚树的复杂度是$\text{询问点个数} \times \text{求出询问点之间LCA的复杂度}$

具体来说 询问点按照DFS序排序, 然后从后向前求出LCA(说白了就是从低到高求LCA), 把询问点和LCA一起按照DFS序排序, 按照祖孙关系连就完事了

一开始抄的hzwer大爷的代码然后发现痛不欲生 具体实现抄的yyb大爷的代码

bool cmp(int x, int y) { return son[x].first < son[y].first; }
stack<int> gary, bh;
void solve() {
    cntb = 0;
    sort(h + 1, h + h[0] + 1, cmp);
    for (int i = h[0]; i > 1; i--)
        h[++h[0]] = lca(h[i], h[i - 1]);
    h[++h[0]] = 1;
    sort(h + 1, h + h[0] + 1, cmp);
    h[0] = unique(h + 1, h + h[0] + 1) - h - 1;
    while (!gary.empty()) gary.pop();
    for (int i = 1; i <= h[0]; i++) {
        while (!gary.empty() && son[gary.top()].second < son[h[i]].first) gary.pop();
        if (!gary.empty())
            adn(gb, b, cntb, gary.top(), h[i], 0);
        gary.push(h[i]);
    }
    printf("%lld\n", dp(1));
}

几道例题

[Sdoi2011]消耗战

喜闻乐见的又双叒叕开小空间了

/**************************************************************
    Problem: 2286
    User: Cansult
    Language: C++
    Result: Accepted
    Time:8488 ms
    Memory:104192 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define LL long long
#define pii pair<int, int>
#define MAXN (500000 + 5)
#define INF (0x7ffffffffffffll)
#define MAXL (25 + 5)
using namespace std;
struct edg {
    int from, to, next, cost;
} b[MAXN], e[MAXN << 1];
const int lgn = 24;
int gb[MAXN], cntb, ge[MAXN], cnte, n, q, h[MAXN], cnta, deep[MAXN], d[MAXN][MAXL];
LL f[MAXN], premin[MAXN];
pii son[MAXN];
bool ist[MAXN];
void adn(int* gx, edg* bx, int& cntx, int from, int to, int cost) {
    bx[++cntx].next = gx[from];
    bx[cntx].from = from, bx[cntx].to = to, bx[cntx].cost = cost;
    gx[from] = cntx;
}
void init(int dq) {
    son[dq].first = ++cnta;
    deep[dq] = deep[d[dq][0]] + 1;
    for (int i = 1; i <= lgn; i++)
        d[dq][i] = d[d[dq][i - 1]][i - 1];
    for (int i = ge[dq]; i; i = e[i].next)
        if (e[i].to != d[dq][0])
            premin[e[i].to] = min(premin[dq], (LL)e[i].cost), d[e[i].to][0] = dq, init(e[i].to);
    son[dq].second = cnta;
}
int lca(int x, int y) {
    if (deep[x] < deep[y]) swap(x, y);
    for (int i = lgn; i >= 0; i--)
        if (deep[d[x][i]] >= deep[y])
            x = d[x][i];
    if (x == y) return x;
    for (int i = lgn; i >= 0; i--)
        if (d[x][i] != d[y][i])
            x = d[x][i], y = d[y][i];
    return d[x][0];
}
bool cmp(int x, int y) { return son[x].first < son[y].first; }
LL dp(int dq) {
    f[dq] = premin[dq];
    LL re = 0;
    for (int i = gb[dq]; i; i = b[i].next)
        re += dp(b[i].to);
    if (re && !ist[dq]) f[dq] = min(f[dq], re);
    gb[dq] = 0;
    return f[dq];
}
stack<int> gary, bh;
void solve() {
    cntb = 0;
    sort(h + 1, h + h[0] + 1, cmp);
    for (int i = h[0]; i > 1; i--)
        h[++h[0]] = lca(h[i], h[i - 1]);
    h[++h[0]] = 1;
    sort(h + 1, h + h[0] + 1, cmp);
    h[0] = unique(h + 1, h + h[0] + 1) - h - 1;
    while (!gary.empty()) gary.pop();
    for (int i = 1; i <= h[0]; i++) {
        while (!gary.empty() && son[gary.top()].second < son[h[i]].first) gary.pop();
        if (!gary.empty())
            adn(gb, b, cntb, gary.top(), h[i], 0);
        gary.push(h[i]);
    }
    printf("%lld\n", dp(1));
}
int main() {
    scanf("%d", &n);
    for (int i = 1, srx, sry, src; i < n; i++) {
        scanf("%d%d%d", &srx, &sry, &src);
        adn(ge, e, cnte, srx, sry, src);
        adn(ge, e, cnte, sry, srx, src);
    }
    premin[1] = INF;
    init(1);
    scanf("%d", &q);
    memset(ist, false, sizeof(ist));
    for (int i = 1; i <= q; i++) {
        scanf("%d", &h[0]);
        for (int j = 1; j <= h[0]; j++)
            scanf("%d", &h[j]), ist[h[j]] = true, bh.push(h[j]);
        solve();
        while (!bh.empty()) ist[bh.top()] = false, bh.pop();
    }
    return 0;
}

[Hnoi2014]世界树

一开始想的是分类讨论: 把虚树上的点分成"询问点"和"询问点的LCA"

  • 对于询问点和询问点之间的边可以直接计算然后更新答案
  • 对于询问点和LCA之间的边可以到LCA上遍历一下也可以统计
  • 但是对于LCA和LCA之间的点我就懵逼了 因为遍历的复杂度就GG了 然后gayge表示我是个沙茶并且告诉我可以在构建虚树的时候就预处理出来每个LCA是被哪个点管辖的 我感觉肥肠厉害
// 咕咕咕

[Heoi2014]大工程

考虑一次询问怎么搞

路径和: 枚举每条边然后看ta两边有多少个点乘起来就完事了

路径最大/最小值: 记录每个点能延伸的最大/小深度和第二大/小深度, 在LCA和询问点上分类搞一搞就完事了

写起来真鸡儿丢人…复制的时候没改全…然后又复制到别的地方…总之就是一团糟…

然后忘了最大值还可能在询问点上更新的情况…GG

/**************************************************************
    Problem: 3611
    User: Cansult
    Language: C++
    Result: Accepted
    Time:11392 ms
    Memory:236836 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define INF (100000000000000000ll)
#define MAXN (1000000 + 5)
#define MAXL (20 + 5)
#define LL long long
#define pii pair<int, int>
using namespace std;
struct edg {
    int from, to, next, cost;
} b[MAXN], e[MAXN << 1];
const int lgn = 23;
int gb[MAXN], ge[MAXN], cntb, cnte, n, q, deep[MAXN], h[MAXN], d[MAXN][MAXL], cnta, size[MAXN], tn;
LL cdeep[MAXN], maxdeep[MAXN], max2deep[MAXN], mindeep[MAXN], min2deep[MAXN];
pii son[MAXN];
bool ish[MAXN];
void adn(int* gx, edg* bx, int& cntx, int from, int to, int cost) {
    bx[++cntx].next = gx[from];
    bx[cntx].from = from, bx[cntx].to = to, bx[cntx].cost = cost;
    gx[from] = cntx;
}
void init(int dq) {
    son[dq].first = ++cnta;
    deep[dq] = deep[d[dq][0]] + 1;
    for (int i = 1; i <= lgn; i++)
        d[dq][i] = d[d[dq][i - 1]][i - 1];
    for (int i = ge[dq]; i; i = e[i].next)
        if (e[i].to != d[dq][0]) {
            cdeep[e[i].to] = cdeep[dq] + e[i].cost;
            d[e[i].to][0] = dq;
            init(e[i].to);
        }
    son[dq].second = cnta;
}
int lca(int x, int y) {
    if (deep[x] < deep[y]) swap(x, y);
    for (int i = lgn; i >= 0; i--)
        if (deep[d[x][i]] >= deep[y])
            x = d[x][i];
    if (x == y) return x;
    for (int i = lgn; i >= 0; i--)
        if (d[x][i] != d[y][i])
            x = d[x][i], y = d[y][i];
    return d[x][0];
}
LL sumc, maxc, minc;
stack<int> gary;
void dfs(int dq) {
    size[dq] = ish[dq];
    maxdeep[dq] = max2deep[dq] = 0;
    mindeep[dq] = min2deep[dq] = INF;
    for (int i = gb[dq]; i; i = b[i].next) {
        dfs(b[i].to);
        sumc += (LL)b[i].cost * (tn - size[b[i].to]) * size[b[i].to], size[dq] += size[b[i].to];
        if (maxdeep[b[i].to] + b[i].cost > maxdeep[dq])
            max2deep[dq] = maxdeep[dq], maxdeep[dq] = maxdeep[b[i].to] + b[i].cost;
        else if (maxdeep[b[i].to] + b[i].cost > max2deep[dq])
            max2deep[dq] = maxdeep[b[i].to] + b[i].cost;

        if (mindeep[b[i].to] + b[i].cost < mindeep[dq])
            min2deep[dq] = mindeep[dq], mindeep[dq] = mindeep[b[i].to] + b[i].cost;
        else if (mindeep[b[i].to] + b[i].cost < min2deep[dq])
            min2deep[dq] = mindeep[b[i].to] + b[i].cost;
    }
    if (ish[dq]) {
        minc = min(minc, mindeep[dq]);
        min2deep[dq] = mindeep[dq] = 0;
        maxc = max(maxc, maxdeep[dq]);
        if (maxdeep[dq] && max2deep[dq])
            maxc = max(maxc, maxdeep[dq] + max2deep[dq]);
    }
    else {
        if (mindeep[dq] < INF && min2deep[dq] < INF)
            minc = min(minc, mindeep[dq] + min2deep[dq]);
        if (maxdeep[dq] && max2deep[dq])
            maxc = max(maxc, maxdeep[dq] + max2deep[dq]);
    }
}
bool cmp(int x, int y) { return son[x].first < son[y].first; }
void solve() {
    cntb = 0;
    sort(h + 1, h + h[0] + 1, cmp);
    for (int i = h[0]; i > 1; i--)
        h[++h[0]] = lca(h[i], h[i - 1]);
    h[++h[0]] = 1;
    sort(h + 1, h + h[0] + 1, cmp);
    h[0] = unique(h + 1, h + h[0] + 1) - h - 1;
    while (!gary.empty())
        gary.pop();
    for (int i = 1; i <= h[0]; i++) {
        while (!gary.empty() && son[gary.top()].second < son[h[i]].first) gary.pop();
        if (!gary.empty()) adn(gb, b, cntb, gary.top(), h[i], cdeep[h[i]] - cdeep[gary.top()]);
        gary.push(h[i]);
    }
    sumc = 0, maxc = 0, minc = INF;
    dfs(1);
    printf("%lld %lld %lld\n", sumc, minc, maxc);
    for (int i = 1; i <= h[0]; i++)
        ish[h[i]] = gb[h[i]] = size[h[i]] = 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 1, srx, sry, src = 1; i < n; i++)
        scanf("%d%d", &srx, &sry), adn(ge, e, cnte, srx, sry, src), adn(ge, e, cnte, sry, srx, src);
    d[1][0] = 1;
    init(1);
    scanf("%d", &q);
    memset(ish, false, sizeof(ish));
    for (int i = 1; i <= q; i++) {
        scanf("%d", &h[0]);
        tn = h[0];
        for (int j = 1; j <= h[0]; j++)
            scanf("%d", &h[j]), ish[h[j]] = true;
        solve();
    }
    return 0;
}

By 准备退役旅游的 Cansult