╰(￣▽￣)╭
Description
故事发生在1486 年的意大利，Ezio 原本只是一个文艺复兴时期的贵族，后来因为家族成员受到圣殿骑士的杀害，决心成为一名刺客。最终，凭借着他的努力和出众的天赋，成为了杰出的刺客大师，他不仅是个身手敏捷的武林高手，飞檐走壁擅长各种暗杀术。刺客组织在他的带领下，为被剥削的平民声张正义，赶跑了原本统治意大利的圣殿骑士首领-教皇亚历山大六世。在他的一生中，经历了无数次惊心动魄、扣人心弦的探险和刺杀。
曾经有一次，为了寻找Altair 留下的线索和装备，Ezio 在佛罗伦萨中的刺客墓穴进行探索。这个刺客墓穴中有许多密室，且任何两个密室之间只存在一条唯一的路径。这些密室里都有一个刺客标记，他可以启动或者关闭该刺客标记。为了打开储存着线索和装备的储藏室，Ezio 必须操作刺客标记来揭开古老的封印。要想解开这个封印，他需要通过改变某些刺客标记的启动情况，使得所有刺客标记与封印密码“看起来一样”。
在这里，“看起来一样”的定义是：存在一种“标记”密室与“密码”密室之间一一对应的关系，使得密室间的连接情况和启动情况相同（提示中有更详细解释）。幸运的是，在Ezio 来到刺客墓穴之前，在Da Vinci 的帮助下，Ezio 已经得知了打开储藏室所需要的密码。
而你的任务则是帮助Ezio 找出达成目标所需要最少的改动标记次数。
对于100%的数据，n<=700，且每个密室至多与11个密室相通。
第一行给出一个整数n，表示密室的个数。 第二行至第n 行，每行给出两个整数a 和b，表示第a 个密室和第b 个密室之间存在一条通道。 第n+1 行，给出n 个整数，分别表示当时每个密室的启动情况（0 表示关闭，1 表示启动）。 第n+2 行，给出n 个整数，分别表示密码中每个密室的启动情况。
Output
输出只有一行，即输出最少改动标记次数。
4 1 2 2 3 3 4 0 0 1 1 1 0 0 0
Sample Output
1
样例解释
密室的编号是可以变的！将第三个密室关闭后，在当前标记和密码之间，存在1->4,2->3,3->2,4->1 的对应关系，重新编号后连接情况没有改变，且标记与密码对应。对于更一般的情况，存在一个1 到n 的置换P，使得对于任意密室之间的道路u-v，都一定有密码密室中的道路P(u)-P(v)；如果不存在密室之间的道路u-v，则一定没有密码密室中的道路P(u)-P(v)。
(⊙ ▽ ⊙)
简化题意
给出一棵树，找出另一棵同构的树，使得结点权值差异最小。
做法
先把无根树转化为有根树，关键就在于我们如何选择根： 首先我们选重心做为树的根，如果重心在边上，就新建一个结点。 选了重心作为根的好处是： 同构的子树之间可以互相调换。
如何判断两棵子树同构呢？先给每个结点及其儿子构成的子树预处理出hash值。深度相同并且hash值也相同的两个结点所构成的子树就是同构的两棵子树。hash值可以利用double hash现在先对所有结点按其深度从大到小排序，hash值为第二关键字排序。 设f[i][j]表示结点i与结点j调换的最小费用， 前面说过，只有同构并且深度相同的子树才能调换。 通过这个条件，并且利用排序后的序列，可以简单地进行转移。
那么转移方程怎么写呢？即f[i][j]=? 由于f[son(i)][]已经求出来了，因为son(i)的深度比i大， 那么通过i和j的儿子相互调换，从而达到最小值，使我们的目的。 实际上，这个过程是带费用的二分图匹配， 可以利用最小费用最大流或者KM算法完成这个过程，设答案为flow。 那么f[i][j]=flow+(a[i] xor b[j])，其中a,b是输入中的两组权值。
由于每个密室至多与11 个密室相通， 所以时间复杂度不会太大。
(￣～￣)
#include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<string.h>#define ll long long#define p1(x) (x+1)#define p2(x) (x+tmd+1)using namespace std;const char* fin="ex3296.in";const char* fout="ex3296.out";const int inf=0x7fffffff;const int maxn=707,maxm=maxn*20,maxN=370,maxM=maxN*2,maxh=99997,maxH=57494,hh=137,HH=97;int n,m,i,j,k,rt;int fi[maxn],ne[maxm],la[maxm],tot,A[maxn],B[maxn];int si[maxn],fa[maxn],ce[3],f[maxn][maxn];int w[maxn],W[maxn];struct node{ int de,h,H,id;}a[maxn];bool cmp(node a,node b){ return a.de>b.de || (a.de==b.de && a.h<b.h) || (a.de==b.de && a.h==b.h && a.H<b.H);}struct network{ int fi[maxN],ne[maxM],la[maxM],va[maxM],co[maxM],tot,num,last[maxN],Last[maxN]; int b[maxN*10],f[maxN],head,tail; bool bz[maxN]; void init(int v){ tot=1; memset(fi,0,sizeof(fi)); num=v; } void add_line(int a,int b,int c,int d){ tot++; ne[tot]=fi[a]; la[tot]=b; va[tot]=c; co[tot]=d; fi[a]=tot; } void add(int a,int b,int c,int d){ add_line(a,b,c,d); add_line(b,a,0,-d); } void add(int v,int dis){ f[v]=dis; if (!bz[v]){ b[++tail]=v; bz[v]=true; } } int spfa(){ int i,j,k,cost=0; head=tail=0; memset(bz,0,sizeof(bz)); memset(f,127,sizeof(f)); add(1,0); while (head++<tail){ for (k=fi[b[head]];k;k=ne[k]) if (va[k] && f[b[head]]+co[k]<f[la[k]]){ Last[la[k]]=k; last[la[k]]=b[head]; add(la[k],f[b[head]]+co[k]); } bz[b[head]]=false; } if (f[num]>2000000000) return -1; for (k=num;k!=1;k=last[k]){ va[Last[k]]--; va[Last[k]^1]++; cost+=co[Last[k]]; } return cost; } int flow(){ int j,k=0; while (1){ j=spfa(); if (j==-1) break; else k+=j; } return k; }}N;void add_line(int a,int b){ tot++; ne[tot]=fi[a]; la[tot]=b; fi[a]=tot;}void dfs(int v,int from){ int i=1,j,k; fa[v]=from; si[v]=1; for (k=fi[v];k;k=ne[k]) if (la[k]!=from){ dfs(la[k],v); si[v]+=si[la[k]]; i&=si[la[k]]<=n/2; } if (i && (n-si[v])<=n/2) ce[++ce[0]]=v;}int t[maxn],T[maxn];void geth(int v,int from){ int i,j,k; fa[v]=from; si[v]=0; a[v].id=v; a[v].de=a[from].de+1; for (k=fi[v];k;k=ne[k]) if (la[k]!=from){ geth(la[k],v); si[v]++; } t[0]=T[0]=0; for (k=fi[v];k;k=ne[k]) if (la[k]!=from) t[++t[0]]=a[la[k]].h,T[++T[0]]=a[la[k]].H; if (!t[0]){ a[v].h=23; a[v].H=89; return ; } sort(t+1,t+t[0]+1),sort(T+1,T+T[0]+1); for (i=1;i<=t[0];i++){ a[v].h=(a[v].h*hh+t[i]*(hh^11))%maxh; a[v].H=(a[v].H*HH+T[i]*(HH^29))%maxH; }}int main(){ scanf("%d",&n); for (i=1;i<n;i++){ scanf("%d%d",&A[i],&B[i]); add_line(A[i],B[i]); add_line(B[i],A[i]); } for (i=1;i<=n;i++) scanf("%d",&w[i]); for (i=1;i<=n;i++) scanf("%d",&W[i]); dfs(1,0); if (ce[0]>1){ memset(fi,0,sizeof(fi)); tot=0; for (i=1;i<n;i++){ if (!(A[i]==ce[1] && B[i]==ce[2] || A[i]==ce[2] && B[i]==ce[1])){ add_line(A[i],B[i]); add_line(B[i],A[i]); } } n++; add_line(n,ce[1]); add_line(ce[1],n); add_line(n,ce[2]); add_line(ce[2],n); rt=n; }else rt=ce[1]; geth(rt,0); sort(a+1,a+n+1,cmp); j=1; memset(f,255,sizeof(f)); for (i=2;i<=n+1;i++) if (i==n+1 || a[i].de!=a[i-1].de || a[i].h!=a[i-1].h || a[i].H!=a[i-1].H){ int tmp=j; for (;j<i;j++) for (k=tmp;k<i;k++){ N.init(si[a[j].id]+si[a[k].id]+2); int l,o,L,O,tmd=si[a[j].id]; for (l=fi[a[j].id],L=1;l;l=ne[l]) if (la[l]!=fa[a[j].id]){ for (o=fi[a[k].id],O=1;o;o=ne[o]) if (la[o]!=fa[a[k].id]){ if (f[la[l]][la[o]]!=-1) N.add(p1(L),p2(O),1,f[la[l]][la[o]]); O++; } L++; } for (l=fi[a[j].id],L=1;l;l=ne[l]) if (la[l]!=fa[a[j].id]) { N.add(1,p1(L),1,0); L++; } for (o=fi[a[k].id],O=1;o;o=ne[o]) if (la[o]!=fa[a[k].id]){ N.add(p2(O),N.num,1,0); O++; } f[a[j].id][a[k].id]= N.flow()+ (w[a[j].id]^W[a[k].id]); PRintf(""); } j=i; } printf("%d",f[rt][rt]); return 0;}(⊙v⊙)
Key Points 1.hash的计算 新加的常数项要乘个系数。
