洛谷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;
}