拿到题就有一个很自然的想法，当存在一个大小\(\ge 3\)的环时，我们可以把上面所有点都走一遍然后回到出发点
然后想到更一般的，直接先来个边双缩点，这样任意两点间都有两条及以上的路径了，因此同一个边双内的点都可以任选
由于经典结论一个连通图边双缩点后会得到一棵树，然后我们很容易想到树形DP求解
设\(f_i\)表示经过\(i\)子树内的所有点后，回到\(i\)能得到的最大代价；同理\(g_i\)则表示不需要回到\(i\)能得到的最大代价，转移为：
\[f_u=\sum_{v\in son(u)} f_v\\g_u=\max_{v\in son(u)} (g_v+\sum_{w\in son(u),w\ne v }f_w) \]然后这题就做完了，复杂度\(O(n+m)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int n,m,w[N],x,y,s,dfn[N],low[N],idx,stk[N],top,vis[N],blk,col[N],sz[N],sum[N],t[N],f[N],g[N]; vector <int> v[N],nv[N];
inline void Tarjan(CI now,CI pre)
{
low[now]=dfn[now]=++idx; stk[++top]=now; vis[now]=1;
for (auto to:v[now]) if (to!=pre)
{
if (!dfn[to]) Tarjan(to,now),low[now]=min(low[now],low[to]);
else if (vis[to]) low[now]=min(low[now],dfn[to]);
}
if (low[now]==dfn[now])
{
++blk; int tmp; do
{
tmp=stk[top--]; vis[tmp]=0; col[tmp]=blk; ++sz[blk]; sum[blk]+=w[tmp];
} while (tmp!=now);
}
}
inline void DFS(CI now,CI fa=0)
{
t[now]=sz[now]>=3; f[now]=g[now]=sum[now];
for (auto to:nv[now]) if (to!=fa)
if (DFS(to,now),t[to]) f[now]+=f[to],t[now]|=t[to];
for (auto to:nv[now]) if (to!=fa)
g[now]=max(g[now],f[now]-(t[to]?f[to]:0LL)+g[to]);
}
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%lld%lld",&n,&m),i=1;i<=n;++i) scanf("%lld",&w[i]);
for (i=1;i<=m;++i) scanf("%lld%lld",&x,&y),v[x].push_back(y),v[y].push_back(x);
for (i=1;i<=n;++i) if (!dfn[i]) Tarjan(i,0);
for (i=1;i<=n;++i) for (auto j:v[i])
if (col[i]!=col[j]) nv[col[i]].push_back(col[j]);
return scanf("%lld",&s),DFS(col[s]),printf("%lld",g[col[s]]),0;
}