虚树 - Veibae CN

Virtual Tree

虚 🌳

P2495

大概的意思时有一棵 $n$ 个节点的树， $m$ 次询问，断一条边需要花费相应的费用，每次询问 $k$ 个点使一号节点和它们不连通最少的代价，断的边不会继承到下一次询问。

$n \leqslant 2.5 \times 10^5,\ m \leqslant 5 \times 10^5, \sum k \leqslant 5 \times 10^5$

首先我们可以树形dp， $f[i]$ 表示切断以 $i$ 为根的子树中所有询问点的代价， $c[i]$ 表示 $u$

到1号节点路径上边权的最小值。

当点 $u$ 本身是询问点时， $f[u] = c[u]$ ，否则 $f[u] = min(c[u], \sum f[v]),v \in son(u)$

最后答案为 $f[1]$ ，时间复杂度 $O(nm)$ ，肯定过不去，但是我们发现有些点根本没必要跑

比如说子树内一个询问点都没有的节点，所以考虑优化这棵树。

建虚树

首先每次询问点时必须要保留的，而又要不改变节点的辈分关系，还要让节点数尽量少

所以我们把询问点和它们两两之间的 LCA 保留，但是我们也不能 $k^2$ 枚举询问点的LCA

所以用单调栈的思想，维护树上的一条链，DFS 序单调递增

先预处理 $dfs$ 序，然后将询问点按 $dfs$ 序排序，开始先将第一个点加入栈中

$u$ 表示当前要加入的点， $lca$ 表示 $u$ 与栈顶的 $lca$

分为两种情况

栈顶就是 $lca$ ，说明栈顶与 $u$ 在一条链上，直接把 $u$ j加入栈
栈顶不是 $lca$ ，弹出栈顶直到 $u$ 与栈顶在一条链上，也就是说跳到 dfn 序大于栈顶

Code

#include <bits/stdc++.h>
#define ll long long
#define cjb 1145141919810
#define MAXN 250005
#define V Vshojo
using namespace std;
int n, m, k;
int a[MAXN];
int vis[MAXN];

#define pir pair <int, ll>
#define dis second
#define to first
vector <pir> e[MAXN];
vector <int> Vshojo[MAXN];

ll c[MAXN];
int T;
int fa[MAXN], siz[MAXN], dep[MAXN];
int son[MAXN], top[MAXN], dfn[MAXN];
void dfs1(int u, int dad)
{
    dfn[u] = ++T;
    siz[u] = 1; fa[u] = dad; dep[u] = dep[dad] + 1;
    for(pir y : e[u])
    {
        int v = y.to;
        if(v == dad) continue;
        
        c[v] = min(c[u], y.dis); 
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int tup)
{
    top[u] = tup;
    if(son[u]) dfs2(son[u], tup);
    for(pir y : e[u])
    {
        int v = y.to;
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
int LCA(int u, int v)
{
    while(top[u] != top[v])
    {
        if(dep[top[u]] >= dep[top[v]])
            u = fa[top[u]];
        else
            v =  fa[top[v]];
    } 
    return dep[u] < dep[v] ? u : v;
}

bool cmp(int a, int b)
{
    return dfn[a] < dfn[b];
}
void build()
{
    int sta[MAXN], top = 0;
    sort(a + 1, a + 1 + k, cmp);
    
    sta[++top] = 1;
    for(int i = 1; i <= k; i++)
    {
        int lca = LCA(a[i], sta[top]);
        if(lca != sta[top])
        {
            while(dfn[lca] < dfn[sta[top-1]])
            {
                V[sta[top]].push_back(sta[top-1]);
                V[sta[top-1]].push_back(sta[top]);
                top--;
            }
            V[lca].push_back(sta[top]);
            V[sta[top]].push_back(lca);
            
            
            if(dfn[sta[top-1]] != dfn[lca]) sta[top] = lca;
            else top--;
        }
        sta[++top] = a[i];
    }
    for(int i = 1; i < top; i++)
    {
        V[sta[i]].push_back(sta[i+1]);
        V[sta[i+1]].push_back(sta[i]);
    }
}

ll dp(int u, int fa)
{
    ll ans = 0;
    for(int v : V[u])
    {
        if(v ==  fa) continue;
        ll s = dp(v, u);
        if(vis[v])
        ans += c[v], vis[v] = 0;
        else
        ans += min(c[v], s);
    }
    V[u].clear();
    return ans;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i < n; i++)
    {
        int u, v; ll w;
        scanf("%d%d%lld", &u, &v, &w);
        e[u].push_back(make_pair(v, w));
        e[v].push_back(make_pair(u, w));
    }
    c[1] = cjb; dfs1(1, 0); dfs2(1, 1);
    
    scanf("%d", &m);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d", &k);
        for(int j = 1; j <= k; j++)
        scanf("%d", &a[j]), vis[a[j]] = 1;
        
        build();
        printf("%lld\n",dp(1, 0));
    }
    
    return 0;
}