272. 【NOIP2015模拟10.28B组】序章-弗兰德的秘密 
(File IO): input:frand.in output:frand.out

Time Limits:  1000 ms  Memory Limits: 262144 KB  Detailed Limits  

Goto ProblemSet

Description

背景介绍
弗兰德，我不知道这个地方对我意味着什么。这里是一切开始的地方。3年前，还是个什么都没见过的少年，来到弗兰德的树下，走进了封闭的密室，扭动的封尘已久机关，在石板上知道了这个世界最角落的最阴暗的东西。那种事情，从未忘怀，从未动摇，我还记得，那一天，我，里修，第一次拔起了剑……

弗兰德的密室里，机关上方画着两棵树的字样，机关下方是一个有数字的刻度……
弗兰德最高的两棵树，只要知道两棵树的共同的相似度就行了……
给定两棵有根树，可以任意删除两棵树上的节点（删除一棵节点必须保证该节点的子树内的所有节点也必须要被删除，换一种说法，删除后的树必须联通并形成一棵树，且根节点不能被删除），使得删除后的两棵树同构，这两棵树有一个共同大小，即树的size，最大化同构的树的size即为机关的答案……

注：两棵同构的树要满足以下条件：
1、两棵树节点个数相等。
2、两棵树的以根节点的儿子为根子树对应同构。如下图，为两棵同构的有根树。
如下图，为两棵同构的有根树。

 

Input

一行两个整数n,m分别表示两棵有根树的大小。
以下n-1行描述第一棵树，每行两个数x,y表示x号节点是y号节点父亲。
以下m-1行描述第二棵树，每行两个数x,y表示x号节点是y号节点父亲。
数据保证两棵树的1号节点均为根。

Output

一行一个数，表示两棵树的相似度（删除后最大化的同构树的大小）。

 

Sample Input

3 3
1 2
1 3
1 2
2 3

Sample Output

2
【样例解释】
第一棵树可以保留1号节点和2号节点删除3号节点，也可以保留1号节点与3号节点删除2号节点，
第二棵树保留1号节点和2号节点删除3号节点。
剩下的树同构，树的节点个数均为2。

 

Data Constraint

对于30%的数据，1 ≤ n ≤10
对于60%的数据，1 ≤ n ≤ 100
对于100%的数据，1 ≤ n ≤ 1000数据保证两棵树上每个节点的度均不超过5。

 

 

 

做法：：树型 DP。设状态 F[x][y]表示，第一棵树中 x 节点与第二 棵树中的 y 节点作为根节点匹配的最大同构。例如，上图中所示的 F[x][y] = 3 。 现在转移方程就很显然了： F[x][y] = Max { F[x 的儿子][y 的儿子] } + 1 ; 这里需要枚举 x 的那些儿子与 y 的哪些儿子匹配，这部分时间复 杂度 O( 5! ) ; 最后答案就是 F[1][1]。

 

代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#define rep(i,a,b)    for(int i=a;i<=b;i++)
#define N 1007
using namespace std;
int f[N][N], n, m, sn[N][N], sm[N][N], ans, q, p;
bool bj[N];

int max(int a, int b) { if (a > b) return a; return b; }

void find(int t, int same)
{
    if (t == sn[q][0] + 1)
    {
        f[q][p] = max(f[q][p], same);
        return;
    }
    find(t + 1, same); 
    bool b = 0;
    rep(i, 1, sm[p][0]) 
    {
        if (bj[i])    continue;
        b = 1;
        bj[i] = 1;
        find(t + 1, same + f[sn[q][t]][sm[p][i]]);
        bj[i] = 0;
    }
    if (!b)
    {
        f[q][p] = max(f[q][p], same);
    }
}

void work(int x)
{
    if (sn[x][0] == 0)
    {
        rep(i, 1, m)
            f[x][i] = 1;
        return;        
    }
    rep(i, 1, sn[x][0])    work(sn[x][i]);
    rep(i, 1, m)
    {
        if (sm[i][0] == 0)
        {
            f[x][i] = 1;
            continue;
        }
        q = x;
        p = i;
        find(1, 0);        
        f[q][p]++;
        if (x == 1 && i == 1)    ans = max(f[q][p], ans);
    }
}

int main()
{
    freopen("frand.in", "r", stdin);
    freopen("frand.out", "w", stdout);
    scanf("%d%d", &n, &m);
    rep(i, 1, n - 1)
    {
        scanf("%d%d", &q, &p);
        sn[q][++sn[q][0]] = p;
    }
    rep(i, 1, m - 1)
    {
        scanf("%d%d", &q, &p);
        sm[q][++sm[q][0]] = p;
    }
    work(1);
    printf("%d", ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}