[SDOI 2011]消耗战

时间：2023-03-09 14:44:52
[SDOI 2011]消耗战

Description

题库链接

给你一棵 \(n\) 个节点根节点为 \(1\) 的有根树，有边权。 \(m\) 次询问，每次给出 \(k_i\) 个关键点。询问切断一些边，使这些点到根节点不连通，最小的边权和。

\(2\leq n\leq 250000,1\leq m,\sum\limits_{i=1}^m k_i\leq 500000,1\leq k_i\leq n-1\)

Solution

在原树做一遍前缀的边权最小值，建好虚树后，简易的树形 \(DP\) 即可。

Code

//It is made by Awson on 2018.2.20

#include <bits/stdc++.h>

#define LL long long

#define dob complex<double>

#define Abs(a) ((a) < 0 ? (-(a)) : (a))

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

#define writeln(x) (write(x), putchar('\n'))

#define lowbit(x) ((x)&(-(x)))

using namespace std;

const int N = 250000;

const LL INF = 1e18;

void read(int &x) {

    char ch; bool flag = 0;

    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());

    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());

    x *= 1-2*flag;

}

void print(LL x) {if (x > 9) print(x/10); putchar(x%10+48); }

void write(LL x) {if (x < 0) putchar('-'); print(Abs(x)); }

int lst[N+5], flag[N+5]; LL minn[N+5], f[N+5];

int dfn[N+5], times, fa[N+5][20], dep[N+5];

int S[N+5], top, n, lim, u, v, c, t, k;

struct graph {

    struct tt {int to, next; LL cost; }edge[(N<<1)+5];

    int path[N+5], top;

    void add(int u, int v) {edge[++top].to = v, edge[top].next = path[u]; path[u] = top; }

    void add(int u, int v, LL c) {edge[++top].to = v, edge[top].cost = c, edge[top].next = path[u]; path[u] = top; }

    void dfs1(int o, int depth) {

    dep[o] = depth, dfn[o] = ++times; for (int i = 1; i <= lim; i++) fa[o][i] = fa[fa[o][i-1]][i-1];

    for (int i = path[o]; i; i = edge[i].next)

        if (dfn[edge[i].to] == 0) minn[edge[i].to] = Min(minn[o], edge[i].cost), fa[edge[i].to][0] = o, dfs1(edge[i].to, depth+1);

    }

    void dfs2(int o) {

    f[o] = minn[o];

    LL sum = 0;

    for (int i = path[o]; i; i = edge[i].next)

        dfs2(edge[i].to), sum += f[edge[i].to];

    if (!flag[o]) f[o] = Min(f[o], sum);

    path[o] = 0;

    }

}g1, g2;

bool comp(const int &a, const int &b) {return dfn[a] < dfn[b]; }

int get_lca(int u, int v) {

    if (dep[u] < dep[v]) Swap(u, v);

    for (int i = lim; i >= 0; i--) if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];

    if (u == v) return u;

    for (int i = lim; i >= 0; i--) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];

    return fa[u][0];

}

void work() {

    minn[1] = INF; read(n), lim = log(n)/log(2);

    for (int i = 1; i < n; i++) {read(u), read(v), read(c); g1.add(u, v, c), g1.add(v, u, c); }

    g1.dfs1(1, 1), read(t);

    while (t--) {

    top = 0, g2.top = 0, read(k); for (int i = 1; i <= k; i++) read(lst[i]), flag[lst[i]] = 1;

    sort(lst+1, lst+k+1, comp);

    S[++top] = 1;

    for (int i = 1; i <= k; i++) {

        int lca = get_lca(S[top], lst[i]);

        while (dfn[lca] < dfn[S[top]]) {

        if (dfn[S[top-1]] <= dfn[lca]) {

            g2.add(lca, S[top]); --top;

            if (S[top] != lca) S[++top] = lca;

            break;

        }

        g2.add(S[top-1], S[top]), --top;

        }

        S[++top] = lst[i];

    }

    while (top > 1) g2.add(S[top-1], S[top]), --top;

    g2.dfs2(1); writeln(f[1]);

    for (int i = 1; i <= k; i++) flag[lst[i]] = 0;

    }

}

int main() {

    work(); return 0;

}

相关文章