首页 > 试题广场 >

爱丽丝的人偶符法

[编程题]爱丽丝的人偶符法

热度指数：76 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

爱丽丝正在森林中布置她的人偶阵列。她将 $n$ 个人偶通过丝线连接成了一棵以人偶 $1$ 为根的树。每个人偶 $i$ 都有一个初始状态 $init_i \in \{0, 1\}$ ，而爱丽丝希望通过魔法将它们全部转变为目标状态 $goal_i \in \{0, 1\}$ 。

爱丽丝可以对任意一个人偶 $u$ 施加一次“波及魔法”。该魔法的效果如下：
翻转人偶 $u$ 及其子树中所有与 $u$ 距离为偶数（ $0, 2, 4, \dots$ ）的人偶的状态。所谓翻转，即 $0$ 变为 $1$ ， $1$ 变为 $0$ 。

请计算爱丽丝最少需要施加多少次魔法，才能使所有人偶都达到目标状态。

输入描述:


	第一行包含一个整数  ()，表示人偶的总数。  

	接下来的  行，每行包含两个整数  和  ()，表示人偶  与  之间有一条丝线连接。输入保证这些丝线构成一棵合法的树。  

	接下来的第  行包含  个整数，第  个整数表示人偶  的初始状态  ( 或 )。  

	接下来的第  行包含  个整数，第  个整数表示人偶  的目标状态  ( 或 )。

输出描述:


	输出一个整数，表示最少需要的操作次数。

示例1

输入

输出

说明


	在样例中，树的结构为一条路径 。

	1. 对人偶  进行操作：由于人偶  与  的距离分别为 （均为偶数），它们的状态从  变为 。此时状态序列为 `1 0 1 0 1`。

	2. 对人偶  进行操作：由于人偶  与  的距离分别为 （均为偶数），它们的状态从  变为 。此时状态序列为 `1 1 1 1 1`。

	总共进行了  次操作，满足所有目标状态。