：
给你一棵树，有两组01权值a[]和b[]。n <= 700
你要构造一个自己到自己的映射，使得整棵树的形态不变，且映射后的a[]和映射之前的b[]中不同元素尽量少。
解：
发现这个整棵树形态不变......我们可能要用到树hash。
有个结论就是两棵树同构，当且仅当以它们重心为根的时候hash值相同。有两个重心就新建一个虚重心。
于是我们把重心搞出来当根，考虑映射之后的树，如果a映射到了b，那么a和b一定深度相同且hash值相同。
于是我们就按照深度分层，每层枚举点对，用f[a][b]来表示把点a映射到点b，子树内最少的不同元素。
于是如何求f[a][b]？发现我们要给a和b的若干个子节点进行匹配，要求权值最小。二分图匹配即可。我采用费用流实现。
复杂度：O(n³ + n * 网络流)，这个复杂度是我猜的...
1 #include2 3 const int N = 710, MO = 998244353, INF = 0x3f3f3f3f; 4 5 struct Edge { 6 int nex, v; 7 bool del; 8 }edge[N << 1]; int tp = 1; 9 10 int f[N][N], n, e[N], siz[N], val[N], h[N], aim[N], p[1000010], top, small, root, root2, in_e[N], lm, in[N], d[N]; 11 bool vis[1000010]; 12 std::vector v[N]; 13 14 inline void getp(int n) { 15 for(int i = 2; i <= n; i++) { 16 if(!vis[i]) { 17 p[++top] = i; 18 } 19 for(int j = 1; j <= top && i * p[j] <= n; j++) { 20 vis[i * p[j]] = 1; 21 if(i % p[j] == 0) { 22 break; 23 } 24 } 25 } 26 return; 27 } 28 29 inline void add(int x, int y) { 30 tp++; 31 edge[tp].v = y; 32 edge[tp].del = 0; 33 edge[tp].nex = e[x]; 34 e[x] = tp; 35 return; 36 } 37 38 void getroot(int x, int f) { 39 int large = 0; 40 siz[x] = 1; 41 for(int i = e[x]; i; i = edge[i].nex) { 42 int y = edge[i].v; 43 if(y == f) { 44 continue; 45 } 46 in_e[y] = i; 47 getroot(y, x); 48 siz[x] += siz[y]; 49 large = std::max(large, siz[y]); 50 } 51 large = std::max(large, n - siz[x]); 52 if(large < small) { 53 root = x; 54 root2 = 0; 55 small = large; 56 } 57 else if(large == small) { 58 root2 = x; 59 } 60 return; 61 } 62 63 void DFS_1(int x, int f) { 64 d[x] = d[f] + 1; 65 v[d[x]].push_back(x); 66 lm = std::max(lm, d[x]); 67 h[x] = 1; 68 for(int i = e[x]; i; i = edge[i].nex) { 69 int y = edge[i].v; 70 if(y == f || edge[i].del) { 71 continue; 72 } 73 DFS_1(y, x); 74 siz[x] += siz[y]; 75 h[x] = (h[x] + 1ll * h[y] * p[siz[y]] % MO) % MO; 76 } 77 return; 78 } 79 80 namespace fl { 81 82 struct Edge { 83 int nex, v, c, len; 84 Edge(int N = 0, int V = 0, int C = 0, int L = 0) { 85 nex = N; 86 v = V; 87 c = C; 88 len = L; 89 } 90 }edge[2000010]; int tp = 1; 91 92 int e[N], d[N], vis[N], Time, pre[N], flow[N], n, tot; 93 std::queue Q; 94 95 inline void add(int x, int y, int z, int w) { 96 //printf("addedge : x = %d y = %d z = %d w = %d \n", x, y, z, w); 97 edge[++tp] = Edge(e[x], y, z, w); 98 e[x] = tp; 99 edge[++tp] = Edge(e[y], x, 0, -w);100 e[y] = tp;101 return;102 }103 104 inline bool SPFA(int s, int t) {105 vis[s] = Time;106 memset(d + 1, 0x3f, tot * sizeof(int));107 flow[s] = INF;108 d[s] = 0;109 Q.push(s);110 while(Q.size()) {111 int x = Q.front();112 Q.pop();113 vis[x] = 0;114 for(int i = e[x]; i; i = edge[i].nex) {115 int y = edge[i].v;116 if(d[y] > d[x] + edge[i].len && edge[i].c) {117 d[y] = d[x] + edge[i].len;118 flow[y] = std::min(edge[i].c, flow[x]);119 pre[y] = i;120 if(vis[y] != Time) {121 vis[y] = Time;122 Q.push(y);123 }124 }125 }126 }127 return d[t] < INF;128 }129 130 inline void update(int s, int t) {131 132 int f = flow[t];133 while(s != t) {134 int i = pre[t];135 edge[i].c -= f;136 edge[i ^ 1].c += f;137 t = edge[i ^ 1].v;138 }139 return;140 }141 142 inline int solve(int x, int y) {143 144 int ans = 0, cost = 0;145 n = in[x] - (x != root);146 int s = 2 * n + 1, t = tot = s + 1;147 //printf("solve : x = %d y = %d n = %d \n", x, y, n);148 memset(e + 1, 0, tot * sizeof(int));149 tp = 1;150 151 for(int i = ::e[x], cnt1 = 1; i; i = ::edge[i].nex, ++cnt1) {152 int u = ::edge[i].v;153 //printf("u = %d \n", u);154 if(::d[u] < ::d[x] || ::edge[i].del) {155 --cnt1;156 continue;157 }158 add(s, cnt1, 1, 0);159 add(cnt1 + n, t, 1, 0);160 for(int j = ::e[y], cnt2 = 1; j; j = ::edge[j].nex, ++cnt2) {161 int v = ::edge[j].v;162 //printf(" v = %d \n", v);163 if(::d[v] < ::d[y] || ::edge[j].del) {164 --cnt2;165 continue;166 }167 /// u v168 if(f[u][v] > -INF) {169 add(cnt1, n + cnt2, 1, f[u][v]);170 }171 172 }173 }174 175 ++Time;176 while(SPFA(s, t)) {177 //printf("inside --------------------- \n");178 ans += flow[t];179 cost += flow[t] * d[t];180 update(s, t);181 ++Time;182 }183 184 //printf("ans = %d cost = %d \n", ans, cost);185 if(ans != n) {186 return -INF;187 }188 else {189 return cost + (val[x] != aim[y]);190 }191 }192 }193 194 int main() {195 196 scanf("%d", &n);197 for(int i = 1, x, y; i < n; i++) {198 scanf("%d%d", &x, &y);199 add(x, y);200 add(y, x);201 in[x]++;202 in[y]++;203 }204 for(int i = 1; i <= n; i++) {205 scanf("%d", &val[i]);206 }207 for(int i = 1; i <= n; i++) {208 scanf("%d", &aim[i]);209 }210 root = root2 = 0;211 small = N;212 getroot(1, 0);213 //printf("root 1 = %d root 2 = %d \n", root, root2);214 215 if(root2) {216 ++n;217 int i;218 if(edge[in_e[root] ^ 1].v == root2) {219 i = in_e[root];220 }221 else {222 i = in_e[root2];223 }224 edge[i].del = edge[i ^ 1].del = 1;225 add(n, root);226 add(n, root2);227 root = n;228 in[n] = 2;229 }230 ///231 232 //printf("root = %d \n", root);233 234 DFS_1(root, 0);235 236 for(int d = lm; d >= 1; d--) {237 int len = v[d].size();238 for(int i = 0; i < len; i++) {239 int x = v[d][i];240 for(int j = 0; j < len; j++) {241 int y = v[d][j];242 if(in[x] != in[y] || h[x] != h[y]) {243 f[x][y] = -INF;244 //printf("1 : ");245 }246 else {247 //f[x][y] = KM::solve(x, y);248 f[x][y] = fl::solve(x, y);249 //printf("2 : ");250 }251 //printf("f %d %d = %d \n", x, y, f[x][y]);252 }253 }254 }255 256 printf("%d\n", f[root][root]);257 return 0;258 }