J. Defend Your Country

前言

思维题，主要是要猜结论证结论。

Solution

对于n是偶数的情况，显然不需要删边。

对于n是奇数的情况，删去非割点显然只用删一个，主要是考虑删掉割点的情况。

假设删除了偶数个割点使得答案最优，由于剩下的联通块必然都是偶数个点（否则继续删奇数联通块更优），推出总点数是偶数，与“n是奇数”矛盾，所以如果删掉割点最优，我们一定会删掉偶数个割点。

显然如果删割点最优，非割点一定不会被删，否则的话只删一个非割点更优。

现在来证明一下，删除的割点个数一定是1，即不可能删除3个或以上的割点：

删除多个割点后，产生的联通块中如果还有奇数且大于1的联通块就要继续删，类似于分治。根据前面推出的结论，删去的点一定都是割点，那么删到最后的终止状态一定是删去割点后产生的联通块全都是偶数个，那么其实其他割点都不用删，只用删这一个割点就能满足要求了，可以直接讨论一下：

如果这个点在割去上一个割点前是非割点，那么结论显然。
如果这个点在割去上一个割点前也是割点，那么其实拆出来的联通块是当前拆出来的联通块的子集，也就是说拆出来的都是偶数个联通块，那么原先的奇数联通块删去一个点同时割掉了若干个偶数联通块，这个联通块的点数就变成了偶数个，那么此时就满足要求了。

综上，从终止状态往回推，如果删掉割点最优的话其实只用删掉一个割点。

那么做法就很明显了，我们在求割点的过程中记录割去这个割点后产生的联通块点个数的奇偶性，只有当割去割点后产生的联通块都是偶数才计入答案，最终再与删去非割点的最小值的结果取max。

时间复杂度 $O(n)$

int dfn[N], low[N], tot, sz[N], a[N];
bool tag[N], cut[N];
vector<int>to[N];
void tarjan(int x, int fa) {
    dfn[x] = low[x] = ++tot;
    sz[x] = 1;
    int child = 0;
    for (auto k : to[x]) {
        if (!dfn[k]) {
            tarjan(k, x);
            sz[x] += sz[k];
            if (low[k] == dfn[x]) {
                if (fa)cut[x] = true;
                if (sz[k] & 1)tag[x] = true;
            }
            low[x] = min(low[x], low[k]);
            if (!fa)++child;
        }
        else low[x] = min(low[x], dfn[k]);
    }
    if (child > 1) {
        cut[x] = true;
    }
}

int main() {
    int T = fast_IO::read();
    while (T--) {
        int n = fast_IO::read(), m = fast_IO::read();
        ll sum = 0;
        tot = 0;
        for (int i = 1; i <= n; ++i)sum += a[i] = fast_IO::read();
        for (int i = 1; i <= m; ++i) {
            int x = fast_IO::read(), y = fast_IO::read();
            to[x].push_back(y);
            to[y].push_back(x);
        }
        if (n & 1) {
            tarjan(1, 0);
            int minn = INF;
            for (int i = 1; i <= n; ++i) {
                if (!cut[i] || !tag[i])
                    minn = min(minn, a[i]);
            }
            printf("%lld\n", sum - minn * 2);
        }
        else printf("%lld\n", sum);
        for (int i = 1; i <= n; ++i)
            cut[i] = sz[i] = tag[i] = dfn[i] = low[i] = 0, to[i].clear();
    }
    return 0;
}

题解 | J. Defend Your Country

J. Defend Your Country

前言

Solution