← 返回题目列表

Codeforces · 852/I

I. 约会

中文机器翻译题面 查看原题

这个故事发生在一个名为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)。