#PQJ211x4130. QOJ 211_4130

    ID: 2776 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SDOI 2013最小生成树

QOJ 211_4130

故事发生在1486 年的意大利,Ezio 原本只是一个文艺复兴时期的贵族,后来因为家族成员受到圣殿骑士的杀害,决心成为一名刺客。最终,凭借着他的努力和出众的天赋,成为了杰出的刺客大师,他不仅是个身手敏捷的武林高手,飞檐走壁擅长各种暗杀术。刺客组织在他的带领下,为被剥削的平民声张正义,赶跑了原本统治意大利的圣殿骑士首领-教皇亚历山大六世。在他的一生中,经历了无数次惊心动魄、扣人心弦的探险和刺杀。

曾经有一次,为了寻找 Altair 留下的线索和装备,Ezio 在佛罗伦萨中的刺客墓穴进行探索。这个刺客墓穴中有许多密室,且任何两个密室之间只存在一条唯一的路径。这些密室里都有一个刺客标记,他可以启动或者关闭该刺客标记。为了打开储存着线索和装备的储藏室,Ezio 必须操作刺客标记来揭开古老的封印。要想解开这个封印,他需要通过改变某些刺客标记的启动情况,使得所有刺客标记与封印密码“看起来一样”。

在这里,“看起来一样”的定义是:存在一种“标记”密室与“密码”密室之间一一对应的关系,使得密室间的连接情况和启动情况相同(提示中有更详细解释)。幸运的是,在 Ezio 来到刺客墓穴之前,在 Da Vinci 的帮助下,Ezio 已经得知了打开储藏室所需要的密码。

而你的任务则是帮助Ezio 找出达成目标所需要最少的改动标记次数。

输入格式

第一行给出一个整数 𝑛 , 表示密室的个数,

第二行至第 𝑛 行, 每行给出两个整数 𝑎 和 𝑏 , 表示第 𝑎 个密室和第 𝑏 个密室之间存在一条通道。

第 𝑛 + 1 行,给出 𝑛 个整数,分别表示当时每个密室的启动情况 (0 表示关闭,1 表示启动)。

第 𝑛 + 2 行,给出 𝑛 个整数,分别表示密码中每个密室的启动情况。

输出格式

输出只有一行,即输出最少改动标记次数。

样例数据 样例输入 4 1 2 2 3 3 4 0 0 1 1 1 0 0 0 样例输出 1 子任务

对于 30 % 的数据, 𝑛 ≤ 10 。

对于 60 % 的数据, 𝑛 ≤ 100 。

对于 100 % 的数据, 1 ≤ 𝑛 ≤ 700 ,且每个密室至多与 11 个密室相通。