NC20354. [SDOI2013]ASSASSIN
描述
故事发生在1486 年的意大利，Ezio 原本只是一个文艺复兴时期的贵族，后来因为家族成员受到圣殿骑士的杀害，决心成为一名刺客。最终，凭借着他的努力和出众的天赋，成为了杰出的刺客大师，他不仅是个身手敏捷的武林高手，飞檐走壁擅长各种暗杀术。刺客组织在他的带领下，为被剥削的平民声张正义，赶跑了原本统治意大利的圣殿骑士首领-教皇亚历山大六世。在他的一生中，经历了无数次惊心动魄、扣人心弦的探险和刺杀。
曾经有一次，为了寻找Altair 留下的线索和装备，Ezio 在佛罗伦萨中的刺客墓穴进行探索。这个刺客墓穴中有许多密室，且任何两个密室之间只存在一条唯一的路径。这些密室里都有一个刺客标记，他可以启动或者关闭该刺客标记。为了打开储存着线索和装备的储藏室，Ezio 必须操作刺客标记来揭开古老的封印。要想解开这个封印，他需要通过改变某些刺客标记的启动情况，使得所有刺客标记与封印密码“看起来一样”。
在这里，“看起来一样”的定义是：存在一种“标记”密室与“密码”密室之间一一对应的关系，使得密室间的连接情况和启动情况相同（提示中有更详细解释）。幸运的是，在Ezio 来到刺客墓穴之前，在Da Vinci 的帮助下，Ezio 已经得知了打开储藏室所需要的密码。
而你的任务则是帮助Ezio 找出达成目标所需要最少的改动标记次数。
输入描述
第一行给出一个整数n, 表示密室的个数,
第二行至第 n 行, 每行绐出两个整数 a 和 b, 表示第 a 个密室和第 b 个密室之间存在一条通道.
第 n+1行1 绐出 n 个整数1 分别表示当时每个密室的启动情况 {0表示关闭, 1表示启动).
第 n+2 行7 给出 n 个整数, 分别表示密码中每个密室的启动情况.
输出描述
输出只有一行，即输出最少改动标记次数
示例1
输入:
4 1 2 2 3 3 4 0 0 1 1 1 0 0 0
输出:
1
C++11(clang++ 3.9) 解法, 执行用时: 206ms, 内存消耗: 484K, 提交时间: 2020-05-22 15:58:19
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,mx,go,bx,by,rot,x,y,g[N][20],a[N],b[N],s[N],c[N],f[N];
void dfs(int x,int fa,int dep)
{
s[++s[0]]=x;
if (dep>mx)
{
mx=dep;
go=x;
memcpy(c,s,sizeof s);
}
for (int i=1;i<=g[x][0];i++)
if (g[x][i]!=fa) dfs(g[x][i],x,dep+1);
s[0]--;
}
void build(int x,int fa)
{
int t[20];
t[0]=0;
for (int i=1;i<=g[x][0];i++)
if (g[x][i]!=fa&&!(x==bx&&g[x][i]==by||x==by&&g[x][i]==bx))
t[++t[0]]=g[x][i];
memcpy(g[x],t,sizeof t);
for (int i=1;i<=g[x][0];i++) build(g[x][i],x);
}
int dp(int x,int y)
{
int w[20][20];
if (g[x][0]!=g[y][0]) return (~0U>>1);
for (int i=1;i<=g[x][0];i++)
for (int j=1;j<=g[y][0];j++)w[i][j]=dp(g[x][i],g[y][j]);
for (int i=0;i<1<<g[x][0];i++)f[i]=(~0U>>1);
f[(1<<g[x][0])-1]=0;
for (int i=(1<<g[x][0])-1;i;i--)
if (f[i]<(~0U>>1))
{
int cnt=g[x][0];
for (int j=0;j<g[x][0];j++)
if (i&(1<<j)) cnt--;
for (int j=0;j<g[x][0];j++)
if (i&(1<<j))f[i^(1<<j)]=min(f[i^(1<<j)],f[i]+w[cnt+1][j+1]);
}
return f[0]+(a[x]!=b[y]);
}
int main()
{
scanf("%d",&n);
for (int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
g[x][++g[x][0]]=y;
g[y][++g[y][0]]=x;
}
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++) scanf("%d",&b[i]);
dfs(1,0,0);
dfs(go,mx=0,0);
if (c[0]&1) rot=c[1+c[0]>>1];
else
{
rot=n+1;
bx=g[rot][++g[rot][0]]=c[c[0]>>1];
by=g[rot][++g[rot][0]]=c[(c[0]>>1)+1];
}
build(rot,0);
printf("%d",dp(rot,rot));
return 0;
}