bzoj 3197 DP

　　这道题我们可以看成给定两个黑白树，可以修改其中一棵树的颜色，问最少修改多少颜色可以使两棵树同构。

　　首先我们知道在树的同构中树上最长链中点（如果是偶数的话就是中间两个点）是不变的，我们把这个点叫做树的重心（如果有两个重心bz,by的话我们可以加一个点连接bx,by，将加的这个点看成重心），那么我们可以以树的重心为根来DP。

　　我们可以处理使x,y为根的子树同构的最小代价，判断树同构的合法性我们可以递归的判断每一个儿子的size来判断，设x,y的子节点sonx,sony，那么假设我们求出了所有sonx,sony的值，我们可以得到状态表示，f[s]代表y子树中我们已经匹配了s集合的子节点，x子树中我们已经匹配了前|s|个节点，现在要用x子树的第|s|+1节点匹配y子树中的其他未匹配节点，然后用sonx和sony的值来更新答案。

　　

/**************************************************************

    Problem: 3197

    User: BLADEVIL

    Language: C++

    Result: Accepted

    Time:576 ms

    Memory:884 kb

****************************************************************/


//By BLADEVIL

#include <cstdio>

#include <cstring>

#include <algorithm>

#define maxn 800

#define inf (~0U>>1)

using namespace std;

int n,mx,go,bx,by,rot;

int g[maxn][],a[maxn],b[maxn],s[maxn],c[maxn],f[maxn];

void dfs(int x,int fa,int dep) {

    s[++s[]]=x;

    if (dep>mx) {

        mx=dep; go=x;

        memcpy(c,s,sizeof s);

    }

    for (int i=;i<=g[x][];i++)

        if (g[x][i]!=fa) dfs(g[x][i],x,dep+);

    s[]--;

}

void build(int x,int fa) {

    int t[]; t[]=;

    for (int i=;i<=g[x][];i++)

        if (g[x][i]!=fa&&!(x==bx&&g[x][i]==by||x==by&&g[x][i]==bx))

            t[++t[]]=g[x][i];

    memcpy(g[x],t,sizeof t);

    for (int i=;i<=g[x][];i++) build(g[x][i],x);

}

int dp(int x,int y) {

    if (g[x][]!=g[y][]) return inf;

    int w[][];

    for (int i=;i<=g[x][];i++)

        for (int j=;j<=g[y][];j++)

            w[i][j]=dp(g[x][i],g[y][j]);

    for (int i=;i<<<g[x][];i++) f[i]=inf;

    f[(<<g[x][])-]=;

    for (int i=(<<g[x][])-;i;i--) {

        if (f[i]<inf) {

            int cnt=g[x][];

            for (int j=;j<g[x][];j++)

                if (i&(<<j)) cnt--;

            for (int j=;j<g[x][];j++)

                if (i&(<<j))

                    f[i^(<<j)]=min(f[i^(<<j)],f[i]+w[cnt+][j+]);

        }

    }

    return f[]+(a[x]!=b[y]);

}

int main() {

    scanf("%d",&n);

    for (int i=;i<n;i++) {

        int x,y; scanf("%d%d",&x,&y);

        g[x][++g[x][]]=y;

        g[y][++g[y][]]=x;

    }

    for (int i=;i<=n;i++) scanf("%d",&a[i]);

    for (int i=;i<=n;i++) scanf("%d",&b[i]);

    dfs(,,);

    dfs(go,mx=,);

    if (c[]&) rot=c[+c[]>>]; else {

        rot=n+;

        bx=g[rot][++g[rot][]]=c[c[]>>];

        by=g[rot][++g[rot][]]=c[(c[]>>)+];

    }

    build(rot,);

    //for (int i=1;i<=n;i++) printf("%d\n",g[i][0]);

    printf("%d\n",dp(rot,rot));

    return ;

}