#include <bits/stdc++.h>
using namespace std;
namespace Std {
int n, m, head[200010][2], nxt[800010], to[800010], cnt, dfn[200010],
    fa[200010], tot, num, f[200010][2], g[200010][2], a[200010];
bool mark[100010];
inline void add(int x, int y, bool z) {
  to[++cnt] = y;
  nxt[cnt] = head[x][z];
  head[x][z] = cnt;
}
void dfs(int x, int y) {
  dfn[x] = ++tot;
  fa[x] = y;
  for (int i = head[x][0]; i; i = nxt[i]) {
    if (to[i] == y) continue;
    if (!dfn[to[i]]) {
      mark[x] = 0;
      dfs(to[i], x);
      if (!mark[x]) add(x, to[i], 1);
    } else {
      if (dfn[to[i]] > dfn[x]) continue;
      int u = x;
      ++num;
      while (u != to[i]) {
        add(num, u, 1);
        u = fa[u];
        mark[u] = 1;
      }
      add(to[i], num, 1);
    }
  }
}
void dp(int x) {
  f[x][1] = a[x];
  for (int i = head[x][1]; i; i = nxt[i]) {
    if (to[i] <= n) {
      dp(to[i]);
      f[x][1] += f[to[i]][0];
      f[x][0] += max(f[to[i]][1], f[to[i]][0]);
    } else {
      int u = to[i], f1, f2, f3, f4;
      for (int j = head[u][1]; j; j = nxt[j]) dp(to[j]);
      tot = 0;
      g[0][0] = f[to[head[u][1]]][0];
      g[0][1] = 0xc3c3c3c3;
      for (int j = head[u][1]; j; j = nxt[j]) {
        if (j == head[u][1]) continue;
        ++tot;
        g[tot][1] = f[to[j]][1] + g[tot - 1][0];
        g[tot][0] = f[to[j]][0] + max(g[tot - 1][0], g[tot - 1][1]);
      }
      f1 = g[tot][0];
      f2 = g[tot][1];
      g[0][0] = 0xc3c3c3c3;
      g[0][1] = f[to[head[u][1]]][1];
      tot = 0;
      for (int j = head[u][1]; j; j = nxt[j]) {
        if (j == head[u][1]) continue;
        ++tot;
        g[tot][1] = f[to[j]][1] + g[tot - 1][0];
        g[tot][0] = f[to[j]][0] + max(g[tot - 1][0], g[tot - 1][1]);
      }
      f3 = g[tot][0];
      f4 = g[tot][1];
      f[x][0] += max(max(f1, f2), max(f3, f4));
      f[x][1] += f1;
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  num = n;
  int u, v;
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &u, &v);
    add(u, v, 0);
    add(v, u, 0);
  }
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  dfs(1, 0);
  dp(1);
  printf("%d\n", max(f[1][0], f[1][1]));
  return 0;
}
}  // namespace Std
int main() { return Std::main(); }

题意简述：给一个仙人掌图，求其最大权独立集。

Tag: 仙人掌，圆方树。

solution:

先建立原图的广义圆方树 $G$，设方点为 $n+1$ 至 $Node$（$Node$ 为 $G$ 的节点数）。

定义状态数组 $f_{u,0/1}$，对于圆点，它的含义是在以 $i$ 为根的子树中选择/不选择节点 $i$ 的最大权值，对于方点，它的含义是在以 $i$ 为根的子树中，选择/不选择父亲节点 $fa$ 的最大权值（$f_{i,1}$ 不包括节点 $fa$ 的权值）。

对于圆点 $u$ 有状态转移方程：$f_{u,0}=\sum_{u\to v}f_{v,0}$，$f_{u,1}=val_{u}+\sum_{u\to v}f_{v,1}$。

对于方点 $u$ 设 $f_0=0$，$f_1=-inf$，$g_0=-inf$，$g_1=0$，然后枚举儿子节点 $v$，有 $o_0=f_0$，$o_1=f_1$，$f_0=\max(o_0,o_1)+f_{v,0}$，$f_1=o_0+f_{v,1}$，$o_0=g_0$，$o_1=g_1$，$g_0=\max(o_0,o_1)+g_{v,0}$，$g_1=o_0+g_{v,1}$（依次按顺序执行），计算完所有儿子节点后，有 $f_{u,0}=\max(f_0,f_1)$，$f_{u,1}=g_0$。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int h[N], nt[N<<1], to[N<<1], cnt, hh[N];
int dfn[N], low[N], Stack[N], Top, Node;
int f[N][2], val[N], n, m, dfnt;
void link(int u, int v){
    nt[++cnt]=h[u], h[u]=cnt, to[cnt]=v;
}
void llink(int u, int v){
    nt[++cnt]=hh[u], hh[u]=cnt, to[cnt]=v;
}
void Tarjan(int u){
    Stack[++Top]=u, dfn[u]=low[u]=++dfnt;
    for(int i=h[u]; i; i=nt[i]){
        int v=to[i];
        if(!dfn[v]){
            Tarjan(v), low[u]=min(low[u], low[v]);
            if(low[v]>=dfn[u]){
                Node++;
                for(int x=0; x!=v; Top--)
                    x=Stack[Top], llink(Node, x), llink(x, Node);
                llink(Node, u), llink(u, Node);
            }
        }
        else low[u]=min(low[u], dfn[v]);
    }
}
void dp(int u, int fa){
//    printf("%d  %d\n", fa, u);
    if(u<=n){
        for(int i=hh[u]; i; i=nt[i]) if(to[i]!=fa)
            dp(to[i], u), f[u][0]+=f[to[i]][0], f[u][1]+=f[to[i]][1];
        f[u][1]+=val[u];
        return;
    }
    else{
        int f0=0, f1=-1.4e8, g0=-1.4e8, g1=0;
        for(int i=hh[u]; i; i=nt[i]){
            int v=to[i]; if(v==fa)continue;
            dp(v, u);
            int o0=f0, o1=f1;
            f0=max(o0, o1)+f[v][0], f1=o0+f[v][1];
                o0=g0, o1=g1;
            g0=max(o0, o1)+f[v][0], g1=o0+f[v][1];
        }
        f[u][0]=max(f0, f1), f[u][1]=g0;
    }
}
int main(){
#ifdef LOCAL
    freopen("text.in","r",stdin);
    freopen("text.out","w",stdout);
#endif // LOCAL
    scanf("%d %d", &n, &m);
    for(int i=1, x, y; i<=m; i++)
        scanf("%d %d", &x, &y), link(x, y), link(y, x);
    for(int i=1; i<=n; i++)
        scanf("%d", &val[i]);
    Node=n, Tarjan(1), Top=0;
    dp(1, -1);
    printf("%d\n", max(f[1][0], f[1][1]));
    return 0;
}