序章-弗兰德的秘密
背景介绍
弗兰德，我不知道这个地方对我意味着什么。这里是一切开始的地方。3年前，还是个什么都没见过的少年，来到弗兰德的树下，走进了封闭的密室，扭动的封尘已久机关，在石板上知道了这个世界最角落的最阴暗的东西。那种事情，从未忘怀，从未动摇，我还记得，那一天，我，里修，第一次拔起了剑……
弗兰德的密室里，机关上方画着两棵树的字样，机关下方是一个有数字的刻度……
弗兰德最高的两棵树，只要知道两棵树的共同的相似度就行了……
给定两棵有根树，可以任意删除两棵树上的节点（删除一棵节点必须保证该节点的子树内的所有节点也必须要被删除，换一种说法，删除后的树必须联通并形成一棵树，且根节点不能被删除），使得删除后的两棵树同构，这两棵树有一个共同大小，即树的size，最大化同构的树的size即为机关的答案……
注：两棵同构的树要满足以下条件：
1、两棵树节点个数相等。
2、两棵树的以根节点的儿子为根子树对应同构。如下图，为两棵同构的有根树。
如下图，为两棵同构的有根树。
一行两个整数n,m分别表示两棵有根树的大小。
以下n-1行描述第一棵树，每行两个数x,y表示x号节点是y号节点父亲。
以下m-1行描述第二棵树，每行两个数x,y表示x号节点是y号节点父亲。
数据保证两棵树的1号节点均为根。
一行一个数，表示两棵树的相似度（删除后最大化的同构树的大小）。
3 3
1 2
1 3
1 2
2 3
2
【样例解释】
第一棵树可以保留1号节点和2号节点删除3号节点，也可以保留1号节点与3号节点删除2号节点，
第二棵树保留1号节点和2号节点删除3号节点。
剩下的树同构，树的节点个数均为2。
对于30%的数据，1 ≤ n ≤10
对于60%的数据，1 ≤ n ≤ 100
对于100%的数据，1 ≤ n ≤ 1000数据保证两棵树上每个节点的度均不超过5。
分析：
其实这题目啊，正解和暴力都是一样的，都是枚举两棵树的每个点的全排列，只是由于数据限制每个点的度不超过5，所以dp成了正解。这其实需要我们挖掘条件的能力，现在我们来挖掘一下。我们要以dp的思想去思考，一般而言dp所维护的与答案所求的有一定关系，不妨大胆设f[x][y]为A树以x为根节点的子树与B树以y为根节点的子树的最大同构数。很明显的，我们要和暴力一样去一一枚举配对(总感觉我在吐槽)，然后搜搜搜，说的也许有点抽象，所以来串代码冷静一下。
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #include<algorithm> 7 #include<vector> 8 using namespace std; 9 #define debug printf("zjyvegetable ") 10 #define int long long 11 inline int read(){ 12 int a=0,b=1;char c=getchar(); 13 while(!isdigit(c)){if(c=='-')b=-1;c=getchar();} 14 while(isdigit(c)){a=a*10+c-'0';c=getchar();} 15 return a*b; 16 } 17 const int N=2e3+50,M=2e5+50; 18 vector<int>vec1[N],vec2[N]; 19 int n,m,f[N][N],xx,yy,vis[M]; 20 void dfss(int k,int z){ 21 if(k>=vec1[xx].size()){ 22 f[xx][yy]=max(f[xx][yy],z); 23 return; 24 } 25 dfss(k+1,z); 26 bool flag=true; 27 for(int i=0;i<vec2[yy].size();i++){ 28 if(!vis[i]){ 29 vis[i]=1; 30 flag=false; 31 dfss(k+1,z+f[vec1[xx][k]][vec2[yy][i]]); 32 vis[i]=0; 33 } 34 } 35 if(flag)f[xx][yy]=max(f[xx][yy],z); 36 } 37 void dfs(int x){ 38 if(!vec1[x].size()){ 39 for(int i=1;i<=m;i++) 40 f[x][i]=1; 41 return; 42 } 43 for(int i=0;i<vec1[x].size();i++) 44 dfs(vec1[x][i]); 45 for(int i=1;i<=m;i++){ 46 if(!vec2[i].size())f[x][i]=1; 47 else{ 48 xx=x;yy=i; 49 dfss(0,0); 50 f[x][i]++; 51 } 52 } 53 } 54 signed main(){ 55 //freopen("frand.in","r",stdin); 56 //freopen("frand.out","w",stdout); 57 int u,v; 58 n=read();m=read(); 59 for(int i=1;i<n;i++){ 60 u=read();v=read(); 61 vec1[u].push_back(v); 62 } 63 for(int i=1;i<m;i++){ 64 u=read();v=read(); 65 vec2[u].push_back(v); 66 } 67 dfs(1); 68 printf("%lld ",f[1][1]); 69 return 0; 70 }
补充：
其实理解这段代码要用暴力的思想去想，你会发现其实没什么差。另外，这串代码的flag部分其实是可以省去的，这只是从意义上更好理解所以才加上的，但很容易发现flag部分所维护的最大值一定会比搜到边界的值小(或等于)。