luogu P8595「KDOI-02」一个网的路题解

显然，一边删点一边连边一定不比先删点再连边优，那么这一题就可以转化为求把一个森林通过删除操作变为许多链的情况下，执行删除操作的个数和删掉的边的个数的和 \(k\) 的最小值，最终的答案即为 \(n-1-m+k_{min}\)。
先考虑森林中的一棵树。
假设我们 \((a,b)\) 表示一条链以结点 \(a\)、结点 \(b\) 为首尾的链，\(\text{LCA}(a,b)\) 表示结点 \(a\)、结点 \(b\) 的最近公共祖先。
我们可以发现，如果想要保证这一棵树被分为了许多条链，那么一个结点 \(u\) 可以被区分为以下三种情况：
情况①：结点 \(u\) 被删除。
情况②：结点 \(u\) 未删除，且有一条满足 \(\text{LCA}(a,b)=a\) 或 \(\text{LCA}(a,b)=b\) 的链 \((a,b)\) 经过结点 \(u\)。
情况③：结点 \(u\) 未删除，且有一条满足 \(\text{LCA}(a,b)\neq a\) 且 \(\text{LCA}(a,b)\neq b\) 的链 \((a,b)\) 经过结点 \(u\)。
故而可以使用树形DP来求解 \(k_{min}\)，令 \(dp[u][x]\) 维护以 \(u\) 为根的子树中，达成情况 \(x\)，在该子树内执行删除操作的个数和删掉的和该子树中结点相连的边的个数的最小值。
当 \(x=0\) 时，表示 \(u\) 结点被删除，即 \(dp[u][0]\) 维护情况①。
当 \(x=1\) 时，表示 \(u\) 结点未被删除，\(u\) 结点的子结点中最多有一个未被删除，即 \(dp[u][1]\) 维护情况②。
当 \(x=2\) 时，表示 \(u\) 结点未被删除，\(u\) 结点的子结点中最多有两个个未被删除，即 \(dp[u][2]\) 维护情况②和情况③的最小值。
下面我们考虑转移
令 \(m1\) 表示 \(\forall v\in{son[u]}\)，\(dp[v][1]-dp[v][0]\) 的最小值，\(m2\) 表示 \(\forall v\in{son[u]}\)，\(dp[v][1]-dp[v][0]\) 的次小值，此处的含义是找到可以向上接的链中，最优和次优的两条。
记 \(cnt_{u}\) 表示结点 \(u\) 的度数，对于 \(dp[u][0]\)，其初始值为 \(cnt_{u}+1\)，注意当结点 \(u\) 和结点 \(v\) 均被删除时，需要对连接结点 \(u\) 和结点 \(v\) 的边进行去重，易得

对于 \(dp[u][1]\)，最多从子结点中找到一个为情况②的结点，接上其所维护的那条链，易得

对于 \(dp[u][1]\)，对于其中的情况③，我们需要从子结点中找到两个个为情况②的结点，接上其所维护的那条链，即 \(m2+dp[u][1]\) 即可，易得

完整代码如下

#include<bits/stdc++.h>
using namespace std;
const int NUM=2000005;
int read()
{
    int 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;
}
int n,m,num,head[NUM],dp[NUM][3],siz[NUM];
bool vis[NUM];
struct edge
{
    int next,to;
}e[NUM<<1];
void add_edge(int from,int to)
{
    siz[to]++;
    e[++num].next=head[from];
    e[num].to=to;
    head[from]=num;
}
void dfs(int u)
{
    int v,m1=0,m2=0;
    dp[u][0]=siz[u]+1;
    vis[u]=true;
    for(int i=head[u];i;i=e[i].next)
    {
        v=e[i].to;
        if(!vis[v])
        {
            dfs(v);
            dp[u][1]+=dp[v][0];
            if(m1>dp[v][1]-dp[v][0])
            {
                m2=m1;
                m1=dp[v][1]-dp[v][0];
            }
            else m2=min(m2,dp[v][1]-dp[v][0]);
            dp[u][0]+=min(dp[v][2],dp[v][0]-1);
        }
    }
    dp[u][1]+=m1;
    dp[u][2]=dp[u][1];
    dp[u][2]+=m2;
}
int main()
{
    int u,v,ans=0;
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        u=read(),v=read();
        add_edge(u,v),add_edge(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            dfs(i);
            ans+=min(dp[i][0],dp[i][2]);
        }
    }
    printf("%d",n-1-m+ans);
}

原文地址：http://www.cnblogs.com/looking-forward-to-tomorrow/p/16904686.html