解题思路

题目中的一次操作是：选择节点 $x$，使得 $x$ 子树中与 $x$ 距离为偶数的节点翻转，与 $x$ 距离为奇数的节点不变。

设节点 $i$ 当前值与目标值是否不同为：

题目内容

老师为孩子们设计了一个使用异或树的游戏。游戏在一棵有 $n$ 个节点的树上进行，节点编号从 $1$ 到 $n$，树的根节点是节点 $1$，各节点之间的父子关系可从根节点 $1$ 开始基于连边关系进行推导。

每个节点 $i$ 有一个初始值 $init_i$，其值要么是 $0$，要么是 $1$。

在游戏过程中，可以对树执行若干次（可能为 $0$次）操作，具体操作就是选择某个节点$x$。

在选中节点 $x$之后：

• 节点 $x$的值会产生翻转（从$0$变成$1$或者从$1$ 变成$0$）
• $x$的子节点值则保持不变
• $x$的孙子节点的值也会翻转
• $x$ 的曾孙节点的值保持不变
• 依次逐代类推（即距离某节点为奇数的子节点保持不变，距离偶数的子节点会跟随翻转）

游戏的最终目标是使得每个节点 $i$的值都变为输入的目标值$goal_i，goal_i$也只能是 $0$ 或$1$。你需要使用最少的操作次数来达成游戏目标。

输入描述

第一行包含一个整数 $n (1 ≤ n ≤ 10^5)$，代表树存在$n$ 个节点。

接下来的 $n-1$行，每行包含两个整数 $u_i$ 和 $v_i (1 ≤ u_i, v_i ≤ n；u_i ≠ v_i)$，表示树节点 $u_i$和 $v_i$之间有树干连接。

下一行包含 $n$个整数，第 $i$ 个数字对应于树节点的$init_i$($init_i$ 只能是 0 或 1)。

接下来一行也包含 $n$ 个整数，第 $i$ 个数字对应于 树节点目标值$goal_i$ ($goal_i$ 只能是 0 或 1)。

特殊说明：所有节点之间的连接都是合法有效的，所有输入数据都能保证能构成一棵裸树。

输出描述

在第一行输出一个整数 $cnt$，代表你执行的最少操作次数。

样例1

输入

5
1 2
2 3
4 5
3 4
0 0 0 0 0
1 1 1 1 1

输出

2

说明

第一行输入表示共有 $5$个节点；接下来的$4$行，每两个数代表两个节点之间有边，比如节点$1$和节点$2$，节点$2$和节点 $3$，节点$4$ 和节点 5，节点 $3$和节点$4$；再接下来的一行中有 $5$ 个数，代表每个节点的初始状态值；再接下来的一行中有 $5$ 个数，代表每个节点的目标状态值。

观察可知，其中节点$1$ 的初始状态为$0$，目标为 $1$，需要执行一次操作，操作时影响到其孙子节点 $3$ 和曾曾孙节点 $5$，使其变为目标值 $1$；节点 $2$的初始状态为 $0$，目标为$1$，需要执行一次操作，会同时影响到其孙子节点$4$，使其变为目标值 $1$。经过两次操作后即可达成游戏目标，使得所有节点状态值达到目标。因此输出最少操作次数为$2$（操作节点为 $1$ 和$2$）。

样例2

输入

10
2 1
3 1
4 2
5 1
6 2
7 5
8 6
9 8
10 5
1 0 1 1 0 1 0 1 0 1
1 0 1 0 0 1 1 1 0 1

输出

2

说明

第一行输入共有$10$个节点；接下来的 $9$ 行，每两个数代表两个节点之间有边，比如节点 $2$ 和节点 $1$，节点 $3$和节点$1$，节点 $4$ 和节点 $2$，节点 $5$ 和节点 $1$，…，节点 $10$ 和节点$5$；再接下来的一行中有 $10$ 个数，代表每个节点的初始状态值；再接下来的一行中有 $10$ 个数，代表每个节点的目标状态值。

观察可知，其中节点 $4$ 的初始状态为 $1$，目标为 $0$，需要执行一次操作，无子节点对其他节点状态不会造成影响；节点 $7$ 的初始状态为 $0$，目标为 $1$，需要执行一次操作，无子节点对其他节点状态不会造成影响。经过两次操作后即可达成游戏目标，使得所有节点状态值达到目标。因此输出最少操作次数为$2$（操作节点为$4$ 和 $7$）。