#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define
maxn 102000
#define maxm 400100
using namespace std;
int
e[maxn],ne[maxm],v[maxm];
int nn;
int val[maxn];
int
dp[maxn][2];
int pre[maxn];
void add(int x,int y){
ne[++nn]=e[x],e[x]=nn,v[nn]=y;
}
int n,m;
int
low[maxn],dfn[maxn],tot;
void tarjan(int x){
low[x]=dfn[x]=++tot;
for(int i=e[x];i;i=ne[i]){
if(v[i]==pre[x])continue;
if(!dfn[v[i]]){
pre[v[i]]=x;
tarjan(v[i]);
low[x]=min(low[x],low[v[i]]);
if(low[v[i]]>dfn[x])dp[x][1]+=dp[v[i]][0],dp[x][0]+=dp[v[i]][1];
} else
low[x]=min(low[x],dfn[v[i]]);
}
for(int
i=e[x];i;i=ne[i])if(dfn[v[i]]>dfn[x]&&pre[v[i]]!=x){
int
m1,m0,temp;
m1=dp[v[i]][1];
m0=dp[v[i]][0];
for(int
j=pre[v[i]];j!=x;j=pre[j]){
temp=m1;
m1=m0+dp[j][1];
m0=temp+dp[j][0];
m1=max(m0,m1);
}
dp[x][0]+=m1;
m1=dp[v[i]][0];
m0=dp[v[i]][0];
for(int
j=pre[v[i]];j!=x;j=pre[j]){
temp=m1;
m1=m0+dp[j][1];
m0=temp+dp[j][0];
m1=max(m1,m0);
}
dp[x][1]+=m0;
}
dp[x][1]=max(dp[x][1],dp[x][0]);
}
int
main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int
a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int
i=1;i<=n;i++){
scanf("%d",&val[i]);
if(val[i]<0)val[i]=0;
dp[i][1]=val[i];
}
tarjan(1);
cout<<dp[1][1];
}
bzoj 1484 [HNOI2009]通往城堡之路 仙人掌dp,布布扣,bubuko.com
bzoj 1484 [HNOI2009]通往城堡之路 仙人掌dp
原文：http://www.cnblogs.com/wangyucheng/p/3621871.html