P3349 [ZJOI2016]小星星

题意都需要看题解才能明白我是不是已经废了

题意就是求一个从树\(S\)到图\(T\)的映射，满足若树上的两个点有边，则它们映射在图中的两个点也连有边，且不能有多个点映射到同一个点

我们先不考虑不能有多个点映射到同一个点的限制。设\(dp[u][i]\)表示树上的\(u\)映射为图中的点\(i\)时，\(u\)的子树中合法的方案数。那么只要做一个树形dp即可，复杂度为\(O(n^3)\)

然而如果我们只是按上面那样去做，有可能会产生多个点映射到同一个点的情况。那么我们就要减去图中被映射的点只有\(n-1\)个时的情况。我们可以暴力枚举被剩下的\(n-1\)个点是哪几个，然后再做一次树形dp即可。发现有多减了\(n-2\)个点的情况...

于是不难看出这个其实就是容斥了，枚举图中被选的点，容斥处理即可

//minamoto

#include<bits/stdc++.h>

#define ll long long

#define rint register int

using namespace std;

#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

char buf[1<<21],*p1=buf,*p2=buf;

int read(){

    int res,f=1;char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

const int N=25;

ll dp[N][N],res=0;bool vis[N];int ban[N],mp[N][N];

struct eg{int nx,v;}e[N];int head[N],tot,n,m;

inline void add(int u,int v){e[++tot]={head[u],v},head[u]=tot;}

void dfs(int u){

    vis[u]=1;for(rint i=1;i<=n;++i)dp[u][i]=1;

    for(rint i=head[u];i;i=e[i].nx){

        int v=e[i].v;if(vis[v])continue;dfs(v);

        for(rint j=1;j<=n;++j)if(ban[j]){

            ll sum=0;

            for(rint k=1;k<=n;++k)if(ban[k])sum+=dp[v][k]*mp[k][j];

            dp[u][j]*=sum;

        }else dp[u][j]=0;

    }

}

int main(){

//	freopen("testdata.in","r",stdin);

    n=read(),m=read();

    for(rint i=1,u,v;i<=m;++i)u=read(),v=read(),mp[u][v]=mp[v][u]=1;

    for(rint i=1,u,v;i<n;++i)u=read(),v=read(),add(u,v),add(v,u);

    for(rint k=1;k<=(1<<n)-1;++k){

        int sz=n;for(rint i=1;i<=n;++i)ban[i]=vis[i]=0;

        for(rint i=1,p=k;p;p>>=1,++i)ban[i]=p&1,sz-=p&1;

        dfs(1);ll ret=0;

        for(rint i=1;i<=n;++i)ret+=dp[1][i];

        sz&1?res-=ret:res+=ret;

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

}

巴特西

P3349 [ZJOI2016]小星星

最新文章

热门文章