cf762f Tree nesting
给定两棵树 \(S,T\) ，求 \(S\) 有多少个连通子图与 \(T\) 同构 . 模 \(10^9+7\) .
\(1\leq |S|\leq 1000,1\leq |T|\leq 12\)
因为 \(|T|\) 的大小只有 \(12\) ，首先考虑到状压，但是，两个状态 \(s_1\) 和 \(s_2\) 可能在 \(T\) 中同构，就会重复计算 .
但还是因为 \(|T|\) 非常小，考虑将 \(T\) 中每一个不同的有根子树都处理出来 ( 有根是因为必须在 \(S\) 上对应一个节点斤进行树形 dp )，此时需要用到有根树同构的判断，树哈希 . 这个数量其实是小的，没有自己测过，最多只会在是在几百上下 .
用 \(dp(i,j)\) 表示当前以 \(i\) 为根，对于 \(T\) 的状态是 \(j\) 时的方案数 .
此时这个 \(dp\) 状态就不会重复计算了，现在的问题就是如何转移 .
此时需要多增加一些状态，每一个代表这一个集合，表示儿子节点对应在 \(T\) 上的状态是 \(\{s_1,s_2,\cdots ,s_k\}\) .
其中有很多状态是无用的，考虑搜索的时候减枝减掉，然后得到的节点个数和之前的状态数，其实最多还是几百 .
但是现在就可以转移了，考虑用 \(dp(u)\) 合并每一个 \(dp(v)\) . 对于状态 \(s_i\) 与 \(s_j\) 合并，最多只可能有一个合法的转移方向 \(s_k\) .
答案即为 \(\sum dp(i,s_T)\) .
时间复杂度 : \(O(ns^2)\)
空间复杂度 : \(O(ns)\)
但是实际上跑得很快，我在 cf 下只跑了 31ms .
code
#include
using namespace std;
const int mod=1e9+7;
const int pri[]={0,2,3,5,7,11,13,17,19,23,29,31,37};
int n,m;
vectorgs[1010],gt[15];
int subtree_id=0;
mapmpt[15];
int hf[100],hsz[100];
vectorrt;
int f[15],sz[15];
void dfs(int id,vectorv,vectortg);
void get_hash(int x,int fa){
sz[x]=f[x]=1;
vectorv;
for(int i=0;i<(int)gt[x].size();i++){
int to=gt[x][i];
if(to==fa)continue;
get_hash(to,x);
sz[x]+=sz[to];
f[x]=(f[x]+1ll*f[to]*pri[sz[to]]%mod)%mod;
v.push_back(mpt[sz[to]][f[to]]);
}
sort(v.begin(),v.end());
dfs(0,{},v);
if(mpt[sz[x]].find(f[x])==mpt[sz[x]].end()){
mpt[sz[x]][f[x]]=subtree_id;
hf[subtree_id]=f[x];
hsz[subtree_id]=sz[x];
v.push_back(subtree_id);
subtree_id++;
}
}
map,int>mpc;
int tid[50010],com_id=0;
void dfs(int id,vectorv,vectortg){
if(id==(int)tg.size()){
if(mpc.find(v)==mpc.end()){
mpc[v]=com_id;
tid[com_id]=-1;
com_id++;
}
return;
}
dfs(id+1,v,tg);
v.push_back(tg[id]);
dfs(id+1,v,tg);
}
int nxt[50010][110];
int dp[1010][110],g[1010][50010],h[50010];
void upd(int a,int b){
memset(h,0,sizeof(h));
for(int i=0;i>n;
for(int i=0;i>u>>v;
u--;v--;
gs[u].push_back(v);
gs[v].push_back(u);
}
cin>>m;
for(int i=0;i>u>>v;
u--;v--;
gt[u].push_back(v);
gt[v].push_back(u);
}
for(int i=0;i,int>::iterator it=mpc.begin();it!=mpc.end();it++){
vectorv=it->first;
int nsz=1,h=1;
for(int i=0;i<(int)v.size();i++){
nsz+=hsz[v[i]];
h=(h+1ll*pri[hsz[v[i]]]*hf[v[i]]%mod)%mod;
}
if(mpt[nsz].find(h)!=mpt[nsz].end())tid[it->second]=mpt[nsz][h];
}
for(map,int>::iterator it=mpc.begin();it!=mpc.end();it++){
vectorv=it->first;
for(int i=0;inv=v;
nv.push_back(i);
sort(nv.begin(),nv.end());
if(mpc.find(nv)!=mpc.end())nxt[it->second][i]=mpc[nv];
else nxt[it->second][i]=-1;
}
}
dfs(0,-1);
cout<