洛谷P2495 [SDOI2011] 消耗战题解

题目链接：P2495 [SDOI2011] 消耗战

题意：

在一场战争中，战场由 \(n\) 个岛屿和 \(n-1\) 个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为 \(1\) 的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他 \(k\) 个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。

侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到 \(1\) 号岛屿上）。不过侦查部门还发现了这台机器只能够使用 \(m\) 次，所以我们只需要把每次任务完成即可。

输入格式：

第一行一个整数 \(n\)，表示岛屿数量。

接下来 \(n-1\) 行，每行三个整数 \(u,v,w\) ，表示 \(u\) 号岛屿和 \(v\) 号岛屿由一条代价为 \(w\) 的桥梁直接相连。

第 \(n+1\) 行，一个整数 \(m\) ，代表敌方机器能使用的次数。

接下来 \(m\) 行，第 \(i\) 行一个整数 \(k_i\) ，代表第 \(i\) 次后，有 \(k_i\) 个岛屿资源丰富。接下来 \(k_i\) 个整数 \(h_1,h_2,..., h_{k_i}\) ，表示资源丰富岛屿的编号。

输出格式：

输出共 \(m\) 行，表示每次任务的最小代价。

数据范围：

\(2\leq n \leq 2.5\times 10^5, 1\leq m\leq 5\times 10^5\)

\(1\le \sum k_i \leq 5\times 10^5, 1\leq k_i< n, h_i\neq 1, 1\leq u,v\leq n, 1\leq w\leq 10^5\) 。

本题是虚树的模板题，~~然后咕咕咕了好久才来写~~（

考虑设 \(f_u\) 表示使得节点 \(u\) 的子树中没有关键点与 \(u\) 相连的最小花费，那么答案就是 \(f_1\) 。

考虑转移。枚举 \(u\) 的儿子 \(v\) ，

若 \(v\) 是关键点，则 \((u,v)\) 必须切断，有 \[ f_u \gets f_u + w(u,v) \]
若 \(v\) 不是关键点，则 \((u,v)\) 可以切断，也可以把 \(v\) 的全切了，有 \[ f_u \gets f_u + \min\{w(u,v),~f_v\} \]

直接暴力转移的话是 \(\mathcal{O}(nq)\) 的。

注意到关键点的总数 \(\sum k_i\) 与 \(n\) 同阶，因此考虑将整棵树进行“压缩”，仅保留必要的点。

怎么压缩呢？显然所有的关键点必须要保留。

并且因为要保持树的结构，所以关键点的 LCA 也需要保留。

那么对于下图的情况（绿色的点是 LCA ，红色的点是关键点）

我们要求的压缩后的树就长这样

考虑将所有关键点先按 dfs 序排序，这样我们可以用一个栈来维护构建的过程。

提示：实际上这是一个单调栈，栈中的元素满足 dfs 序单调，栈顶的 dfs 序最大。

每次加入一个新的关键点时，我们求一下栈顶元素和它的 LCA ，记为 \(p\) ，

若 \(p\) 就是栈顶元素，则栈顶元素和当前点位于树上的一条链中，直接加入栈中即可。
若 \(p\) 不是栈顶元素，则不停弹栈，直到当前点的 dfs 序比栈顶下面那个元素的 dfs 序小
- 此时若 \(p\) 是栈顶，直接将当前点入栈即可
- 否则 \(p\) 一定不在栈中，且在原树中位于栈顶下面那个元素到栈顶的链上
  
  这种情况考虑将栈顶弹出，然后将 \(p\) 和关键点入栈即可。

然后弹栈的时候（注意不是入栈的时候）连一下边就好了。

这样整棵树的节点数至多有 \(2k_i-1\) 个点（二叉树的情况）

时间复杂度 \(\mathcal{O}(n\log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(5e5 + 15))

struct Gragh
{
    int pos = 1, head[N];
    struct Edge { int v, w, next; } e[N * 2];
    void addEdge(int u, int v, int w) { e[++pos] = {v, w, head[u]}; head[u] = pos; }
} g1, g2;
set<int> st;
int mn_w, a[N], dfn[N], dep[N];
int dp[N], dis[N], fa[20][N], mn[20][N];
void dfs1(int u, int f)
{
    static int tim = 0; dfn[u] = ++tim;
    dep[u] = dep[f] + 1; fa[0][u] = f;
    rep(i, 1, 19)
    {
        fa[i][u] = fa[i - 1][fa[i - 1][u]];
        down(mn[i][u] = mn[i - 1][u], mn[i - 1][fa[i - 1][u]]);
    }
    for(int i = g1.head[u]; i; i = g1.e[i].next)
    {
        int v = g1.e[i].v, w = g1.e[i].w;
        if(v != f) { dis[v] = dis[u] + w; mn[0][v] = w; dfs1(v, u); }
    }
}
int getlca(int x, int y)
{
    mn_w = INF; if(dep[x] < dep[y]) swap(x, y);
    Rep(i, 19, 0) if(dep[x] >= dep[y] + (1 << i)) { down(mn_w, mn[i][x]); x = fa[i][x]; }
    if(x == y) return x;
    Rep(i, 19, 0) if(fa[i][x] != fa[i][y]) { 
        down(mn_w, min(mn[i][x], mn[i][y])); x = fa[i][x]; y = fa[i][y];
    } return fa[0][x];
}
void dfs2(int u)
{
    dp[u] = 0;
    for(int i = g2.head[u]; i; i = g2.e[i].next)
    {
        int v = g2.e[i].v, w = g2.e[i].w; dfs2(v);
        if(st.count(v)) dp[u] += w; else dp[u] += min(dp[v], w); 
    }
}
void solve()
{
    st.clear(); int k; cin >> k;
    rep(i, 1, k) { cin >> a[i]; st.insert(a[i]); }
    sort(a + 1, a + 1 + k, [](int x, int y) { return dfn[x] < dfn[y]; });
    static int top, stk[N]; stk[top = 1] = 1; g2.head[1] = 0;
    rep(i, 1, k)
    {
        int lca = getlca(a[i], stk[top]);
        if(lca != stk[top])
        {
            while(dfn[lca] < dfn[stk[top - 1]])
            {
                int u = stk[top - 1], v = stk[top];
                getlca(u, v); g2.addEdge(u, v, mn_w); --top;
            }
            if(dfn[lca] > dfn[stk[top - 1]])
            {
                getlca(lca, stk[top]); g2.head[lca] = 0;
                g2.addEdge(lca, stk[top], mn_w); stk[top] = lca;
            }else
            {
                int u = stk[top - 1], v = stk[top];
                getlca(u, v); g2.addEdge(u, v, mn_w); --top;
            }
        }
        g2.head[a[i]] = 0; stk[++top] = a[i];
    }
    while(top > 1)
    {
        int u = stk[top - 1], v = stk[top];
        getlca(u, v); g2.addEdge(u, v, mn_w); --top;
    }
    dfs2(1); cout << dp[1] << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    rep(i, 1, n - 1)
    {
        static int u, v, w; cin >> u >> v >> w;
        g1.addEdge(u, v, w); g1.addEdge(v, u, w);
    }
    dfs1(1, 0); int q; cin >> q; while(q--) solve();
    return 0;
}