虚树讲解

虚树

前言

在一些树形dp的题目中，有的题目会出现关键点的要求，此时数据范围会和询问的总个数有关，这类问题每次跑一边树形dp复杂度不优，虚树可以将复杂度降至$O(\sum k_i)$，来解决问题。

正文

虚树

虚树其实就是对于每次询问，只保留了有用的关键节点建出来的树形结构，可以有效的降低时间复杂度。

虚树的构建

假设我们现在有$k$个关键点，对其建成一棵虚树的操作如下。

• 将关键点按dfs序排序
• 遍历一遍，求出相邻两个关键点的LCA
• 根据原树中的节点关系建树

这个过程可以使用单调栈来实现。

首先将根节点加入单调栈中，按dfs序排序后逐个加入当前询问中的关键点，假设当前加入的点为$k_i$，先求出$k_i$和当前栈顶的LCA，如果当前的栈顶元素和求出的LCA不同，说明新加入的元素不在当前的子树中，我们需要按dfs序找到LCA在栈中的位置，将dfs序大于LCA的弹出栈同时进行连边操作。如果LCA不在栈中需要将其加入栈中，最后加入当前节点，处理完后，还需要将最后栈中存下的节点之间建好边。

通过上述过程，不难看出栈中维护的是一条到栈顶元素的链，建好虚树后，就可以在上面dp了，时间复杂度$O(\sum(k \log k + k \log n))$。

代码如下，

bool cmp(int x, int y)
{
    return dfn[x] < dfn[y];
}

void insert(int x)
{
    if(st[top] == x)return;
    int lca = LCA(x, st[top]);
    if(lca != st[top])
    {
        while(dfn[lca] < dfn[st[top - 1]])
            add(st[top - 1], st[top]), top--;
        if(dfn[lca] > dfn[st[top - 1]])
            add(lca, st[top]), st[top] = lca;
        else add(lca, st[top--]);
    }
    st[++top] = x;
}

void build(int n)
{
    sort(k + 1, k + n + 1, cmp);
    st[++top] = 1;
    for(int i = 1; i <= n; i++)
        insert(k[i]);
    for(int i = 1; i < top; i++)
        add(st[i], st[i + 1]);
}

说实话我不会五行建虚树。

应用

P2495 消耗战

首先考虑转移方程不难得到，设$f_x$表示使$x$不与其子树中任意一个关键点连通的最小代价，枚举其子节点，

• 若$v$是关键点，$f_x = f_x + w(x, v)$
• 若$v$不是关键点，$f_x = f_x + \min\{f_v, w(x, v)\}$

这样每次跑一遍是$O(nq)$的，考虑每次建出虚树来直接在虚树上转移即可优化复杂度。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2.5e5 + 10;
const int M = 5e5 + 10;
const int INF = 1e15;

int n, m;
int cnt, head[N];
struct edge{
    int to, nxt, cost;
    edge(int _v = 0, int _n = 0, int _c = 0): to(_v), nxt(_n), cost(_c) {}
}e[M << 1];

void add(int u, int v, int c)
{
    e[++cnt] = edge(v, head[u], c);
    head[u] = cnt;
}

int tot;
int siz[N], fa[N], top[N], son[N], depth[N], id[N];
int Min[N];

void dfs1(int x, int father)
{
    siz[x] = 1;
    fa[x] = father;
    depth[x] = depth[father] + 1;
    int maxs = -1;
    for(int i = head[x]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        int c = e[i].cost;
        if(v == father)continue;
        Min[v] = min(Min[x], c);
        dfs1(v, x);
        siz[x] += siz[v];
        if(siz[v] > maxs)
            maxs = siz[v], son[x] = v;
    }
}

void dfs2(int x, int topfather)
{
    id[x] = ++tot;
    top[x] = topfather;
    if(!son[x])return;
    dfs2(son[x], topfather);
    for(int i = head[x]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa[x] || v == son[x])continue;
        dfs2(v, v);
    }
}

int LCA(int x, int y)
{
    while(top[x] != top[y])
    {
        if(depth[top[x]] < depth[top[y]])
            swap(x, y);
        x = fa[top[x]];
    }
    if(depth[x] > depth[y])swap(x, y);
    return x;
}

int st[N];
vector<int> v[N];

void calc(int x)
{
    if(tot == 1)
    {
        st[++tot] = x;
        return;
    }
    int lca = LCA(x, st[tot]);
    if(lca == st[tot])return;
    while(tot > 1 && id[st[tot-1]] >= id[lca])
    {
        v[st[tot-1]].push_back(st[tot]);
        tot--;
    }
    if(st[tot] != lca)
    {
        v[lca].push_back(st[tot]);
        st[tot] = lca;
    }
    st[++tot] = x;
}

int dp(int x)
{
    if(!v[x].size())return Min[x];
    int sum = 0;
    for(int i = 0; i < v[x].size(); i++)
        sum += dp(v[x][i]);
    v[x].clear();
    return min(Min[x], sum);
}

int a[N];

bool cmp(int x, int y)
{
    return id[x] < id[y];
}

signed main()
{
    scanf("%lld", &n);
    for(int i = 1; i < n; i++)
    {
        int x, y, z;
        scanf("%lld%lld%lld", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    Min[1] = INF;
    dfs1(1, 0);
    dfs2(1, 1);
    int T;
    tot = 0;
    scanf("%lld", &T);
    while(T--)
    {
        int m;
        scanf("%lld", &m);
        for(int i = 1; i <= m; i++)
            scanf("%lld", &a[i]);
        sort(a+1, a+m+1, cmp);
        st[++tot] = 1;
        for(int i = 1; i <= m; i++)calc(a[i]);
        while(tot)
        {
            v[st[tot-1]].push_back(st[tot]);
            tot--;
        }
        printf("%lld\n", dp(1));
    }
    return 0;
}

CF613D Kingdom and its Cities

首先考虑如何转移，显然就是分一下情况设$f_x$表示让以$x$的子树中询问点不连通的最少花费，$g_x$表示当前子树中还有多少个需要断开的询问点

• 当前点是询问点时，$f_x = f_x + g_x, g_x = 1$
• 当前点不是询问点时，$f_x = f_x + 1, g_x = 0$

然后建出虚树转移即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, q;

int k[N], b[N];

int cnt, head[N];

struct edge
{
    int to, nxt;
    edge(int v = 0, int x = 0) : to(v), nxt(x) {}
};

edge e[N << 1];

void add(int u, int v)
{
    e[++cnt] = edge(v, head[u]); head[u] = cnt;
    e[++cnt] = edge(u, head[v]); head[v] = cnt;
}

int tim, dfn[N];

int depth[N], top[N], son[N], siz[N], fa[N];

void dfs1(int x, int father)
{
    dfn[x] = ++tim;
    fa[x] = father;
    depth[x] = depth[fa[x]] + 1;
    siz[x] = 1;
    for(int i = head[x]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa[x])continue;
        dfs1(v, x);
        siz[x] += siz[v];
        if(siz[v] > siz[son[x]])
            son[x] = v;
    }
}

void dfs2(int x, int topfather)
{
    top[x] = topfather;
    if(!son[x])return;
    dfs2(son[x], topfather);
    for(int i = head[x]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa[x] || v == son[x])
            continue;
        dfs2(v, v);
    }
}

int LCA(int x, int y)
{
    while(top[x] != top[y])
    {
        if(depth[top[x]] < depth[top[y]])
            swap(x, y);
        x = fa[top[x]];
    }
    if(depth[x] > depth[y])
        swap(x, y);
    return x;
}

int st[N], t;

int f[N], h[N], c[N];

vector <int> g[N];

void link(int x, int y)
{
    g[x].push_back(y);
}

void clear(int x)
{
    f[x] = h[x] = c[x] = 0;
    g[x].clear();
}

void insert(int x)
{
    if(st[t] == x)return;
    int lca = LCA(st[t], x);
    if(lca != st[t])
    {
        while(dfn[lca] < dfn[st[t - 1]])
            link(st[t - 1], st[t]), t--;
        if(dfn[lca] > dfn[st[t - 1]])
            clear(lca), link(lca, st[t]), st[t] = lca;
        else link(lca, st[t--]);
    }
    st[++t] = x; clear(x);
}

bool cmp(int x, int y)
{
    return dfn[x] < dfn[y];
}

void build(int n)
{
    sort(k + 1, k + n + 1, cmp);
    t = 0; st[++t] = 1; clear(1);
    for(int i = 1; i <= n; i++)
        insert(k[i]);
    for(int i = 1; i < t; i++)
        link(st[i], st[i + 1]);
}

void dp(int x, int fa)
{
    for(auto v : g[x])
    {
        dp(v, x);
        f[x] += f[v];
        h[x] += h[v];
    }
    if(f[x] == -1)return;
    if(b[x])f[x] += h[x], h[x] = 1;
    else if(h[x] > 1)f[x]++, h[x] = 0;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    dfs1(1, 0); dfs2(1, 0);
    scanf("%d", &q);
    for(int i = 1; i <= q; i++)
    {
        int m; scanf("%d", &m);
        for(int j = 1; j <= m; j++)
            scanf("%d", &k[j]), b[k[j]] = 1;
        bool flag = true;
        for(int j = 1; j <= m; j++)
        {
            if(b[fa[k[j]]] && k[j] != 1)
            {
                printf("-1\n");
                flag = false; break;
            }
        }
        if(flag){build(m); dp(1, 0);
                printf("%d\n", f[1]);}
        for(int j = 1; j <= m; j++)
            b[k[j]] = 0;
    }
    return 0;
}

后记

不算难，（难的是真的难。