2021牛客多校赛第六场

第六场"/>

2021牛客多校赛第六场

传送门

A
B
C构造
D
E
F水题
G
H扫描线
I水题
J图论tarjan割点(求割点，还需要求割点去除后形成的各个连通块的点数奇偶)
K

J
题意：给一个n个点m条边的联通无向图(保证没有自环和重边)，每个点有点权ai。对于图内每个连通块它产生的价值为(-1)^块内点数*块内点权和。现在可以随便删边需要使得总价值最大

解析：如果n是偶数，则不需要删除任何东西。如果n是奇数，那么奇数只能分割为偶数+奇数。所以考虑奇数部分最小，那当然是只有一个点的时候最小。故删除一个点即可(删除与其相关的所有边)。所以可以尝试枚举删除1~n个点得到答案，但是有可能点是割点。就需要保证去掉这个点之后形成的各个连通块都为偶数才行。维护答案即可。

实现：难点在于求割点，那么tarjan求割点即可。然后需要记录割点后各个分块的点数奇偶，则需要更改tarjan，在dfs途中记录割点同时记录此时每个节点下的各个子树节点个数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;struct YPO
{ll to,next;
}edges[5000050];
ll head[1000050],tot;
ll INF=1e15;ll idx,low[1000050],dfn[1000050];   //tarjan所用ll siz[1000050];    //siz[i]表示以i为结点的子树结点数总和。
bool cut[1000050],tag[1000050];   //cut[i]表示i结点是否为割点，tag[i]表示i这个割点割去之后剩下的连通块城市数量是否为偶数。ll n,m,a[1000050];
ll res;void init()
{tot=0;idx=0;res=0;for(ll i=1;i<=n;i++){head[i]=0;low[i]=0;dfn[i]=0;siz[i]=0;cut[i]=0;tag[i]=0;}
}void add(ll u,ll v)
{tot++;edges[tot].next=head[u];edges[tot].to=v;head[u]=tot;
}void tarjan(ll u,ll fu)
{idx++;dfn[u]=low[u]=idx;ll son=0;siz[u]=1;for(ll i=head[u];i!=0;i=edges[i].next){ll v=edges[i].to;if(v==fu)continue;if(!dfn[v]){son++;tarjan(v,u);siz[u]+=siz[v];low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]){if(fu)  //为割点。cut[u]=1;if(siz[v]&1)  //说明子树结点为奇数tag[u]=1;}}else{low[u]=min(low[u],dfn[v]);}}if(fu==-1&&son>1)cut[u]=1;
}void solve()
{if(n%2==0){printf("%lld\n",res);init();return;}tarjan(1,-1);ll minn=INF;for(ll i=1;i<=n;i++){if(!cut[i]||!tag[i]){minn=min(minn,a[i]);}}printf("%lld\n",res-2*minn);init();
}int main()
{ll t;scanf("%lld",&t);while(t--){scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++){scanf("%lld",&a[i]);res+=a[i];}ll u,v;for(ll i=1;i<=m;i++){scanf("%lld%lld",&u,&v);add(u,v);add(v,u);}solve();}return 0;
}