P4410 [HNOI2009]无归岛

P4410 [HNOI2009]无归岛

显然这还是一个仙人掌图

要求求最大独立集，和树形dp一样，遇到环时单独提出来处理一下就好了

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

typedef long long LL;

const LL maxn=1e6;

const LL inf=0x3f3f3f3f;

inline LL Read(){

    LL x=0,f=1; char c=getchar();

    while(c<'0'||c>'9'){

        if(c=='-') f=-1; c=getchar();

    }

    while(c>='0'&&c<='9')

        x=(x<<3)+(x<<1)+c-'0',c=getchar();

    return x*f;

}

struct node{

    LL to,next;

}dis[maxn];

LL n,m,num,tot;

LL dp[maxn][2],fa[maxn],head[maxn],dfn[maxn],low[maxn],a[maxn];

inline void Add(LL u,LL v){

    dis[++num]=(node){v,head[u]},head[u]=num;

}

inline void Dp(LL u,LL v){

    LL sum0(0),sum1(0),sum2(0),sum3(0);

    for(LL i=v;i!=u;i=fa[i]){

        sum3=sum0+dp[i][1],

        sum2=sum1+dp[i][0],

        sum0=sum2,

        sum1=max(sum2,sum3);

    }

    dp[u][0]+=sum1;

    sum0=-inf,sum1=0;

    for(LL i=v;i!=u;i=fa[i]){

        sum3=sum0+dp[i][1],

        sum2=sum1+dp[i][0],

        sum0=sum2,

        sum1=max(sum2,sum3);

    }

    dp[u][1]+=sum0;

}

void Tarjan(LL u){

    low[u]=dfn[u]=++tot;

    dp[u][1]=a[u];

    for(LL i=head[u];i;i=dis[i].next){

        LL v=dis[i].to;

        if(!dfn[v])

            fa[v]=u,

            Tarjan(v),

            low[u]=min(low[u],low[v]);

        else if(v!=fa[u])

            low[u]=min(low[u],dfn[v]);

        if(dfn[u]<low[v])

            dp[u][1]+=dp[v][0],

            dp[u][0]+=max(dp[v][0],dp[v][1]);

    }

    for(LL i=head[u];i;i=dis[i].next){

        LL v=dis[i].to;

        if(fa[v]!=u&&dfn[u]<dfn[v])

            Dp(u,v);

    }

}

int main(){

    n=Read(),m=Read();

    for(LL i=1;i<=m;++i){

        LL u=Read(),v=Read();

        Add(u,v),Add(v,u);

    }

    for(LL i=1;i<=n;++i)

        a[i]=Read();

    Tarjan(1);

    printf("%lld",max(dp[1][0],dp[1][1]));

    return 0;

}