[Educational Codeforces Round 17 F (762F)] Tree nesting

2019-11-14 09:29:46

字体：大中小

来源：转载

供稿：网友

题意

我把educational round 理解为 eazy round真是too young too simple，明明是 be educated round

给定两棵树S $S$ ,T $T$ ，|S|≤1000,|T|≤12 $|S|/le 1000,|T|/le 12$ 询问S $S$ 中有多少个子图（我觉着讲子树不太形象吧）与T $T$ 同构。

题解

树的同构问题一般都是牵扯到最小表示法的。

官方题解给出了一个trick，同构的树总有一个点或一条边位置不变，也就是树的中心，或者两个中心之间的边。按照题解的说法，求以中心为树根的最小表示，然后在S $S$ 中枚举点做树根统计得到T $T$ 最小表示的方案数？不太会写。于是去膜了一发毛爷爷。

首先，求出T $T$ 以每个点为根的最小表示，具体方法为用1表示进入一棵子树，0表示离开一棵子树，01串就能表示一整棵树，最小表示要求每个节点都要对儿子们的最小表示排个序，然后拼起来成为这棵子树的最小表示。在这个过程中记录下来所有的状态（包含子树状态）。

再然后就是dfs一遍S $S$ 树了。先dfs儿子们，使儿子们求出得到记录中的各个状态（遍历S $S$ 时得到的状态们）的方案数。然后枚举当前节点的所有状态，每个状态都要求这个节点有一定的状态集合，这时通过枚举所有的儿子的所有状态进行dp。具体实现比较复杂，详见代码。

另外，原来c++11用着这么爽，编译命令加个-std=c++11就行了（似乎需要gcc4.8.x以上？我是gcc4.9.2）。

代码

/// by ztx/// blog.csdn.net/hzoi_ztx/// learnt from myy (matthew99:http://codeforces.com/contest/762/submission/24128833)#define Rep(i,l,r) for(i=(l);i<=(r);i++)#define rep(i,l,r) for(i=(l);i< (r);i++)#define r(x) read(x)typedef long long ll ;int CH , NEG ;template <typename TP>inline void read(TP& ret) { ret = NEG = 0 ; while (CH=getchar() , CH<'!') ; if (CH == '-') NEG = true , CH = getchar() ; while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ; if (NEG) ret = -ret ;}using namespace std; #define kN 1000LL#define kM 12LL#define pb push_back#define kMod 1000000007LLint n, m, ANS;int now[(1<<kM)+5], nxt[(1<<kM)+5];vector<int> G[kN+5], g[kM+5];map<int,vector<int> > STA;map<int,int> ans[kN+5];inline int blen(int x) { return 32 - __builtin_clz(x); } // __builtin_clz() count leading zerosinline int combine(int x, int y) { return x << blen(y) | y; }inline void P(int x) { for (int i = 30; ~i; i -- ) { PRintf("%d",int(bool(x&(1<<i)))); } puts("");}int dfs0(int u,int fa = 0) { int h = 1; vector<int> H; for (auto v : g[u]) if (v != fa) H.pb(dfs0(v,u)); sort(H.begin(), H.end()); // minimum representation of tree for (auto s : H) h = combine(h,s); h <<= 1;//printf("h[%d] = ",u);//P(h); if (!STA.count(h)) STA[h] = H; return h;}void dfs(int u,int fa = 0) { vector<int> chd; for (auto v : G[u]) if (v != fa) chd.pb(v), dfs(v,u); for (const auto &sta : STA) { auto &H = sta.second; int h = sta.first, N = H.size(); memset(now, 0, sizeof(int)*(1<<N)); now[0] = 1; for (auto ch : chd) { memcpy(nxt, now, sizeof(int)*(1<<N)); for (int i = 0; i < N; i ++ ) { int num = ans[ch][H[i]]; if (!num) continue; for (int j = (1<<N)-1; j >= 0; j -- ) if (now[j] && !(j>>i & 1) && !(i && H[i]==H[i-1] && !(j>>(i-1) & 1))) (nxt[j|(1<<i)] += (ll)now[j]*num%kMod) %= kMod; } memcpy(now, nxt, sizeof(int)*(1<<N)); } if (now[(1 << N) - 1]) { ans[u][h] = now[(1 << N) - 1]; if (blen(h) == (m<<1)) (ANS += now[(1<<N)-1]) %= kMod; } }}int main() { int i, u, v; r(n); rep (i,1,n) r(u), r(v), G[u].pb(v), G[v].pb(u); r(m); rep (i,1,m) r(u), r(v), g[u].pb(v), g[v].pb(u); Rep (i,1,m) dfs0(i); dfs(1); (ANS += kMod) %= kMod; printf("%d/n", ANS); END: getchar(), getchar(); return 0;}

上一篇：使用C#将HTML文本转换为普通文本，去掉所有的Html标记

下一篇：588A. Duff and Meat