BZOJ 4455: [Zjoi2016]小星星

时间：2021-07-18 05:55:25

Sol

容斥原理+树形DP.

这道题用的容斥思想非常妙啊！主要的思路就是让所有点与S集合中的点对应,可以重复对应,并且可以不用对应完全(意思是是S的子集也可以).这样他有未对应完全的,那就减去,从全都一一对应到少对应几个,减号套减号,就形成了容斥关系,看S中元素个数与n的关系,如果相差奇数个,那就减去,相差偶数个,那就加上.用树形DP转移,枚举当前节点选哪一个,再枚举子节点选哪一个,如果两个有连线就统计到答案里.因为每个节点只进入一次,转移是 \(n^2\) 的,枚举子集是 \(2^n\) 总复杂度就是 \(O(2^nn^3)\)

Code

/**************************************************************

    Problem: 4455

    User: BeiYu

    Language: C++

    Result: Accepted

    Time:6200 ms

    Memory:1296 kb

****************************************************************/

#include<cstdio>

#include<vector>

#include<iostream>

using namespace std;

const int N = 18;

typedef long long LL;

int n,m,S;LL ans;

LL f[N][N];

int q[N],t,pow2[N];

bool b[N][N];

vector<int> g[N];

void DP(int x,int fa=0){

    for(int i=1;i<=t;i++) f[x][q[i]]=1;

    for(int i=0,v;i<g[x].size();i++) if((v=g[x][i])!=fa){

        DP(v,x);

        for(int j=1;j<=t;j++){

            LL tmp=0;

            for(int k=1;k<=t;k++) if(b[q[j]][q[k]]) tmp+=f[v][q[k]];

            f[x][q[j]]*=tmp;

        }

    }

}

void calc(const int &S){ t=0;for(int i=1;i<=n;i++) if(S&pow2[i-1]) q[++t]=i; }

inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();

    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }

int main(){

    n=in(),m=in();pow2[0]=1;for(int i=1;i<18;i++) pow2[i]=pow2[i-1]<<1;

    for(int i=1,u,v;i<=m;i++) u=in(),v=in(),b[u][v]=b[v][u]=1;

    for(int i=1,u,v;i<n;i++) u=in(),v=in(),g[u].push_back(v),g[v].push_back(u);

    for(S=1;S<(1<<n);S++){

        calc(S);DP(1,0);LL tmp=0;

        for(int i=1;i<=t;i++) tmp+=f[1][q[i]];

        if((n-t)&1) ans-=tmp;else ans+=tmp;

    }return printf("%lld\n",ans),0;

}

　　

相关文章