题目大意

给定一棵树和两组 01 权值，求对这棵树重标号后，第一组权值和第二组权值最小不同数。

$n\leq700$ 。

题解

真是一场酣畅淋漓的写题啊！

处理无根树的方式与 P4895 独钓寒江雪 一样，重心作根，两个重心就新开个点向两中心连边；哈希也与之相同。

有根后设 $f_{x,y}$ 表示在子树 $x,y$ 同构的条件下，二者权值最小不同数。考虑转移， $x,y$ 同构而它们的所有子树的形态一样的，所谓重编号，就相当于 $x$ 中同构的子树与 $y$ 中同构的子树可以对应（连边）而我们需要一个最优的匹配，这样就把问题转化为二分图带权匹配，用费用流即可。

代码

真是一场酣畅淋漓的敲代码啊！

const int N = 710, mod = 1e9 + 7;
const int BASE = 19260817;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	int a[N], b[N];
	struct Edge {
		int to, nxt;
	} e[N << 1];
	int head[N], tot;
	void add_edge (int u, int v) { e[++tot] = (Edge) {v, head[u]}, head[u] = tot; }

	int rt;
	int siz[N], mx[N];
	void get_root(int u, int fa) {
		siz[u] = 1;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (v == fa) continue;
			get_root(v, u);
			siz[u] += siz[v];
			mx[u] = max(mx[u], siz[v]);
		}
		mx[u] = max(mx[u], n - siz[u]);
		if (!rt || mx[u] < mx[rt]) rt = u;
	}
	unsigned ll hash[N];
	int r1 = 0, r2 = 0;
	int tmp[N], fa[N], dep[N];
#define nop(u, v) (u == r1 && v == r2 || u == r2 && v == r1)
	void calc_hash(int u) {
		hash[u] = 1;
		dep[u] = dep[fa[u]] + 1;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to; if (v == fa[u] || nop(u, v)) continue;
			fa[v] = u;
			calc_hash(v);
		}
		int tot = 0;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to; if (v == fa[u] || nop(u, v)) continue;
			tmp[++tot] = hash[e[i].to];
		}
		sort(tmp + 1, tmp + tot + 1);
		for (int i = 1; i <= tot; i++) (((hash[u] *= BASE) += tmp[i]) ^= tmp[i]) += tmp[i];
	}

	bool DEBUG = 0;

	struct NetworkFlow {
		const int inf = 707406378;
		const static int N = 25;
		int S, T, n;
		int head[N], tot = 1;
		struct Edge {
			int to; ll w, c; int nxt;
		} e[N * N];
		void add_edge(int u, int v, ll w, ll c) {
			e[++tot] = (Edge) {v, w, c, head[u]}, head[u] = tot;
			e[++tot] = (Edge) {u, 0, -c, head[v]}, head[v] = tot;
		}
		NetworkFlow() {tot = 1;}

		bool vis[N];
		int dis[N];
		deque <int> q;
		bool spfa() {
			while (!q.empty()) q.pop_back();
			for (int i = 1; i <= n; i++) vis[i] = 0, dis[i] = inf;
			dis[T] = 0, vis[T] = 1;
			q.push_back(T);
			while (!q.empty()) {
				int u = q.front(); q.pop_front(); vis[u] = 0;
				for (int i = head[u]; i; i = e[i].nxt) {
					int v = e[i].to;
					if (dis[v] > dis[u] - e[i].c && e[i ^ 1].w) {
						dis[v] = dis[u] - e[i].c;
						if (!vis[v]) {
							vis[v] = 1;
							if (q.size() && dis[v] < dis[q.front()]) q.push_front(v);
							else q.push_back(v);
						}
					}
				}
			}
			return dis[S] < inf;
		}
		ll mcost = 0;
		ll dfs (int u, ll flow) {
			vis[u] = 1;
			if (u == T || !flow) return flow;
			ll sum = 0;
			for (int i = head[u]; i; i = e[i].nxt) {
				int v = e[i].to;
				if (dis[v] == dis[u] - e[i].c && e[i].w && !vis[v]) {
					ll f = dfs(v, min(e[i].w, flow - sum));
					if (!f) continue;
					e[i].w -= f;
					e[i ^ 1].w += f;
					sum += f;
					mcost += f * e[i].c;
					if (sum == flow) break;
				}
			}
			return sum;
		}
		ll mcmf () {
			ll ret = 0;
			// if (DEBUG) printf ("%d\n", tot);
			while (spfa()) {
				vis[T] = 1;
				for (; vis[T]; ret += dfs(S, inf))
					for (int i = 1; i <= n; i++) vis[i] = 0;
			}
			return ret;
		}

		void clear(int num) {
			S = num + 1, T = S + 1; tot = 1;
			n = num + 2; mcost = 0;
			for (int i = 1; i <= n; i++) head[i] = 0;
		}
	} nf;

	int f[N][N];
	pair <unsigned ll, int> p1[N], p2[N];
	void solve (int x, int y) {
		int tot1 = 0, tot2 = 0;
		for (int i = head[x]; i; i = e[i].nxt)
			if (e[i].to != fa[x] && !nop(x, e[i].to)) p1[++tot1] = make_pair(hash[e[i].to], e[i].to);
		for (int i = head[y]; i; i = e[i].nxt)
			if (e[i].to != fa[y] && !nop(y, e[i].to)) p2[++tot2] = make_pair(hash[e[i].to], e[i].to);
		sort (p1 + 1, p1 + 1 + tot1); sort (p2 + 1, p2 + 1 + tot2);
		DEBUG =  (x == 5 && y == 5);
		for (int i = 1; i <= tot1; i++) {
			int j;
			for (j = i; j < tot1 && p1[j].first == p1[j + 1].first; j++);
			int len = j - i + 1;
			nf.clear (len * 2);
			for (int k1 = i; k1 <= j; k1++)
				for (int k2 = i; k2 <= j; k2++)
					nf.add_edge(k1 - i + 1, k2 - i + 1 + len, 1, f[p1[k1].second][p2[k2].second]);
			for (int k = 1; k <= len; k++) nf.add_edge(nf.S, k, 1, 0), nf.add_edge(k + len, nf.T, 1, 0);
			nf.mcmf(); f[x][y] += nf.mcost;
			//if (x == 5 && y == 5) printf ("%d %d\n", i, j);
			i = j;
		}
		if (a[x] != b[y]) f[x][y]++;
	}
	pair<int, pair <unsigned ll, int> > w[N];
	int main () {
		n = Read();
		for (int i = 1; i < n; i++) {
			int u = Read(), v = Read();
			add_edge(u, v), add_edge(v, u);
		}
		for (int i = 1; i <= n; i++) a[i] = Read();
		for (int i = 1; i <= n; i++) b[i] = Read();
		get_root(1, 0);
		for (int i = 1; i <= n; i++)
			if (mx[i] == mx[rt]) r2 = r1, r1 = i;
		if (r2) n++, add_edge(n, r1), add_edge(n, r2), rt = n;
		calc_hash(rt);
		for (int i = 1; i <= n; i++) w[i] = make_pair(-dep[i], make_pair(hash[i], i));
		sort (w + 1, w + 1 + n);
		for (int i = 1; i <= n; i++) {
			int j;
			for (j = i; j < n && w[j].first == w[j + 1].first && w[j].second.first == w[j + 1].second.first; j++);
			for (int k1 = i; k1 <= j; k1++)
				for (int k2 = i; k2 <= j; k2++)
					solve (w[k1].second.second, w[k2].second.second);
			i = j;
		}
		printf ("%d\n", f[rt][rt]);
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}