Description
Neverland是个神奇的地方，它由一些岛屿环形排列组成，每个岛上都生活着之中与众不同的物种。但是这些物种都有一个共同的生活习性：对于同一个岛上的任意两个生物，他们有且仅有一个公共朋友，即对同一岛上的任意两个生物a和b有且仅有一个生物c既是a的朋友也是b的朋友，当然某些岛上也可能会只有一个生物孤单地生活着。这一习性有一个明显的好处，当两个生物发生矛盾的时候，他们可以请那个唯一的公共朋友来裁决谁对谁错。
另外，岛与岛之间也有交流，具体来说，每个岛都会挑选出一个最聪明的生物做代表，然后这个生物与他相邻的两个岛的代表成为朋友。
不行的是，A世界准备入侵Neverland，作为Neverland的守护者，Lostmonkey想知道在一种比较坏的情况下Never的战斗力。因为和朋友并肩作战，能力会得到提升，所以Lostmonkey想知道在不选出一对朋友的情况下Neverland的最大战斗力。即选出一些生物，且没有一对生物是朋友，并且要求它们的战斗力之和最大。
Input
第一行包含用空格隔开的两个整数n和m，分别表示Neverland的生物种数和朋友对数。接下来的m行描述所有朋友对，具体来说，每行包含用空格隔开的两个整数a和b，表示生物a和生物b是朋友（每对朋友只出现一次）。第m+2行包含用空格隔开的n个整数，其中第i个整数表示生物i的战斗力Ai。输入数据保证4<=n<=100000，1<=a,b<=n，1<=m<=200000，-1000<=Ai<=1000.
Output
仅包含一个整数，表示满足条件的最大战斗力。
Sample Input
Sample Output
50 【样例说明】 有四个岛，生物1在1号岛，生物2在2号岛，生物3、5、6在3号岛，生物4在4号岛。
题解都说原图是仙人掌，但我不知道怎麽证，有人知道可以告诉我
如果是仙人掌，那么就可以环DP，可以保证复杂度不会退化
f[i][0]表示这个点选择了的最大值，f[i][1]表示未选
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 struct Node 7 { 8 int next,to; 9 }edge[400001];10 int head[100001],num,f[100001][2],n,m,fa[100001],cnt,dfn[100001],low[100001],val[100001];11 void add(int u,int v)12 {13 num++;14 edge[num].next=head[u];15 edge[num].to=v;16 head[u]=num;17 }18 void dp(int root,int x)19 { int i;20 int u1=0,u2=0,v1,v2;21 for (i=x;i!=root;i=fa[i])22 {23 v1=u1+f[i][0];v2=u2+f[i][1];24 u1=v2;u2=max(v1,v2);25 }26 f[root][1]+=u2;27 u1=-2e9,u2=0;28 for (i=x;i!=root;i=fa[i])29 {30 v1=u1+f[i][0];v2=u2+f[i][1];31 u1=v2;u2=max(v1,v2);32 }33 f[root][0]+=u1;34 }35 void dfs(int x)36 { int i;37 ++cnt;38 low[x]=dfn[x]=cnt;39 for (i=head[x];i;i=edge[i].next)40 {41 int v=edge[i].to;42 if (v!=fa[x])43 if (!dfn[v])44 {45 fa[v]=x;46 dfs(v);47 low[x]=min(low[x],low[v]);48 }49 else low[x]=min(low[x],dfn[v]);50 }51 f[x][0]=val[x];52 for (i=head[x];i;i=edge[i].next)53 {54 int v=edge[i].to;55 if (fa[v]!=x&&dfn[v]>dfn[x])56 dp(x,v);57 }58 }59 int main()60 { int i,u,v;61 cin>>n>>m;62 for (i=1;i<=m;i++)63 {64 scanf("%d%d",&u,&v);65 add(u,v);add(v,u);66 }67 for (i=1;i<=n;i++)68 scanf("%d",&val[i]);69 dfs(1);70 cout<