2021牛客暑期多校训练营6 J、Defend Your Country

题目大意

你有一张个点条边的无向联通图，现在对于图中的连通分量产生的价值做出如下定义。

如果一个联通分量里面点的个数是偶数那么它的价值就是里面每个点权的和。

如果一个连通分量里面点的个数是奇数那么他的价值就是里面每个点权的和的相反数。

保证每个点的点权。

你现在可以选择一个点把它删去，并且它连的边也一并删去，问进行删除任意多个点之后整张图的权值和最大是多少？

Solution

考点：求割点

首先可以知道，当是偶数的时候，我们不需要进行删点，直接输出就行了。

当是奇数的时候，结论是只需要删掉最多一个点，接下来我们稍微验证一下这个结论。

首先我们去找不是割点的点，这些点是可以随意删除的，删掉它不会带来其他点的损失，那么我们把所有非割点定为可删的点。

那么还有一大类就是对于割点而言，那么如果从号点开始我们会跑出一个类似树的结构。

我们又知道了一定是奇数，那么对于任意个一个割点而言，如果存在一棵子数它的节点总数是奇数，那么一定存在一个对应的子数节点数也是奇数，因为去掉这个割点之后其余点数之和应该为偶数了，所以我们对于存在奇数子树节点的割点，我们就不能删掉，否则如果它下面全部的子树都是偶数，那么对应的它头顶上剩下的子树节点数也是偶数个，对于这样的割点删掉带来的负反馈也是一个节点的值，这样的割点我也认为它可删去。

接下来就去找全部可删去的点里面权值的最小值，用就是答案了。

const int N = 1e6 + 7;
const int M = 1e6 + 7;

struct Map {
    struct Node {
        int v, nxt;
    };
    int head[N], tot;
    Node edge[M << 1];
    void init(int n) { fill(head,head+n+1,-1), tot = 0; }
    void add(int u, int v) {
        edge[++tot].v = v;
        edge[tot].nxt = head[u];
        head[u] = tot;
    }
}G1;

int a[N];
bool cut[N], ok[N];
int rt, low[N], dfn[N], tot, sz[N];

void tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    sz[u] = 1;
    int son = 0;
    for (int i = G1.head[u]; ~i; i = G1.edge[i].nxt) {
        int v = G1.edge[i].v;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            sz[u] += sz[v];
            if (low[v] >= dfn[u]) {
                ++son;
                if (u != rt or son > 1)    cut[u] = 1;
                if (sz[v] & 1)    ok[u] = 0;
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

int solve() {
    int n = read(), m = read();
    G1.init(n);
    for (int i = 1; i <= n; ++i) {
        cut[i] = 0;
        ok[i] = 1;
        low[i] = dfn[i] = sz[i] = 0;
    }
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        sum += a[i];
    }
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        G1.add(u, v);
        G1.add(v, u);
    }
    if (n & 1) {
        rt = 1;
        tarjan(1);
        int mini = INT_MAX;
        for (int i = 1; i <= n; ++i) {
            if (cut[i] == 0 || (cut[i] == 1 && ok[i] == 1)) {
                mini = min(mini, a[i]);
            }
        }
        print(sum - 2 * mini);
    }
    else {
        print(sum);
    }

    return 1;
}