DeaphetS

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

題目鏈接：https://ac.nowcoder.com/acm/contest/884/G

題目大意：給定一個樹\(A\)，再給出\(t\)次詢問，問\(A\)中有多少連通子圖與樹\(B_i\)同構(gòu)。\(|A|\leq 2000,t\leq 10000, |B_i|\leq 12\)

題解：本題實際上是Codeforces 762F的加強版，關(guān)于這題的題解請戳這里

　　　本題做法與之前這道題類似，也是預(yù)處理出樹的最小表示法后進(jìn)行樹形DP，但是由于這里有多達(dá)一萬次詢問，所以考慮預(yù)處理枚舉所有點數(shù)不超過\(12\)的樹并求出他們的最小表示。對于如何預(yù)處理所有滿足條件的樹，我的方法是假設(shè)當(dāng)前樹的大小為\(n\)，將第\(n+1\)個點作為當(dāng)前點或其祖先的兒子加入樹中，并繼續(xù)遞歸直至樹的大小達(dá)到\(12\)。這樣預(yù)處理后會發(fā)現(xiàn)點數(shù)不超過\(12\)的樹只有不到\(8000\)個。接下來就是要對樹\(A\)進(jìn)行DP，設(shè)f[i][j]表示有多少以\(i\)為根節(jié)點的子樹與編號為\(j\)的樹同構(gòu)，再令\(ans[j]=\sum_{i=1}^{n}f[i][j]\)，對于每個詢問的答案就是\(\sum ans[j]\)，這里的\(j\)是樹\(B\)以不同點為根時對應(yīng)的編號。

　　　另外，在預(yù)處理的時候，我們同樣可以預(yù)處理出當(dāng)編號為\(j\)的樹的根作為編號為\(i\)的樹的根的兒子合并進(jìn)來之后新樹的編號，這樣的合并關(guān)系只有不到\(14000\)組。這樣對樹\(A\)進(jìn)行DP時就可以枚舉所有這樣的合并關(guān)系進(jìn)行計算，將這一部分時間復(fù)雜度優(yōu)化到\(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 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;
}

View Code

posted @ 2019-07-28 19:29 DeaphetS 閱讀(232) 評論(0) 收藏舉報

刷新頁面返回頂部

DeaphetS

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

公告