题解：
树上Hash
首先重心在边上就把边分裂
以重心为根建树，这样两个根一定对应
然后f[i][j]表示i匹配另一棵的j节点的最小代价
把他们的儿子摘出来做最小权匹配即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=1500;
typedef unsigned long long uLint;
const int oo=100000000;//int n;
int rx[maxn],ry[maxn];
int mi[maxn],ming[maxn];int cntedge=0;
int head[maxn]={0};
int to[maxn<<1],nex[maxn<<1];
void Addedge(int x,int y){
nex[++cntedge]=head[x];
to[cntedge]=y;
head[x]=cntedge;
}int root1=0,root2=0;
int siz[maxn]={0},g[maxn]={0};
void Dfs(int x,int fa){
siz[x]=1;g[x]=0;
for(int i=head[x];i;i=nex[i]){
if(to[i]==fa)continue;
Dfs(to[i],x);
siz[x]+=siz[to[i]];
g[x]=max(g[x],siz[to[i]]);
}
g[x]=max(g[x],n-siz[x]);if(g[x]<=g[root1]){
root2=root1;root1=x;
}else if(g[x]<=g[root2]){
root2=x;
}
}uLint hh[maxn];
int dep[maxn];
int father[maxn];
void Gethash(int x,int fa){
hh[x]=666;
father[x]=fa;
dep[x]=dep[fa]+1;
for(int i=head[x];i;i=nex[i]){
if(to[i]==fa)continue;
Gethash(to[i],x);
hh[x]+=hh[to[i]];
}
hh[x]=hh[x]*hh[x];
}int a[maxn];
bool cmp(const int &rhs1,const int &rhs2){
if(dep[rhs1]==dep[rhs2])return hh[rhs1]<hh[rhs2];
else return dep[rhs1]>dep[rhs2];
}struct NetworkFlow{
int totn,s,t;struct Edge{
int from,to,cap,flow,cost;
};
vector<int>G[maxn];
vector<Edge>edges;
void Addedge(int x,int y,int z,int w){
Edge e;
e.from=x;e.to=y;e.cap=z;e.flow=0;e.cost=w;
edges.push_back(e);
e.from=y;e.to=x;e.cap=0;e.flow=0;e.cost=-w;
edges.push_back(e);
int c=edges.size();
G[x].push_back(c-2);
G[y].push_back(c-1);
}int inq[maxn];
int d[maxn];
int p[maxn];
queue<int>q;
int Spfa(int &nowflow,int &nowcost){
for(int i=1;i<=totn;++i){
d[i]=oo;inq[i]=0;
}
d[s]=0;inq[s]=1;q.push(s);
while(!q.empty()){
int x=q.front();q.pop();inq[x]=0;
for(int i=0;i<G[x].size();++i){
Edge e=edges[G[x][i]];
if((e.cap>e.flow)&&(d[x]+e.cost<d[e.to])){
d[e.to]=d[x]+e.cost;
p[e.to]=G[x][i];
if(!inq[e.to]){
q.push(e.to);
inq[e.to]=1;
}
}
}
}if(d[t]==oo)return 0;int f=oo,x=t;
while(x!=s){
Edge e=edges[p[x]];
f=min(f,e.cap-e.flow);
x=e.from;
}
nowflow+=f;nowcost+=f*d[t];
x=t;
while(x!=s){
edges[p[x]].flow+=f;
edges[p[x]^1].flow-=f;
x=edges[p[x]].from;
}
return 1;
}int Mincost(){
int flow=0,cost=0;
while(Spfa(flow,cost)){
}
return cost;
}
void MCMFinit(){
totn=n+n+2;s=n+n+1;t=s+1;
edges.clear();
G[s].clear();G[t].clear();
}
}W;int f[maxn][maxn];
int main(){
scanf("%d",&n);
for(int i=1;i<=n-1;++i){
int x,y;
scanf("%d%d",&x,&y);
Addedge(x,y);
Addedge(y,x);
rx[i]=x;ry[i]=y;
}
for(int i=1;i<=n;++i)scanf("%d",&ming[i]);
for(int i=1;i<=n;++i)scanf("%d",&mi[i]);
mi[n+1]=ming[n+1]=0;g[0]=0x7fffffff;
Dfs(1,0);
if(g[root1]!=g[root2])root2=0;
if(root1&&root2){
cntedge=0;
memset(head,0,sizeof(head));
for(int i=0;i<n;++i){
if((rx[i]==root1&&ry[i]==root2)||(rx[i]==root2&&ry[i]==root1))continue;
Addedge(rx[i],ry[i]);
Addedge(ry[i],rx[i]);
}
Addedge(root1,n+1);
Addedge(n+1,root1);
Addedge(root2,n+1);
Addedge(n+1,root2);
root1=++n;
}
Gethash(root1,0);for(int i=1;i<=n;++i)a[i]=i;
sort(a+1,a+1+n,cmp);for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
int x=a[i];
int y=a[j];
if(hh[x]!=hh[y]){
f[x][y]=oo;
continue;
}
W.MCMFinit();
for(int ii=head[x];ii;ii=nex[ii]){
if(to[ii]==father[x])continue;
W.G[to[ii]].clear();
}
for(int ii=head[y];ii;ii=nex[ii]){
if(to[ii]==father[y])continue;
W.G[to[ii]+n].clear();
}
for(int ii=head[x];ii;ii=nex[ii]){
if(to[ii]==father[x])continue;
for(int jj=head[y];jj;jj=nex[jj]){
if(to[jj]==father[y])continue;
if(hh[to[ii]]!=hh[to[jj]])continue;
W.Addedge(to[ii],to[jj]+n,1,f[to[ii]][to[jj]]);
}
}
for(int ii=head[x];ii;ii=nex[ii]){
if(to[ii]==father[x])continue;
W.Addedge(W.s,to[ii],1,0);
}
for(int ii=head[y];ii;ii=nex[ii]){
if(to[ii]==father[y])continue;
W.Addedge(to[ii]+n,W.t,1,0);
}
f[x][y]=(ming[x]^mi[y])+W.Mincost();
}
}//for(int i=1;i<=n;++i){
//for(int j=1;j<=n;++j){
//cout<<f[i][j]<<' ';
//}
//cout<<endl;
//}
printf("%d\n",f[root1][root1]);
return 0;
}
