洛谷P2478 [SDOI2010]城市规划题解

题目链接：P2478 [SDOI2010]城市规划

题意：

给定一个带点权沙漠（多棵仙人掌），求最大权独立集。

此处独立集的定义为集合中任意两个结点的最短路径长度不小于 $3$ （就是隔两个结点）

独立集的权值定义为独立集中所有的点的权值的和。

数据范围：

$n\le 10^6,m\le 2\times 10^6$，且点权 $0\le h_i \le 1000$。

提示：

原题给出的是点仙人掌组成的沙漠。

点仙人掌的定义为：每个点至多存在于一个简单环内的无向连通图。

边仙人掌的定义为：每条边至多存在于一个简单环内的无向连通图。

考虑这样一张图 (1,2) (1,3) (2,3) (3,4) (3,5) (4,5) 。它就是边仙人掌，而不是点仙人掌。

仙人掌dp套dp神题，想了我大概 $5$ 个小时（~~其实是沙漠~~）

我们可以用 $\mathtt{Tarjan}$ 找环，然后分别考虑树上dp和环上dp。

设 $f_{i,0/1/2}$ ，则

$f_{i,0}$ 表示选了 $i$ ， $i$ 所在子树的最大价值
$f_{i,1}$ 表示选了 $i$ 的某个儿子， $i$ 所在子树的最大价值
$f_{i,2}$ 表示 $i$ 和它儿子都没选，子树的最大价值

这里子树的定义为

若 $u$ 不在环上或 $u$ 是环顶，则子树定义为缩点后 $\mathtt{DFS}$ 树上的子树，不考虑返祖边和横叉边。
若 $u$ 在环上但不是环顶，则子树定义为 $\mathtt{DFS}$ 树上「所有不在环上的儿子」的子树与 $u$ 的并。

下文中使用 $a \uparrow b+c$ 表示 a += b+c 。在讲解之前先给一张图方便理解。

树上dp部分：

显然叶子结点有 $f_{u,0}=h_u,~f_{u,1}=f_{u,2}=0$ 。

考虑转移。设 $u$ 为非叶子结点， $v \in \mathtt{son}(u)$ ，则

$\begin{aligned} f_{u,0} &\uparrow f_{v,2} \\[6pt]f_{u,2} &\uparrow \max\{f_{v,1},~f_{v,2}\} \end{aligned}$

显然 $f_{u,1}$ 需要在 $f_{u,0},f_{u,2}$ 计算完再计算

因为恰好只能选一个儿子，所以我们可以按 $f_{u,2}$ 的方式转移，并考虑选的那个儿子对应的增量，则

$f_{u,1} = f_{u,2} + \max\left\{f_{v,0} - \max\{f_{v,1}, ~ f_{v,2}\}\right\}$

注意到后面那个式子是可以在算 $f_{u,0}$ 和 $f_{u,2}$ 的时候算出来的。

因为用了 $\mathtt{Tarjan}$ ，所以在做 $u$ 的树上dp部分时，不会把 $u$ 的环上dp部分给多算进去。

环上dp部分：

设环顶为 $u$ （即 $\mathtt{DFS}$ 树上深度最小的那个点）

记环上点按深度大到小依次为 $c_1,c_2,\cdots,c_k$ ，则有 $c_k = u$ 。

设 $\mathtt{calc}(l,r)$ 表示规定了环上 $c_{l-1},c_{r+1}$ 不能选，他们之间的结点 $c_{l\sim r}$按照题意随便选的最大价值。

类似于 $f$ 的定义，对于每个要处理的环，我们设一个 $g_{i,0/1/2}$ 。

$g_{i,0}$ 表示选了 $c_i$ ，$c_i$ 所在子树的最大价值。
$g_{i,1}$ 表示选了 $c_i$ 的某个儿子，$c_i$ 所在子树的最大价值。
$g_{i,2}$ 表示 $c_i$ 和儿子都没选，$c_i$ 所在子树的最大价值

边界：$g_{l-1,0} = 0, ~g_{l-1,1} = f_{c_{l-1},1},~g_{l-1,2} = f_{c_{l-1},2}$ 。

考虑转移，不难发现有

$\begin{aligned} g_{i,0} &= g_{i-1,2} + f_{c_i,0} \\[6pt] g_{i,2} &= \max\left\{g_{i-1,1},~g_{i-1,2}\right\} + f_{c_i,2} \\[6pt] g_{i,1} &= \max\left\{g_{i-1,0} + f_{c_i,2}, ~\max\{g_{i-1,1},~g_{i-1,2}\} + f_{c_i,1}\right\} \end{aligned}$

注意 $l \le i \le r+1$ ，$\mathtt{calc}(l,r) = \max\{g_{r+1,1},~g_{r+1,2}\}$ 。

特别地，如果 $l > r+1$ ，则定义 $\mathtt{calc}(l,r)=0$ 。

接着考虑 $f_{u,0/1/2}$ （环顶）的转移，不难发现（注意这里还是增量，因为可能不止一个儿子在环上）

$\begin{aligned} f_{u,0} &\uparrow f_{c_1,2} + f_{c_{k-1},2} + \mathtt{calc}(3,k-3) \\[6pt] f_{u,2} &\uparrow \mathtt{calc}(2,k-2) \end{aligned}$

$f_{u,1}$ 不同于树上dp部分，要在 $f_{u,0},f_{u,2}$ 之前算。

选择了环外子结点，则 $f_{u,1} \gets f_{u,1} + \mathtt{calc}(2,k-2)$
选择了 $c_1$ ，则 $f_{u,1} \gets f_{u,2} + f_{c_2,2} + f_{c_1,0} + \mathtt{calc}(4,k-2)$
选择了 $c_{k-1}$ ，则 $f_{u,1} \gets f_{u,2} + f_{c_{k-2},2} + f_{c_{k-1},0} + \mathtt{calc}(2,k-4)$

综上，有

$f_{u,1} \gets \max\begin{cases}f_{u,1} + \mathtt{calc}(2,k-2) \\[6pt]f_{u,2} + f_{c_2,2} + f_{c_1,0} + \mathtt{calc}(4,k-2) \\[6pt]f_{u,2} + f_{c_{k-2},2} + f_{c_{k-1},0} + \mathtt{calc}(2,k-4) \end{cases}$

时间复杂度 $\mathcal{O}(n+m)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
    template<typename T>void print(T x) { write(x); pc('\n'); }
}using namespace FastIO;
#define N ((int)(1e6+15))

int n,m,tim,pos=1,head[N],tmp[N][3],h[N],c[N],f[N][3],fa[N],dfn[N],low[N];
struct Edge{ int u,v,next; } e[N * 2];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
int calc(int l,int r)
{
    if(l > r+1) return 0;
    tmp[l-1][0] = 0;
    tmp[l-1][1] = f[c[l-1]][1];
    tmp[l-1][2] = f[c[l-1]][2];
    for(int i=l; i<=r+1; i++)
    {
        tmp[i][0] = tmp[i-1][2] + f[c[i]][0];
        tmp[i][2] = max(tmp[i-1][1], tmp[i-1][2]) + f[c[i]][2];
        tmp[i][1] = max(tmp[i-1][0] + f[c[i]][2], max(tmp[i-1][1],tmp[i-1][2]) + f[c[i]][1]);
    }
    // cout << l << "  " << r << "  " << max(tmp[r+1][1],tmp[r+1][2]) << '\n';
    return max(tmp[r+1][1], tmp[r+1][2]);
}
void solve(int s,int t)
{
    int cnt = 0;
    for(c[++cnt] = s; c[cnt] != t; ++cnt)
        c[cnt + 1] = fa[c[cnt]];

    int mx = max(f[c[1]][0] + f[c[2]][2] + calc(4,cnt-2),
         f[c[cnt-1]][0] + f[c[cnt-2]][2] + calc(2,cnt-4));
    f[t][1] = max(f[t][1] + calc(2,cnt-2), f[t][2] + mx);
    f[t][0] += calc(3, cnt-3) + f[c[1]][2] + f[c[cnt-1]][2];
    f[t][2] += calc(2, cnt-2);
}
void Tarjan(int u,int Fa)
{
    fa[u] = Fa; dfn[u] = low[u] = ++tim;
    f[u][0] = h[u]; f[u][2] = 0;
    int mx = 0;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v;
        if(!dfn[v])
        {
            Tarjan(v,u); down(low[u], low[v]);
        }else if(v != Fa)
        { down(low[u], dfn[v]); }
        if(low[v] > dfn[u])
        {
            f[u][0] += f[v][2];
            f[u][2] += max(f[v][2], f[v][1]);
            up(mx, f[v][0] - max(f[v][2], f[v][1]));
        }
    }
    f[u][1] = f[u][2] + mx;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v;
        if(low[v] == dfn[u] && fa[v] != u) solve(v,u);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n); read(m);
    for(int i=1; i<=n; i++) read(h[i]);
    for(int i=1,u,v; i<=m; i++)
    {
        read(u); read(v);
        addEdge(u,v); addEdge(v,u);
    }
    int ans = 0;
    for(int i=1; i<=n; i++) if(!dfn[i])
    { Tarjan(i,0); ans += max({f[i][0], f[i][1], f[i][2]}); }
    print(ans);
    return 0;
}