记录编号	442172	评测结果	AAAAAAAAAAA
题目名称	子集	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.031 s
提交时间	2017-08-26 12:21:37	内存使用	4.87 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,m,id,v[N],w[N],head[N],next[N];
bool incir[N];
void add(int f,int t){
	static int cnt=1;
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
int fa[N],up[N];
bool vis[N],use[N],cir[N];
void dfs(int x){
	vis[x]=1;
	for (int i=head[x];i;i=next[i])
	if (!use[i]){
		use[i]=use[i^1]=1;
		int v=w[i];
		if (v==fa[x]) continue;
		if (vis[v]){
			id++;
			add(id,v);add(v,id);
			cir[i]=cir[i^1]=1;
			for (int i=x;i!=v;i=fa[i]){//按顺序加边，以便后面dp使用
				add(id,i);add(i,id);
				cir[up[i]]=cir[up[i]^1]=1;
			}
		}
		else up[v]=i,fa[v]=x,dfs(v);
	}
}
int dp[N][2];//dp[i][j]表示以i为根的仙人掌中取/不取根的最大独立集
void solve(int x,int fa){
	if (x<=n){//圆点
		dp[x][1]=v[x];
		for (int i=head[x];i;i=next[i])
		if (!cir[i]&&w[i]!=fa){
			int v=w[i];
			solve(v,x);
			if (v<=n) dp[x][1]+=dp[v][0],dp[x][0]+=max(dp[v][0],dp[v][1]);
				else dp[x][1]+=dp[v][1],dp[x][0]+=dp[v][0];
		}
	}
	else{//方点
		for (int i=head[x];i;i=next[i])
			if (!cir[i]&&w[i]!=fa) solve(w[i],x);
		//从根开始，化环为链
		static int q[N],f[N][2];//f[i][j]表示前i个中选/不选最后一个的最大独立集
		int size=0;
		for (int i=head[x];i;i=next[i])
			if (!cir[i]&&w[i]!=fa) q[++size]=w[i];
		//求dp[x][1]
		f[1][0]=dp[q[1]][0];f[1][1]=-1e9;
		for (int i=2;i<=size;i++)
			f[i][1]=f[i-1][0]+dp[q[i]][1],f[i][0]=max(f[i-1][0],f[i-1][1])+dp[q[i]][0];
		dp[x][1]=f[size][0];
		//求dp[x][0]
		f[1][0]=dp[q[1]][0];f[1][1]=dp[q[1]][1];
		for (int i=2;i<=size;i++)
			f[i][1]=f[i-1][0]+dp[q[i]][1],f[i][0]=max(f[i-1][0],f[i-1][1])+dp[q[i]][0];
		dp[x][0]=max(f[size][0],f[size][1]);
	}
}
int main()
{
	freopen("subseta.in","r",stdin);
	freopen("subseta.out","w",stdout);
	scanf("%d",&n);id=n;
	for (int i=1;i<=n;i++) scanf("%d",&v[i]);
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	int ans=0;
	for (int i=1;i<=n;i++)
		if (!vis[i]) dfs(i),solve(i,0),ans+=max(dp[i][0],dp[i][1]);
	printf("%d\n",ans);
	return 0;
}