Educational Codeforces Round 17F Tree nesting

时间：2023-11-23 23:50:50

来自FallDream的博客，未经允许，请勿转载， 谢谢。

给你两棵树，一棵比较大(n<=1000)，一棵比较小(m<=12) 问第一棵树中有多少个连通子树和第二棵同构。

答案取膜1e9+7

考虑在大树中随便选个根，然后在小的那棵那里枚举一个根作为大树中深度最小的节点（注意哈希判同构）

然后f[x][y]表示大树的x节点作为小树的y节点的方案数。

如果y是叶子结点，f[x][y]=1

否则要用x的儿子中的一些节点表示y的所有叶子节点。

考虑一个状压dp，g[i][s]表示前i个儿子表示了小树的s集合内的节点的方案数，容易转移。

然后如果y有一些儿子同构，则需要除以个数的阶乘。

复杂度上界是n*m*2^m

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

#include<map>

#define MN 1000

#define mod 1000000007

using namespace std;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

unsigned long long ha[MN+];vector<unsigned long long> v[MN+];map<unsigned long long,int> mp,mp2;

int n,m,head[MN+],Head[MN+],fa[MN+],cnt=,f[MN+][],F[<<],size[MN+],son[MN+],q[MN+],ans=,now,P[];

struct edge{int to,next;}e[MN*+];

inline void R(int&x,int y){x+=y;x>=mod?x-=mod:;}

inline void ins(int*H,int f,int t)

{

    e[++cnt]=(edge){t,H[f]};H[f]=cnt;

    e[++cnt]=(edge){f,H[t]};H[t]=cnt;

}

int pow(int x,int k)

{

    int sum=;

    for(;k;k>>=,x=1LL*x*x%mod)

        if(k&) sum=1LL*sum*x%mod;

    return sum;

}

void GetHa(int x,int f)

{

    ha[x]=;size[x]=;v[x].clear();fa[x]=f;

    for(int i=Head[x];i;i=e[i].next)

        if(e[i].to!=f)

        {

            GetHa(e[i].to,x);

            v[x].push_back(ha[e[i].to]);

        }

    son[x]=v[x].size();

    sort(v[x].begin(),v[x].end());

    for(int i=;i<v[x].size();++i) ha[x]=ha[x]*+v[x][i];

    ha[x]=ha[x]*+size[x];

}

void Solve(int x,int fat)

{

    int num=;

    for(int i=head[x];i;i=e[i].next)

        if(e[i].to!=fat) Solve(e[i].to,x),++num;

    for(int i=;i<=m;++i)

    {

        if(!son[i]){f[x][i]=;continue;}

        if(num<son[i]){f[x][i]=;continue;}

        for(int k=;k<<<son[i];++k)F[k]=;

        F[]=;int top=;

        for(int j=Head[i];j;j=e[j].next) if(e[j].to!=fa[i]) q[++top]=e[j].to,++mp2[ha[e[j].to]];

        for(int j=head[x];j;j=e[j].next)

            if(e[j].to!=fat)

            {

                for(int s=(<<top)-;~s;--s)

                    for(int k=;k<=top;++k) if(f[e[j].to][q[k]])

                            if(!(s&(<<k-))) R(F[s|(<<k-)],1LL*F[s]*f[e[j].to][q[k]]%mod);

            }

        f[x][i]=F[(<<top)-];

        for(int j=;j<=top;++j)

            if(mp2[ha[q[j]]]) f[x][i]=1LL*f[x][i]*pow(P[mp2[ha[q[j]]]],mod-)%mod,mp2[ha[q[j]]]=;

    }

    R(ans,f[x][now]);

}

int main()

{

    n=read();P[]=;

    for(int i=;i<=;++i) P[i]=1LL*P[i-]*i%mod;

    for(int i=;i<n;++i) ins(head,read(),read());m=read();

    for(int i=;i<m;++i) ins(Head,read(),read());

    for(int i=;i<=m;++i)

    {

        GetHa(i,);

        if(mp[ha[i]]) continue;

        memset(f,,sizeof(f));mp[ha[i]]=;

        now=i;Solve(,);

    }

    printf("%d\n",ans);

    return ;

}

相关文章