sss

<更新提示>

<第一次更新>

<正文>

Tree nesting (CF762F)

Description

有两个树 S、T，问 S 中有多少个互不相同的连通子图与 T 同构。由于答案可能会很大，请输出答案模 1000000007 后的值。
两个连通子图 P、Q 称为互不相同的，当且仅当存在一个点 v∈S，使得 v∈P 与 v∈Q 恰好有一个成立。
图 G 与 H（在此题中 G 与 H 均为树）同构的定义为，存在一个一一映射 f， G 中任意一点 u 在 H 中都有唯一的点 v 与之对应；同样对 H 中任意一点 v 也有唯一的在 G 中的点 u 与之对应。不妨设 f(u)=v, f-1 (v)=u(u∈G, v∈H)，则还有对任意 A, B∈G，若 A 与 B 之间有边相连，则 f(A)与 f(B)在 H 中也有边相连；同样的，对任意 A, B∈H，若 A 与 B 之间有边相连，则 f -1 (A)与 f -1 (B)在 G 中也有边相连。

Input Format

第一行一个正整数|S|表示树 S 的大小
接下来|S|-1 行都有两个正整数 ui , vi表示|S|中的边
接下来一行一个正整数|T|表示树 T 的大小
接下来|T|-1 行都有两个正整数 xi , yi表示|T|中的边

Output Format

一行，一个正整数表示答案模 1000000007 后的值

Sample Input

Sample Output

解析

一道(cf)毒瘤题。

看到树同构于是想到树的最小表示法，也就是树的括号序列。以点(x)为根的子树的括号序列就是(x)所有子树的括号序列按字典序从小到大接起来，然后在最外面再套一对括号，这样就能唯一的表示一颗树。

我们先以(T)的每一个点为根，求一遍(T)的最小表示法，由于(T)的大小比较小，所以最小表示法序列还可以方便地用二进制数先存起来。

然后，我们考虑在(S)上用(dp)计数。(S)的连通子图和(T)同构，其大小首先一定等于(T)的大小，所以需要(dp)的范围也是很小的，考虑用状压(dp)。设(f[x][S])代表以(x)为根的子树中，最小表示法序列匹配为(S)的方案数。

由同构的性质可知，要转移得到(S)，其子最小表示法序列必然要是(T)中一样的子最小表示法，这启发我们在求(T)的最小表示法时，把最小表示法是由哪几个子最小表示法序列拼凑起来的也记录下来，这个我们可以用(map+vector)。

接下来考虑如何(dp)，对于一个节点(x)，我们先将所有子节点先(dp)，再利用子节点的(dp)值来更新。首先我们一定要枚举(T)的每一个最小表示法序列，然后我们就考虑现在节点(x)的儿子们和当前枚举到最小表示法序列的子序列们的一一匹配，如果能匹配上，就代表我们可以转移。

若(x)的第(i)个儿子为(ch_i)，当前最小表示法序列的第(j)个子序列为(cur_j)，那么我们要看的就是(f[ch_i][cur_j])的值，这就代表了儿子(i)与子序列(j)合法配对的方案。对于所有的((i,j))满足(f[ch_i][cur_j]>0)都是我们需要考虑的，因为这些都代表了一种配对的可能。

如何利用子节点的(f)值转移得到当前节点呢？我们发现不能直接转移。可是再观察可以发现，这是另一个状压(dp)。

设当前最小表示法序列是由(len)个子最小表示法序列构成的，那么状态(g[i][k])代表前(i)个儿子，子最小表示法序列中已经配对状态为(k)的配对方案数。由(i)来划分阶段，我们很快就可以列出状态转移方程：

[g[i][k|2^j]=sum_{j ot in k} g[i-1][k]*f[ch_i][cur_j] ]

为了简便，我们可以用滚动数组的技巧把(g)化简成两个一维的数组。

注意，这个状压(dp)还有一点坑：若当前的最小表示法序列有两个相同的子序列，那么我们可能会对两个子序列重复计数(就是把((10)_2)和((01)_2)这两种本质相同的选法都统计了一遍)。我们只需要最转移时特判一下即可。

好了，这样树形(dp)也基本上做完了，设(x)有(p)个儿子，那么我们就可以用(g[p][2^{len}-1])来更新(f[x][S])。当然，如果(S)的长度为(2m)的话，就对应了(T)整棵树的某个最小表示法，可以直接累加到最后的答案里。

(Code:)

#include <bits/stdc++.h>
using namespace std;
const int N = 1020 , M = 15;
const int Mod = 1000000007;
int n,m,t1,t2,Head1[N],Head2[N];
int g[1<<M],p[1<<M],ans;
map < int , vector<int> > List;
map < int , int > f[N];
struct edge { int ver,next; } e1[N*2],e2[N*2];
inline void insert(int x,int y,int id)
{
    if ( id == 1 )
        e1[++t1] = (edge){y,Head1[x]} , Head1[x] = t1,
        e1[++t1] = (edge){x,Head1[y]} , Head1[y] = t1;
    if ( id == 2 )
        e2[++t2] = (edge){y,Head2[x]} , Head2[x] = t2,
        e2[++t2] = (edge){x,Head2[y]} , Head2[y] = t2;
}
inline int read(void)
{
    int x = 0 , w = 0; char ch = ' ';
    while ( !isdigit(ch) ) w |= ch=='-' , ch = getchar();
    while ( isdigit(ch) ) x = x*10 + ch-48 , ch = getchar();
    return w ? -x : x;
}
inline void input(void)
{
    n = read();
    for (int i=1;i<n;i++)
        insert( read() , read() , 1 );
    m = read();
    for (int i=1;i<m;i++)
        insert( read() , read() , 2 );
}
inline int lenth(int x) { return 32 - __builtin_clz(x); }
inline void connect(int &x,int y) { x = x << lenth(y) | y; }
inline int Ergodic(int x,int fa)
{
    int S = 1;
    vector < int > cur;
    for (int i=Head2[x];i;i=e2[i].next)
    {
        int y = e2[i].ver;
        if ( y == fa ) continue;
        cur.push_back( Ergodic( y , x ) );
    }
    sort( cur.begin() , cur.end() );
    vector < int > :: iterator it;
    for (it=cur.begin();it!=cur.end();it++)
        connect( S , *it );
    S <<= 1;
    if ( !List.count( S ) ) List[S] = cur;
    return S;
}
inline void dp(int x,int fa)
{
    vector < int > ch;
    for (int i=Head1[x];i;i=e1[i].next)
    {
        int y = e1[i].ver;
        if ( y == fa ) continue;
        ch.push_back( y ) , dp( y , x );
    }
    map < int , vector< int > > :: iterator it;
    for (it=List.begin();it!=List.end();it++)
    {
        vector < int > cur = it -> second;
        int S = it -> first , len = cur.size();
        memset( g , 0 , sizeof g );
        g[0] = 1;
        for (int i=0;i<ch.size();i++)
        {
            memcpy( p , g , sizeof g );
            for (int j=0;j<len;j++)
            {
                int val = f[ch[i]][cur[j]];
                if ( val == 0 ) continue;
                for (int k=(1<<len)-1;k>=0;k--)
                    if ( g[k] && !( k >> j & 1 ) && ( j == 0 || cur[j] != cur[j-1] || ( k >> (j-1) & 1 ) ) )
                        p[k|(1<<j)] = ( p[k|(1<<j)] + 1LL * g[k] * val % Mod ) % Mod;
            }
            memcpy( g , p , sizeof p );
        }
        if ( g[(1<<len)-1] )
        {
            f[x][S] = g[(1<<len)-1];
            if ( lenth(S) == (m<<1) )
                ans = ( ans + f[x][S] ) % Mod;
        }
    }
}
int main(void)
{
    input();
    for (int i=1;i<=m;i++)
        Ergodic( i , 0 );
    dp( 1 , 0 );
    printf("%d
",ans);
    return 0;
}

<后记>