题意分析

题意分析

神题呀

这题让你求\(n\)个结点的树当中有所少个联通块是与\(m\)个节点的树同构的

首先 我们对于\(m\) 枚举根节点

然后 ? ? ? 树上哈希鄙人也震惊到了

我们对于当前节点

搜出所有的儿子后 把儿子的哈希值\(sort\)一遍(防止重复)

然后暴力合并

同时我们对于形态相同的子树需要用阶乘防止重复

哈希完之后 如果当前已经出现了 我们就\(continue\)

用\(set\)维护一下就可以了

然后我们从遍历\(n\)个节点的树

我们树形\(dp\)考虑如何合并

注意 难点来了

我们考虑 当前遍历到了\(n\)树\(now\)这个点

同时令\(m\)树的\(j\)点同其匹配

先提取出当前\(j\)节点的儿子 然后状压一下

我们同时从左往右扫描

我们同时扫描如果当前的\(i\)同\(j\)的儿子不匹配的话

我们就加上原来的值

否则的话

就是当前\(j\)的儿子同\(i\)匹配的方案数* 原有未匹配的方案书

这里比较麻烦 待会在代码里会详解

然后我们累加即可

最后累加到对答案的贡献里

CODE:

/*-------------OI使我快乐-------------*/
ll n,m,root,have,ans;
vector<ll> cdy[N],wzy[N];
set<ll> vis;
ll fa[N],tmp[N];
ll dp[N][N],fro[N][N];
IL ll qpow(ll x,ll y)
{ll res=1;for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;return res;}
IL ull dfs(ll now,ll fat)
{
    vector<ull> son;
    ull res=bas;
    for(R ll i=0;i<(ll)wzy[now].size();++i)
    if(wzy[now][i]!=fat) fa[wzy[now][i]]=now,son.push_back(dfs(wzy[now][i],now));
   //预处理出父亲以及儿子的哈希值
    sort(son.begin(),son.end());
    //排序防止重复
    ll len=1;
    for(R ll i=0;i<(ll)son.size();++i)
    {
        if(i&&son[i]==son[i-1]) ++len;
        else len=1;
        res+=son[i];
        have=have*qpow(len,mod-2)%mod;
     //相同的形态存在(n!)中重复情况
    }
    return res*res%mod;
}
IL void DFS(ll now,ll fat)
{
    for(R ll i=0;i<(ll)cdy[now].size();++i)
    if(cdy[now][i]!=fat) DFS(cdy[now][i],now);
   //我们利用递归处理出儿子节点的dp值
    for(R ll j=1;j<=m;++j)
    {
        ll cnt=0,id=0;
        for(R ll i=0;i<(ll)wzy[j].size();++i)
        if(wzy[j][i]!=fa[j]) tmp[++cnt]=wzy[j][i];
        ll all=(1<<cnt)-1;
   //我们提出匹配点所有儿子并且状压一下
        fro[0][0]=1;
        for(R ll i=0;i<(ll)cdy[now].size();++i)
        {
            if(cdy[now][i]==fat) continue;
            ll v=cdy[now][i];
            ++id;
            for(R ll k=0;k<=all;++k) fro[id][k]=(fro[id][k]+fro[id-1][k])%mod;
        //一种情况是不匹配   
            for(R ll k=1;k<=cnt;++k)
            {
                for(R ll p=0;p<=all;++p)
                if(p&(1<<(k-1)))
                fro[id][p]=(fro[id][p]+fro[id-1][p^(1<<(k-1))]*dp[v][tmp[k]]%mod)%mod;
   //匹配的话 之前未存在对应状态的方案数*当前点匹配的方案数        
            }
        } 
        dp[now][j]=(dp[now][j]+fro[id][all])%mod;
    //我们自然是累加全部匹配的方案数
     for(R ll i=0;i<=id;++i)
         for(R ll k=0;k<=all;++k)
          fro[i][k]=0;
    //这是一个临时数组 需要清空
    }
}
int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    vis.clear();
    read(n);
    for(R ll i=1,x,y;i<n;++i)
    {
        read(x);read(y);
        cdy[x].push_back(y);cdy[y].push_back(x);
    }
    read(m);
    for(R ll i=1,x,y;i<m;++i)
    {
        read(x);read(y);
        wzy[x].push_back(y);wzy[y].push_back(x);
    }
    for(R ll i=1;i<=m;++i)
    {//枚举当前m树的根节点 从而对应不同的形态
        fa[root=i]=0;
        have=1;
        ll key=dfs(root,0);//树哈希
        if(vis.count(key)) continue;vis.insert(key);
        DFS(1,0);
        for(R ll j=1;j<=n;++j)
        ans=(ans+dp[j][i]*have%mod)%mod;
     //我们需要除以重复的情况数   
        memset(dp,0,sizeof dp);
    }
    printf("%lld\n",ans);
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

HEOI 2019 RP++

「2019冬令营提高组」树

原文：https://www.cnblogs.com/LovToLZX/p/10590555.html