【题解】HNOI2009无归岛

　　这题真的是无语了，在哪个岛上根本就没有任何的用处……不过我是画了下图，感受到一定是仙人掌，并不会证。有谁会证的求解……

　　如果当做仙人掌来做确实十分的简单。只要像没有上司的舞会一样树形dp就好了，遇到环出现的时候把环遍历一遍单独求解，和小C的独立集完全是一样的做法。

#include <bits/stdc++.h>

using namespace std;

#define maxn 500000

#define int long long

#define INF 999999999

int n, m, cnp = ;

int f[maxn][], fa[maxn], val[maxn];

int ans, timer, dfn[maxn], low[maxn];

struct edge

{

    int cnp = , head[maxn], to[maxn], last[maxn];

    void add(int u, int v)

    {

        to[cnp] = v, last[cnp] = head[u], head[u] = cnp ++;

        to[cnp] = u, last[cnp] = head[v], head[v] = cnp ++;

    }

}E1;

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

void Solve(int u, int v)

{

    bool flag = ;

    if(u == ) flag = ;

    int f1 = , f0 = ;

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

    {

        int t0 = f0 + f[i][], t1 = f1 + f[i][];

        f0 = max(t0, t1), f1 = t0;

    }

    f[u][] += f0;

    f1 = -INF, f0 = ;

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

    {

        int t0 = f[i][] + f0, t1 = f[i][] + f1;

        f1 = t0, f0 = max(t0, t1);

    }

    f[u][] += f1;

}

void Tarjan(int u)

{

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

    f[u][] = , f[u][] = val[u];

    for(int i = E1.head[u]; i; i = E1.last[i])

    {

        int v = E1.to[i];

        if(v == fa[u]) continue;

        if(!dfn[v])

        {

            fa[v] = u; Tarjan(v);

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

        }

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

        if(low[v] > dfn[u] && fa[v] == u)

            f[u][] += f[v][], f[u][] += max(f[v][], f[v][]);

    }

    for(int i = E1.head[u]; i; i = E1.last[i])

    {

        int v = E1.to[i];

        if(dfn[v] > dfn[u] && fa[v] != u) Solve(u, v);

    }

}

signed main()

{

    n = read(), m = read();

    for(int i = ; i <= m; i ++)

    {

        int u = read(), v = read();

        E1.add(u, v);

    }

    for(int i = ; i <= n; i ++)

        val[i] = read();

    for(int i = ; i <= n; i ++)

    {

        if(dfn[i]) continue;

        Tarjan(i); ans += max(f[i][], f[i][]);

    }

    printf("%lld\n", ans);

    return ;

}