[Educational Round 17][Codeforces 762F. Tree nesting]

题目大意：给出两个树\(S,T\)，问\(S\)中有多少连通子图与\(T\)同构。\(|S|\leq 1000,|T|\leq 12\)

题解：考虑树的最小表示法（有关知识可戳https://www.byvoid.com/zhs/blog/directed-tree-bracket-sequence），求出\(T\)以不同点为根时所有的子树状态

　　　开始对树\(S\)进行\(DFS\)，求出每个点的状态为\(t\)时的方案数，由于\(t\)还是由\(n\)个数字（括号序列）合并起来的，而且\(n\)不会太大，所以可以用二进制DP求解

　　　对当前点求解时，只需遍历其儿子，将儿子的解并入当前的状态即可。由于一个点可能有若干个形状相同的子树，所以要考虑去重，具体实现见代码

#include<bits/stdc++.h>

using namespace std;

#define N 1001

#define M 1<<12

#define MOD 1000000007

int len(int x){return -__builtin_clz(x);}

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

struct Tree

{

    int n,ans;

    int f[M][];

    vector<int>d[N];

    map<int,int>num[N];

    map<int,vector<int> >mp;

    void read()

      {

      scanf("%d",&n);

      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)

      {

      int res=;

      vector<int>tmp;

      //tmp用来记录子树的状态

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

        tmp.push_back(dfs(nxt,cur));

      sort(tmp.begin(),tmp.end());

      for(auto x:tmp)res=Union(res,x);

      res<<=;

      //res表示当前节点的最小表示

      if(!mp.count(res))mp[res]=tmp;

      //将当前点对应的子树们也记录下来

      return res;

      }

    void getID()

      {

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

        dfs(i,);

      //枚举以所有的点为根的情况

      }

    void DP(int cur,int pre,const Tree &T)

      {

      for(auto nxt:d[cur])if(nxt!=pre)DP(nxt,cur,T);

      for(const auto &pi:T.mp)//枚举T中的所有状态

        {

        auto &types=pi.second;

        int id=pi.first,n=types.size(),now=,lst=;

        for(int i=;i<(<<n);i++)f[i][]=f[i][]=;

        f[][]=;

        //id为当前枚举到的状态，n为当前状态拥有的子树数目，用滚动数组实现儿子们的合并

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

          {

          now^=,lst^=;

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

            f[i][now]=f[i][lst];

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

            if(num[nxt][types[i]])//num[i][j]表示点i的状态为j时方案有多少个

              for(int j=(<<n)-;j>=;j--)

                if(f[j][lst] && !((<<i)&j) && !(i && types[i]==types[i-] && !((<<(i-))&j)))

                  // (i && types[i]==types[i-1] && !((1<<(i-1))&j)代表的是

                  //当前枚举的子树和前一个子树同构 ，且前一个子树的状态未记录

                  (f[(<<i)|j][now]+=1ll*f[j][lst]*num[nxt][types[i]]%MOD)%=MOD;

          }

        if(f[(<<n)-][now])

          {

          num[cur][id]=f[(<<n)-][now];//集齐了所有子树即为对应num的答案

          if(len(id)==*T.n)(ans+=num[cur][id])%=MOD;//id的二进制长度为2m则说明一定是根节点的状态,加入答案

          }

        }

      }

}S,T;

int main()

{

    S.read();

    T.read();

    T.getID();

    S.DP(,,T);

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

}

秒客网

[Educational Round 17][Codeforces 762F. Tree nesting]

相关文章