P4426 [HNOI/AHOI2018]毒瘤（虚树dp)

木xx木大 · 2021-01-19 23:08:33 · 题解

P4426 [HNOI/AHOI2018]毒瘤

这题和它的名字一样毒瘤！这直接导致了我失去了一晚上的快乐颓废时光

一句话题意：求一幅图的独立集方案数。

暴力：

首先考虑树上怎么做。设 dp[u][0/1] 表示不选/选 u 的方案数，根据乘法原理，dp 方程显然：

发现 m-n 很小，我们暴力枚举非树边可能的情况，即(1,0),(0,0),(0,1)。发现后两种情况可以合并为一种。于是我们就得到了一个 O(2^{m-n+1}n) 的做法。可以得 75pts，代码非常好写。（听说极致卡常的话能过？）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace FGF
{
    int n,m;
    const int N=1e5+5,mo=998244353;
    int dfn[N],num,eu[N],ev[N],tot,dp[N][2],op[N][2],ans;
    bool vis[N];
    vector<int> g[N];
    int read()
    {
        int s=0;char ch=getchar();
        while(!isdigit(ch))ch=getchar();
        while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
        return s;
    }
    void dfs1(const int &u,const int &f)
    {
        dfn[u]=++num;
        for(auto v:g[u])
        {
            if(v==f)continue;
            if(!dfn[v])dfs1(v,u);
            else if(dfn[u]<dfn[v])eu[tot]=u,ev[tot++]=v;
        }
    }
    void getdp(const int &u)
    {
        dp[u][0]=!op[u][1],dp[u][1]=!op[u][0],vis[u]=1;
        for(auto v:g[u])        
        {
            if(vis[v])continue;
            getdp(v);
            dp[u][0]=1ll*dp[u][0]*(dp[v][0]+dp[v][1])%mo;
            dp[u][1]=1ll*dp[u][1]*dp[v][0]%mo;
        }
    }
    void work()
    {
        n=read(),m=read();
        for(int i=1,u,v;i<=m;i++)
        {
            u=read(),v=read();
            g[u].push_back(v),g[v].push_back(u);
        }
        dfs1(1,0);
        for(int i=0;i<(1<<tot);i++)
        {
            for(int j=0;j<tot;j++)
                if((i>>j)&1)op[eu[j]][1]=op[ev[j]][0]=1;
                    else op[eu[j]][0]=1;
            getdp(1);
            memset(vis,0,sizeof(bool[n+1]));
            ans=(1ll*ans+dp[1][0]+dp[1][1])%mo;
            for(int j=0;j<tot;j++)
                if((i>>j)&1)op[eu[j]][1]=op[ev[j]][0]=0;
                    else op[eu[j]][0]=0;
        }
        printf("%d",ans);
    }
}
int main()
{
    FGF::work();
    return 0;
}

正解

发现每次状态变化的只有非树边涉及的点，这样的点点数很少。对这些点建虚树。考虑虚树上的父子之间怎么转移。对于一条 u\to x_1\to x_2\to\dots x_k \to v，有转移

依次类推，转移方程可以化为 dp[u][0/1]=\prod (k[0/1][0]dp[v][0]+k[0/1][1]dp[v][1])。我们只需要求出转移系数 k 即可。 k 的转移和原来的 dp 式子基本相同，但需要在 u 为关键点时重置且需要统计分叉的贡献（即上面的 dp'）。除此之外，在虚树上 dp 时 dp[u] 的初始值不再是 1 ，还需要预处理出 dp 的初始值。

复杂度为 O(n+2^{m-n+1}(m-n+1))

感觉还是有一定实现上的难度的，代码一定程度上参考了第一篇题解。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace FGF
{
    int n,m;
    const int N=1e5+5,mo=998244353;
    int siz[N],dfn[N],num,eu[N],ev[N],tot,dp[N][2],p[N][2],op[N][2],ans;
    bool vis[N],is[N];
    vector<int> g[N];
    struct Node{
        int x,y;
        Node(){}
        Node(int xx,int yy):x(xx),y(yy){};
    }k[N][2];
    Node operator +(Node a,Node b){return Node((a.x+b.x)%mo,(a.y+b.y)%mo);}
    Node operator *(Node a,int b){return Node(1ll*a.x*b%mo,1ll*a.y*b%mo);}
    struct edg{
        int to,nxt;Node a,b;
    }e[N<<1];
    int cnt,head[N];
    void add(int u,int v,Node a,Node b)
    {
        cnt++;
        e[cnt].to=v;
        e[cnt].nxt=head[u];
        head[u]=cnt;
        e[cnt].a=a,e[cnt].b=b;
    }
    void dfs1(int u,int f) 
    {
        dfn[u]=++num;
        for(auto v:g[u])
        {
            if(v==f)continue;
            if(!dfn[v])dfs1(v,u),siz[u]+=siz[v];
            else
            {
                is[u]=1;//把虚树上的点标起来 
                if(dfn[u]<dfn[v])eu[tot]=u,ev[tot++]=v;//记录非树边 
            }
        }
        is[u]|=siz[u]>=2;
        siz[u]=siz[u]||is[u];
    }
    int predp(int u)
    {
        vis[u]=1;
        p[u][0]=p[u][1]=1;//初始dp值 
        int pos=0,x;
        for(auto v:g[u])
        {
            if(vis[v])continue;
            x=predp(v);//原树子树内离自己最近的虚树上的点 
            if(!x)p[u][0]=1ll*p[u][0]*(p[v][0]+p[v][1])%mo,p[u][1]=1ll*p[u][1]*p[v][0]%mo;
            else if(is[u])add(u,x,k[v][1]+k[v][0],k[v][0]);
            else k[u][1]=k[v][0],k[u][0]=k[v][1]+k[v][0],pos=x;
        }
        if(is[u])k[u][0]={1,0},k[u][1]={0,1},pos=u;//这里k[u][0]={1,0}是因为初始k[u][0]+k[u][1]={1,1} 
        else k[u][0]=k[u][0]*p[u][0],k[u][1]=k[u][1]*p[u][1];
        return pos;
    }
    void getdp(int u)
    {
        dp[u][0]=(op[u][1]^1)*p[u][0],dp[u][1]=(op[u][0]^1)*p[u][1];
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            getdp(v);
            dp[u][0]=1ll*dp[u][0]*((1ll*e[i].a.x*dp[v][0]%mo+1ll*e[i].a.y*dp[v][1]%mo)%mo)%mo;
            dp[u][1]=1ll*dp[u][1]*((1ll*e[i].b.x*dp[v][0]%mo+1ll*e[i].b.y*dp[v][1]%mo)%mo)%mo;
        }
    }
    void work()
    {
        scanf("%d%d",&n,&m);
        for(int i=1,u,v;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            g[u].push_back(v),g[v].push_back(u);
        }
        dfs1(1,0);is[1]=1;
        predp(1);
        for(int i=0;i<(1<<tot);i++)
        {
            for(int j=0;j<tot;j++)
                if((i>>j)&1)op[eu[j]][1]=op[ev[j]][0]=1;//op:强制选某一种情况 
                    else op[eu[j]][0]=1;
            getdp(1);
            ans=(1ll*ans+dp[1][0]+dp[1][1])%mo;
            for(int j=0;j<tot;j++)
                if((i>>j)&1)op[eu[j]][1]=op[ev[j]][0]=0;
                    else op[eu[j]][0]=0;
        }
        printf("%d",ans);
    }
}
int main()
{
    FGF::work();
    return 0;
}