题意分析

神题呀

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

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

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

我们对于当前节点

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

然后暴力合并

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

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

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

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

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

注意 难点来了

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

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

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

我们同时从左往右扫描

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

我们就加上原来的值

否则的话

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

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

然后我们累加即可

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

CODE:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define ll long long#define inf 0x7fffffff#define N 2050#define IL inline#define M 1008611#define D double#define ull unsigned long long#define mod 1000000007#define bas 233#define R registerusing namespace std;template
                   
                    IL void read(T &_){ T __=0,___=1;char ____=getchar(); while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();} while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();} _=___ ? __:-__;}/*-------------OI使我快乐-------------*/ll n,m,root,have,ans;vector
                    
                      cdy[N],wzy[N];set
                     
                       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
                      
                        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; } 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); 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<