这个故事发生在一个名为BubbleLand的小镇。 BubbleLand中有n栋房子。这n栋房子里每栋都住着一个男孩或一个女孩。那里的人们真的很喜欢数字,每个人都有自己最喜欢的数字 f。这意味着住在第 i 栋房子里的男孩或女孩最喜欢的数字等于 fi。
房屋用数字 1 到 n 进行编号。
房屋之间有 n - 1 条双向道路相连,您可以从镇上的任何房屋前往任何其他房屋。每对房屋之间都有一条路径。
一家新的约会机构在这个神秘的小镇开设了办事处,市民们非常兴奋。他们立即向该机构发送了 q 个问题,每个问题的格式如下:
- a b — 询问有多少种方法可以选择一对具有相同最喜欢数字的情侣(男孩和女孩),并且住在从 a 房子到 b 房子的唯一路径上的其中一栋房子里。
帮助婚介所回答问题并发展业务。
输入
第一行包含一个整数n (1 ≤ n ≤ 105),即城镇中的房屋数量。
第二行包含n个整数,其中如果男孩住在第i个房子,则第i个数字为1;如果女孩住在第i个房子,则第i个数字为0。
第三行包含n个整数,其中第i个数字表示住在第i个房子里的女孩或男孩最喜欢的数字fi(1≤fi≤109)。
接下来的 n - 1 行包含有关道路的信息,第 i 行包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ n),这意味着这两栋房子之间存在道路。保证可以从任何其他房屋到达任何房屋。
下面一行包含一个整数 q (1 ≤ q ≤ 105),即查询次数。
以下 q 行代表一个问题,由两个整数 a 和 b (1 ≤ a, b ≤ n) 组成。
输出
对于每个 q 问题输出一个数字,即公民问题的答案。
示例
输入 #1
7 1 0 0 1 0 1 0 9 2 9 2 2 9 9 2 6 1 2 4 2 6 5 3 6 7 4 2 1 3 7 5
输出 #1
2 3
注意
在第一个问题中,从 1 号房子到 3 号房子,潜在的情侣是 (1, 3) 和 (6, 3)。
在第二个问题中,从 7 号房子到 5 号房子,潜在的情侣是 (7, 6)、(4, 2) 和 (4, 5)。