[BZOJ3197][Sdoi2013]assassin（树形DP+树同构+二分图最优匹配）

关于树同构，有一个神奇的性质：
一棵树的重心只有 $1$ 个或 $2$ 个，如果有 $2$ 个（记为 $u$ 和 $v$），那么一定有边 $(u,v)$ ，而此时可以断开边 $(u,v)$ ，新建一个节点，分别向 $u$ 和 $v$ 建边，这样新建的节点就是重心。上面所说的性质是：如果有两棵树，强制以重心为根，那么这两棵树同构当且仅当形成的两棵有根树同构。
而两棵有根树（分别以 $u$ 和 $v$）同构，当且仅当 $u$ 和 $v$ 的度数相同，
并且设 $u$ 的子节点集合为 $son_u=\{x_1,x_2,...,x_m\}$ ，
$v$ 的子节点集合为 $son_v=\{y_1,y_2,...,y_m\}$ ，
存在一个 $1$ 到 $m$ 的排列 $P$ 使得对于每个 $i$ ，满足以 $x_i$ 为根的子树与以 $y_{P_i}$ 为根的子树同构。
回到原问题。根据性质，可以先找出树的重心，然后强制以重心为根，做一次树形 DP：
$f[x][y]$ ：使 $x$ 的子树和 $y$ 的子树启动情况同构的最小代价。其中 $x$ 和 $y$ 必须深度相同且子树同构。
转移当然是从 $x$ 和 $y$ 的子树转移。也就是找到一个合法的，最优的子树匹配，使得满足条件：
（1）如果 $x$ 的一个子树 $u$ 和 $y$ 的一个子树 $v$ 进行匹配，那么 $u$ 的子树和 $v$ 的子树必须同构。
（2）$u$ 和 $v$ 匹配的代价为 $f[u][v]$ ，必须最小化 $\sum f[u][v]$ 。
显然，关键在于条件（2）。而条件（2）是一个最小权和完备匹配问题，用 KM / 费用流可以求得。
现在还剩下最后一个问题，那就是，如何判断深度相同的两个子树 $u$ 和 $v$ 是否同构。
Hash 大法好！
也就是为每个子树定义一个 Hash 函数，如果 $u$ 和 $v$ 的 Hash 值相等，那么 $u$ 的子树和 $v$ 的子树同构。
具体地，构造这个 Hash 函数的方法是：
将子树内的所有节点按照 Hash 值从大到小排序，那么 Hash 函数为：

$$H(u)=((A\times H(son[u]_1))\times p+H(son[u]_2))\times p+...$$


调了 37 遍，最后才发现 KM 写挂了

代码：

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
#define Edge(u) for (int e = adj[u], v; e; e = nxt[e])
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
typedef long long ll;
const int N = 805, M = N << 1, INF = 0x3f3f3f3f;
int n, ecnt, nxt[M], adj[N], go[M], st[N], ed[N], dis[N], pyz[N], lpf[N],
Root = -1, Root0 = -1, tot, cnt, mo[N], ox[N], f[N][N], fa[N], dep[N];
vector<int> edg[N];
ll has[N], orz[N];
struct cyx {
    int n, val[N][N], tox[N], ex[N], ey[N], orz[N];
    bool visx[N], visy[N];
    bool dfs(int u) {
        int v; visx[u] = 1; For (v, 1, n) {
            if (visy[v] || val[u][v] == -1) continue;
            int t = val[u][v] - ex[u] - ey[v]; if (t == 0) {
                visy[v] = 1; if (!tox[v] || dfs(tox[v]))
                    return tox[v] = u, 1;
            }
            else orz[v] = min(orz[v], t);
        }
        return 0;
    }
    int solve() {
        if (n == 0) return 0;
        int i, j; For (i, 1, n) tox[i] = 0;
        For (i, 1, n) {
            ey[i] = 0; ex[i] = INF; For (j, 1, n)
                if (val[i][j] != -1) ex[i] = min(ex[i], val[i][j]);
        }
        For (i, 1, n) {
            For (j, 1, n) orz[j] = INF; int cnt = 0; while (1) {
                For (j, 1, n) visx[j] = visy[j] = 0;
                if (dfs(i)) break; int mind = INF; For (j, 1, n)
                    if (!visy[j]) mind = min(mind, orz[j]);
                For (j, 1, n) {
                    if (visx[j]) ex[j] += mind;
                    if (visy[j]) ey[j] -= mind;
                    else orz[j] -= mind;
                }
            }
        }
        int ans = 0; For (i, 1, n) ans += ex[i] + ey[i]; return ans;
    }
} km;
void add_edge(int u, int v) {
    nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
    nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;
}
int dfs(int u, int fu) {
    fa[u] = fu; dis[u] = 0; pyz[u] = u; Edge(u) {
        if ((v = go[e]) == fu) continue; dfs(v, u);
        if (2 + dis[v] > dis[u]) dis[u] = 2 + dis[v], pyz[u] = pyz[v];
    }
    return pyz[u];
}
void calcHash(int u, int fu) {
    dep[u] = dep[fu] + 1;
    has[u] = 14221; Edge(u) if ((v = go[e]) != fu) calcHash(v, u);
    int i; tot = 0; Edge(u) if ((v = go[e]) != fu) orz[++tot] = has[v];
    sort(orz + 1, orz + tot + 1); For (i, 1, tot)
        has[u] = (has[u] * 4481 % 1060469 ^ orz[i]) % 1060469;
    has[u] = has[u] * 20707 % 1060469;
}
bool comp(int u, int v) {
  
  return has[u] < has[v];}
bool comp2(int u, int v) {
    if (dep[u] != dep[v]) return dep[u] > dep[v]; return has[u] < has[v];
}
int DP() {
    int i, j, k; For(i, 1, n) lpf[i] = i; sort(lpf + 1, lpf + n + 1, comp2);
    for (k = 1; k <= n;) {
        int nx = k; while (nx <= n && dep[lpf[k]] == dep[lpf[nx]]
            && has[lpf[k]] == has[lpf[nx]]) nx++;
        For (i, k, nx - 1) For (j, k, nx - 1) {
            int u = lpf[i], v = lpf[j], sb = 0; km.n = 0;
            for (int e = adj[u]; e; e = nxt[e])
                if (dep[go[e]] == dep[u] + 1) km.n++;
            for (int e = adj[u]; e; e = nxt[e]) if (dep[go[e]] == dep[u] + 1) {
                sb++; int sp = 0; for (int r = adj[v]; r; r = nxt[r])
                    if (dep[go[r]] == dep[v] + 1) {
                        km.val[sb][++sp] = has[go[e]] == has[go[r]]
                            ? f[go[e]][go[r]] : -1;
                    }
            }
            f[u][v] = km.solve() + (st[u] != ed[v]);
        }
        k = nx;
    }
    return f[Root][Root];
}
int main() {
    int i, j, x, y, d; n = read(); For (i, 1, n - 1)
        x = read(), y = read(), edg[x].push_back(y),
        edg[y].push_back(x), add_edge(x, y);
    For (i, 1, n) st[i] = read(); For (i, 1, n) ed[i] = read();
    x = dfs(1, 0); y = dfs(x, 0); Root = y; d = dis[x] >> 1;
    For (i, 1, d >> 1) Root = fa[Root]; if (d & 1) Root0 = fa[Root];
    if (Root0 != -1) {
        ecnt = 0; memset(adj, 0, sizeof(adj));
        For (i, 1, n) {
            int tmp = edg[i].size(); For (j, 0, tmp - 1)
                if (i < edg[i][j] && !(i == Root && edg[i][j] == Root0) &&
                    !(i == Root0 && edg[i][j] == Root)) add_edge(i, edg[i][j]);
        }
        add_edge(++n, Root); add_edge(n, Root0); Root = n;
    }
    calcHash(Root, 0); printf("%d\n", DP());
    return 0;
}