牛客 - Defend Your Country（割点）

传送门：牛客 - Defend Your Country

思路分析

结论就是只删除一个点，如果是割点的话要判断其他连通块是否都是偶数

AC代码

#include <bits/stdc++.h>
#define V vector
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) (x)&(-x)
#define sz(x) (int)(x).size()
#define each(x,a) for(auto& x:a)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define mcp(a,b) memcpy(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 1e18;
const double PI = acos(-1);
const int N = 2e6+10;

int a[N],siz[N],low[N],dfn[N],cut[N],tim,mi;
V<int>e[N];
void tarjan(int u,int f){
    dfn[u] = low[u] = ++tim;
    int ch = 0,ok = 1;
    siz[u] = 1,cut[u]=0;
    each(v,e[u]){
        if(!dfn[v]){
            tarjan(v,f);
            low[u] = min(low[u],low[v]);
            siz[u]+=siz[v];
            if(low[v]>=dfn[u]){
                if(u!=f) cut[u] = 1;
                if(siz[v]%2) ok = 0;
            }
            ch++;
        }else low[u] = min(low[u],dfn[v]);
    }
    if(u==f && ch>=2) cut[u] = 1;
    if(cut[u] && ok) mi = min(mi,a[u]);
    if(!cut[u]) mi = min(mi,a[u]);

}

signed main() {

#ifdef xiaofan
    clock_t stTime = clock();
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
/*==========================begin============================*/
    IOS;
    int T;
    cin>>T;
    while(T--){
        int n,m;
        tim = 0,mi = INF;
        int ans = 0;
        cin>>n>>m;
        for(int i=1;i<=n;i++) {
            cin>>a[i];
            ans+=a[i];
            low[i] = dfn[i] = 0;
            e[i].clear();
        }
        for(int i=1;i<=m;i++) {
            int u,v;
            cin>>u>>v;
            e[u].pb(v);
            e[v].pb(u);
        }
        if(n%2 == 0){
            cout<<ans<<endl;
        }else{
            tarjan(1,1);
            cout<<ans-2*mi<<endl;
        }

    }



/*===========================end=============================*/
#ifdef xiaofan
    cerr << "Time Used:" << clock() - stTime << "ms" <<endl;
#endif
    return 0;
}