Topic link: https://ac.nowcoder.com/acm/contest/884/G

Main idea of the title: Given a tree (A), then give (t) a question and ask how many connected subgraphs in (A) are isomorphic to the tree (B_i). \ (| A | Leq 2000, t Leq 10000, | B_i | Leq 12\)

Problem Solution: This question is actually an enhanced version of Codeforces 762F, and the solution to this question Please stamp here.

This problem is similar to the previous one, and it is also the minimum representation of tree after pre-processing. But since there are as many as 10,000 queries, we consider pre-processing to enumerate all trees whose points do not exceed (12) and find their minimum representation. For preprocessing all eligible trees, my approach is to assume that the current tree size is (n), add (n+1\\\\\\\\\\\ After pretreatment, it will be found that there are fewer than \(12\) trees with points less than \\\\\. The next step is to do DP for tree\((A\((\\\(\\\\\\(\\\\\\\\\\\\The number corresponding to the root of (B) is different.

In addition, in the pre-processing, we can also pre-process the number of new trees when the root of the tree numbered \\\\\\\\\\\\\ In this way, all such merging relationships can be enumerated and calculated when DP is applied to tree\\\\A\\\\\\

#include<bits/stdc++.h>
using namespace std;
#define N 2001
#define M 1<<12
#define MM 8001 
#define NN 16773121
#define MOD 1000000007
int len(int x){return 32-__builtin_clz(x);}
int Union(int x,int y){return (x<<len(y))|y;}
int cnt;
set<int>id[13];
int uni[MM][MM];
int num_to_id[NN];
int id_to_num[MM];
int f[N][MM];
vector<int>Id[13];
struct Tree
{
    int sz[N];
    int n,ans[NN];
    vector<int>d[N];
    vector<int>mp[MM];
    void read()
      {
      scanf("%d",&n);
      for(int i=1;i<=n;i++)
        d[i].clear();
      for(int i=2;i<=n;i++)
        {
        int u,v;
        scanf("%d%d",&u,&v);
        d[u].push_back(v);
        d[v].push_back(u);
        }
      }
    int dfs(int cur,int pre)
      {
      sz[cur]=1;
      int res=1;
      vector<int>tmp;
      for(auto nxt:d[cur])if(nxt!=pre)
        tmp.push_back(dfs(nxt,cur)),sz[cur]+=sz[nxt];
      sort(tmp.begin(),tmp.end());
      for(auto x:tmp)res=Union(res,x);
      res<<=1;
      if(!num_to_id[res])cnt++,mp[cnt]=tmp,id_to_num[cnt]=res,num_to_id[res]=cnt;
      for(int i=0;i<tmp.size();i++)
        {
        int R=1;
        for(int j=0;j<tmp.size();j++)if(j!=i)
          R=Union(R,tmp[j]);
        R<<=1;
        uni[num_to_id[R]][num_to_id[tmp[i]]]=num_to_id[res];
        }
      id[sz[cur]].insert(num_to_id[res]);
      return res;
      }
    void getID()
      {
      for(int i=1;i<=n;i++)
        dfs(i,0);
      }
    void DP2(int cur,int pre)
      {
      sz[cur]=1;
      f[cur][1]=1;
      for(auto nxt:d[cur])if(nxt!=pre)
        {
        DP2(nxt,cur);
        for(int i=min(12,sz[cur]);i>=1;i--)
          for(auto ii:Id[i])
            {
            int v=f[cur][ii];
            if(!v)continue;
            for(int j=1;j<=min(12-i,sz[nxt]);j++)
              for(auto jj:Id[j])
                (f[cur][uni[ii][jj]]+=v*f[nxt][jj]%MOD)%=MOD;
            }
        sz[cur]+=sz[nxt];
        }
      for(int i=1;i<=min(12,sz[cur]);i++)
        for(auto ii:Id[i])
          (ans[ii]+=f[cur][ii])%=MOD;
      }
}S,T;
set<int>s;
int fa[13];
vector<int>d[13];
void fuck(int cur,int pre)
{
    fa[cur]=pre;
    for(int i=1;i<=12;i++)
      T.d[i]=d[i];
    T.n=cur;
    if(cur==12){T.dfs(1,0);return;}
    int x=cur;
    while(x!=0)
      {
      d[x].push_back(cur+1);
      fuck(cur+1,x);
      d[x].pop_back();
      x=fa[x];
      }
}
int main()
{
    fuck(1,0);
    for(int i=1;i<=12;i++)
      for(auto j:id[i])Id[i].push_back(j);
    S.read();
    S.DP2(1,0);
    int t;
    scanf("%d",&t);
    while(t--)
      {
      T.read();
      int ans=0;
      s.clear();
      for(int i=1;i<=T.n;i++)
        s.insert(T.dfs(i,0));
      for(auto x:s)(ans+=S.ans[num_to_id[x]])%=MOD;
      printf("%d\n",ans);
      }
    return 0;
}