20分代码求调

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int maxn=200005;
int n,m,newn,tot,u,v;
vector<int>G[maxn];
vector<int>newG[maxn];
int dfn[maxn],low[maxn],fa[maxn],size[maxn];
long long ans;
long long a[maxn];
long long dp[maxn][2][2];
long long g[maxn][2][2];
int vis[maxn][2][2];
long long sl(int u,int i,int s1,int s2)
{
	long long &ans=g[i][s1][s2];
	if (vis[i][s1][s2]==u)
	{
		return ans;
	}
	vis[i][s1][s2]=u;
	if (i==size[u])
	{
		ans=0;
		return 0;
	}
	if (s2==0)
	{
		if (newG[u][i]==fa[u])
		{
			ans=sl(u,i+1,s1,s2);
			return ans;
		}
		else if (i==size[u]-1)
		{
			if (s1==0)
			{
				ans=max(dp[newG[u][size[u]-1]][0][0],dp[newG[u][size[u]-1]][1][0]);
				return ans;
			}
			else
			{
				ans=dp[newG[u][size[u]-1]][0][0];
				return ans;
			}
		}
		else
		{
			ans=max(sl(u,i+1,s1,s2)+dp[newG[u][i]][0][0],sl(u,i+2,i==0?1:s1,s2)+dp[newG[u][i]][1][0]);
			return ans;
		}		
	}
	else
	{
		if (newG[u][i]==fa[u]||(i>0&&newG[u][i-1]==fa[u])||(i==0&&newG[u][size[u]-1]==fa[u])||(i==size[u]-1&&newG[u][0]==fa[u])||(i<size[u]-1&&newG[u][i+1]==fa[u]))
		{
			ans=sl(u,i+1,s1,s2);
			return ans;
		}
		else if (i==size[u]-1)
		{
			if (s1==0)
			{
				ans=max(dp[newG[u][size[u]-1]][0][0],dp[newG[u][size[u]-1]][1][0]);
				return ans;
			}
			else
			{
				ans=dp[newG[u][size[u]-1]][0][0];
				return ans;
			}
		}
		else
		{
			ans=max(sl(u,i+1,s1,s2)+dp[newG[u][i]][0][0],sl(u,i+2,i==0?1:s1,s2)+dp[newG[u][i]][1][0]);
			return ans;
		}		
	}
}
void addedge(int u,int v)
{
	newG[u].push_back(v);
	newG[v].push_back(u);
}

void build_square(int u,int v)
{
	int temp=u,point=++newn;
	while (temp!=fa[v])
	{
		addedge(point,temp);
		temp=fa[temp];
	}
}
void tarjan(int u,int f)
{
	dfn[u]=low[u]=++tot;
	int sz=G[u].size();
	for (int i=0;i<sz;i++)
	{
		int v=G[u][i];
		if (!dfn[v])
		{
			fa[v]=u;
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if (low[v]>dfn[u])
			{
				addedge(u,v);
			}
		}
		else if (v!=f)
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	for (int i=0;i<sz;i++)
	{
		int v=G[u][i];
		if (v!=f&&dfn[v]<dfn[u])
		{
			build_square(u,v);
		}
	}
}

void dfs(int u,int f)
{
	fa[u]=f;
	int sz=newG[u].size();
	for (int i=0;i<sz;i++)
	{
		if (newG[u][i]==f)
		{
			continue;
		}
		dfs(newG[u][i],u);
	}
}
long long solve(int u,int st,int f)
{
	long long &ans=dp[u][st][f];
	if (ans!=-1)
	{
		return ans;
	}
	ans=0;
	int sz=newG[u].size();
	if (u<=n)
	{
		if (st==0)
		{
			for (int i=0;i<sz;i++)
			{
				if (newG[u][i]==fa[u])
				{
					continue;
				}
				ans+=max(solve(newG[u][i],0,0),solve(newG[u][i],1,0));
			}
			return ans;
		}
		else
		{
			for (int i=0;i<sz;i++)
			{
				if (newG[u][i]==fa[u])
				{
					continue;
				}
				ans+=solve(newG[u][i],0,1);
			}
			ans+=a[u];
			ans=max(ans,0ll); 
			return ans;
		}
	}
	else
	{
		size[u]=sz;
		for (int i=0;i<sz;i++)
		{
			if (newG[u][i]==fa[u])
			{
				continue;
			}
			solve(newG[u][i],0,0);
			solve(newG[u][i],1,0);
		}
		if (f==0)
		{
			ans=sl(u,0,0,0);
			return ans;
		}
		else
		{
			ans=sl(u,0,0,1);
			return ans;
		}
	}
}
int main()
{
	memset(dp,-1,sizeof(dp));
	cin>>n>>m;
	newn=n;
	for (int i=1;i<=m;i++)
	{
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for (int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for (int i=1;i<=n;i++)
	{
		if (!dfn[i])
		{
			tarjan(i,0);
			dfs(i,0);
			ans+=max(solve(i,0,0),solve(i,1,0));
		}
	}
	cout<<ans<<endl;
}