「2019冬令营提高组」树

题意分析

神题呀

这题让你求\(n\)个结点的树当中有所少个联通块是与\(m\)个节点的树同构的

首先我们对于\(m\) 枚举根节点

然后 ? ? ? 树上哈希~~鄙人也震惊到了~~

我们对于当前节点

搜出所有的儿子后把儿子的哈希值\(sort\)一遍(防止重复)

然后暴力合并

同时我们对于形态相同的子树需要用阶乘防止重复

哈希完之后如果当前已经出现了我们就\(continue\)

用\(set\)维护一下就可以了

然后我们从遍历\(n\)个节点的树

我们树形\(dp\)考虑如何合并

注意 难点来了

我们考虑当前遍历到了\(n\)树\(now\)这个点

同时令\(m\)树的\(j\)点同其匹配

先提取出当前\(j\)节点的儿子然后状压一下

我们同时从左往右扫描

我们同时扫描如果当前的\(i\)同\(j\)的儿子不匹配的话

我们就加上原来的值

否则的话

就是当前\(j\)的儿子同\(i\)匹配的方案数* 原有未匹配的方案书

这里比较麻烦待会在代码里会详解

然后我们累加即可

最后累加到对答案的贡献里

CODE:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x7fffffff
#define N 2050
#define IL inline
#define M 1008611
#define D double
#define ull unsigned long long
#define mod 1000000007
#define bas 233
#define R register
using namespace std;
templateIL void read(T &_)
{
    T __=0,___=1;char ____=getchar();
    while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
    while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
    _=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
ll n,m,root,have,ans;
vector cdy[N],wzy[N];
set vis;
ll fa[N],tmp[N];
ll dp[N][N],fro[N][N];
IL ll qpow(ll x,ll y)
{ll res=1;for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;return res;}
IL ull dfs(ll now,ll fat)
{
	vector son;
	ull res=bas;
	for(R ll i=0;i<(ll)wzy[now].size();++i)
	if(wzy[now][i]!=fat) fa[wzy[now][i]]=now,son.push_back(dfs(wzy[now][i],now));
	sort(son.begin(),son.end());
	ll len=1;
	for(R ll i=0;i<(ll)son.size();++i)
	{
		if(i&&son[i]==son[i-1]) ++len;
		else len=1;
		res+=son[i];
		have=have*qpow(len,mod-2)%mod;
	}
	return res*res%mod;
}
IL void DFS(ll now,ll fat)
{
	for(R ll i=0;i<(ll)cdy[now].size();++i)
	if(cdy[now][i]!=fat) DFS(cdy[now][i],now);
	for(R ll j=1;j<=m;++j)
	{
		ll cnt=0,id=0;
		for(R ll i=0;i<(ll)wzy[j].size();++i)
		if(wzy[j][i]!=fa[j]) tmp[++cnt]=wzy[j][i];
		ll all=(1<


HEOI 2019 RP++

「2019冬令营提高组」树

题意分析

题意分析

CODE:

HEOI 2019 RP++

相关

标签