[2019牛客多校第四场][G. Tree]

题目链接：https://ac.nowcoder.com/acm/contest/884/G

题目大意：给定一个树\(A\)，再给出\(t\)次询问，问\(A\)中有多少连通子图与树\(B_i\)同构。\(|A|\leq 2000,t\leq 10000, |B_i|\leq 12\)

题解：本题实际上是Codeforces 762F的加强版，关于这题的题解请戳这里

　　　本题做法与之前这道题类似，也是预处理出树的最小表示法后进行树形DP，但是由于这里有多达一万次询问，所以考虑预处理枚举所有点数不超过\(12\)的树并求出他们的最小表示。对于如何预处理所有满足条件的树，我的方法是假设当前树的大小为\(n\)，将第\(n+1\)个点作为当前点或其祖先的儿子加入树中，并继续递归直至树的大小达到\(12\)。这样预处理后会发现点数不超过\(12\)的树只有不到\(8000\)个。接下来就是要对树\(A\)进行DP，设f[i][j]表示有多少以\(i\)为根节点的子树与编号为\(j\)的树同构，再令\(ans[j]=\sum_{i=1}^{n}f[i][j]\)，对于每个询问的答案就是\(\sum ans[j]\)，这里的\(j\)是树\(B\)以不同点为根时对应的编号。

　　　另外，在预处理的时候，我们同样可以预处理出当编号为\(j\)的树的根作为编号为\(i\)的树的根的儿子合并进来之后新树的编号，这样的合并关系只有不到\(14000\)组。这样对树\(A\)进行DP时就可以枚举所有这样的合并关系进行计算，将这一部分时间复杂度优化到\(O(14000n)\)

#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 -__builtin_clz(x);}

int Union(int x,int y){return (x<<len(y))|y;}

int cnt;

set<int>id[];

int uni[MM][MM];

int num_to_id[NN];

int id_to_num[MM];

int f[N][MM];

vector<int>Id[];

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=;i<=n;i++)

        d[i].clear();

      for(int i=;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]=;

      int res=;

      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<<=;

      if(!num_to_id[res])cnt++,mp[cnt]=tmp,id_to_num[cnt]=res,num_to_id[res]=cnt;

      for(int i=;i<tmp.size();i++)

        {

        int R=;

        for(int j=;j<tmp.size();j++)if(j!=i)

          R=Union(R,tmp[j]);

        R<<=;

        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=;i<=n;i++)

        dfs(i,);

      }

    void DP2(int cur,int pre)

      {

      sz[cur]=;

      f[cur][]=;

      for(auto nxt:d[cur])if(nxt!=pre)

        {

        DP2(nxt,cur);

        for(int i=min(,sz[cur]);i>=;i--)

          for(auto ii:Id[i])

            {

            int v=f[cur][ii];

            if(!v)continue;

            for(int j=;j<=min(-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=;i<=min(,sz[cur]);i++)

        for(auto ii:Id[i])

          (ans[ii]+=f[cur][ii])%=MOD;

      }

}S,T;

set<int>s;

int fa[];

vector<int>d[];

void fuck(int cur,int pre)

{

    fa[cur]=pre;

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

      T.d[i]=d[i];

    T.n=cur;

    if(cur==){T.dfs(,);return;}

    int x=cur;

    while(x!=)

      {

      d[x].push_back(cur+);

      fuck(cur+,x);

      d[x].pop_back();

      x=fa[x];

      }

}

int main()

{

    fuck(,);

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

      for(auto j:id[i])Id[i].push_back(j);

    S.read();

    S.DP2(,);

    int t;

    scanf("%d",&t);

    while(t--)

      {

      T.read();

      int ans=;

      s.clear();

      for(int i=;i<=T.n;i++)

        s.insert(T.dfs(i,));

      for(auto x:s)(ans+=S.ans[num_to_id[x]])%=MOD;

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

      }

    return ;

}

巴特西

[2019牛客多校第四场][G. Tree]

最新文章

热门文章