【題解】HNOI-2018毒瘤

Problem

洛谷 & pdf題面

題目概述：

給定一張 n n 個點mm條邊的無向圖，求獨立集數量

n≤100000,m−n≤10 n ≤ 100000 , m − n ≤ 10

Thoughts

話說在考場上居然沒開 long long l o n g   l o n g ，直挂 25 25 分

一開始看題面，觀察特殊資料，發現如果這個圖是一棵樹，可以樹型Dp，方程：

f[x][0]=∏(f[son][0]+f[son][1]) f [ x ] [ 0 ] = ∏ ( f [ s o n ] [ 0 ] + f [ s o n ] [ 1 ] )

f[x][1]=∏f[son][0] f [ x ] [ 1 ] = ∏ f [ s o n ] [ 0 ]

觀察到資料 m−n≤10 m − n ≤ 10 ，意味着樹之外最多有 11 11 條邊，明顯可以暴力枚舉這些邊的兩端節點的選取與否（有三種狀态： (1,0),(0,0),(0,1) ( 1 , 0 ) , ( 0 , 0 ) , ( 0 , 1 ) ）

複雜度 O(3m−n+1n) O ( 3 m − n + 1 n ) ，預期得分 55 55 分，實際得分 65 65 分，蒟蒻爆 long long l o n g   l o n g ，得分……

發現其實隻要限制其中一個點時， (0,0) ( 0 , 0 ) 與 (0,1) ( 0 , 1 ) 可以同時轉移，是以對于每條邊隻有兩種情況

複雜度 O(2n−m+1n) O ( 2 n − m + 1 n ) ，預期得分 80 80 分，實際得分 80 80 ~ 100 100 分，蒟蒻爆 long long l o n g   l o n g ，得分……

Solution

正解是虛樹Dp，蒟蒻不會……

虛樹部分：

實際上就是将剩下的這 m−n+1 m − n + 1 條邊的兩端的點作為關鍵點，同時為了保證這棵樹的整體狀态不變，我們還要選取其中任意兩個點的 lca l c a ，為了降低複雜度，我們将這些點根據 dfs d f s 序排序，隻要選取相鄰兩個的 lca l c a 即可，用一個棧可以實作

Dp部分：

先減除冗雜部分（即僅與一個關鍵節點相連的子樹），我們考慮先将虛樹之外的貢獻設為 g[x][0/1] g [ x ] [ 0 / 1 ] ，轉移方程和上面一樣，隻不過隻有在子樹不屬于虛樹時要轉移

其次，為了使虛樹中壓縮的路徑得以展現，我們采用對系數進行 Dp D p ，提前預處理出虛樹上每一條邊的轉移系數，可以采用樹型 Dp D p 解決

一定要時刻提醒自己因 long long l o n g   l o n g 翻的車

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rg register

template <typename _Tp> inline _Tp read(_Tp&x){
    char c11=getchar(),ob=;x=;
    while(c11^'-'&&!isdigit(c11))c11=getchar();if(c11=='-')c11=getchar(),ob=;
    while(isdigit(c11))x=x*+c11-'0',c11=getchar();if(ob)x=-x;return x;
}

const int N=,p=;
int lx[N],rx[N],dfn[N],vis[N],is[N],head[N],Head[N];
int f[N][],g[N][],shall[N][];
int n,m,ans,dfc,tot,_,__;

struct Par{
    int x,y;
    Par(){}
    Par(const int&Ax,const int&By){x=Ax,y=By;}
    inline Par operator + (const Par&bb) const {return Par((x+bb.x)%p,(y+bb.y)%p);}
    inline Par operator * (const int bb) const {return Par(int(l*x*bb%p),int(l*y*bb%p));}
    inline void operator += (const Par&bb) {*this=*this+bb;}
    inline void operator *= (const int&bb) {*this=*this*bb;}
}k[N][];

struct Edge{int v,nxt;}a[N<<];
struct vEdge{int v,nxt;Par a,b;}e[];

inline void add(int u,int v){a[++_].v=v,a[_].nxt=head[u],head[u]=_;}

inline void add2(int u,int v,Par a,Par b){e[++__].v=v,e[__].a=a,e[__].b=b,e[__].nxt=Head[u],Head[u]=__;}

inline int build(int x){
    g[x][]=g[x][]=;
    int son=;vis[x]=;
    for(int i=head[x];i;i=a[i].nxt)
        if(!vis[a[i].v]){
            int to=build(a[i].v);
            if(!to){
                g[x][]=l*g[x][]*(g[a[i].v][]+g[a[i].v][])%p;
                g[x][]=l*g[x][]*g[a[i].v][]%p;
            }else if(is[x])add2(x,to,k[a[i].v][]+k[a[i].v][],k[a[i].v][]);
            else k[x][]=k[a[i].v][]+k[a[i].v][],k[x][]=k[a[i].v][],son=to;
        }
    if(is[x])k[x][]=Par(,),k[x][]=Par(,);
    else k[x][]*=g[x][],k[x][]*=g[x][];
    return is[x]?x:son;
}

inline int dfs(int x,int las){
    dfn[x]=++dfc;
    int cnt=;
    for(int i=head[x];i;i=a[i].nxt)
        if(a[i].v!=las)
            if(!dfn[a[i].v])cnt+=dfs(a[i].v,x);
            else {
                is[x]=;
                if(dfn[x]<dfn[a[i].v])lx[++tot]=x,rx[tot]=a[i].v;
            }
    if(cnt>)is[x]=;
    return cnt||is[x];
}

inline void dp(int x){
    if(shall[x][])f[x][]=;else f[x][]=g[x][];
    if(shall[x][])f[x][]=;else f[x][]=g[x][];
    for(rg int i=Head[x];i;i=e[i].nxt){
        dp(e[i].v);
        f[x][]=l*f[x][]*(l*e[i].a.x*f[e[i].v][]%p+l*e[i].a.y*f[e[i].v][]%p)%p;
        f[x][]=l*f[x][]*(l*e[i].b.x*f[e[i].v][]%p+l*e[i].b.y*f[e[i].v][]%p)%p;
    }
}

int main(){
    read(n);read(m);int x,y;
    for(rg int i=;i<m;++i)read(x),read(y),add(x,y),add(y,x);
    dfs(,);is[]=;build();
   for(rg int S=;S<(<<tot);++S){
        for(rg int i=;i<=tot;++i)
            if(S&(<<(i-)))
                shall[lx[i]][]=shall[rx[i]][]=;
            else shall[lx[i]][]=;
        dp();ans=(ans+(f[][]+f[][])%p)%p;
        for(rg int i=;i<=tot;++i)
            if(S&(<<(i-)))
                shall[lx[i]][]=shall[rx[i]][]=;
            else shall[lx[i]][]=;
    }
    printf("%d\n",ans);
    return ;
}