自动搬运

查看原文

来自洛谷，原作者为

	xyz32768 “各方面相差太远”

搬运于2025-08-24 21:47:27，当前版本为作者最后更新于2018-04-06 10:23:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

关于树同构，有一个神奇的性质：

一棵树的重心只有 $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;
}