URI Online Judge | 3072

Dating

By RS Serbia

Timelimit: 3

This story is happening in a town named BubbleLand. There are n houses in BubbleLand. In each of these N(1 ≤ N ≤ 105) houses lives a boy or a girl. People there really love numbers, and everyone has a favorite number F. That means that the boy or the girl that lives in the i − th house has a favorite number equal to Fi(1 ≤ Fi ≤ 109).

The houses are numerated with numbers from 1 to N.

The houses are connected with N − 1 bi-directional roads and you can travel from any house to any other house in the town. There is exactly one path between every pair of houses.

A new dating agency had opened their offices in BubbleLand and the citizens were very excited. They immediately sent Q(1 ≤ Q ≤ 105) questions to the agency and each question was in the following format:
AB – asking how many ways there are to choose a couple (boy and girl) that have the same favorite number and live in one of the houses on a unique path from house A to house B.

Help the dating agency answer the questions and grow their business.

Input

The first line contains an integer n, the number of houses in the town.
The second line contains n integers, where the i-th number is 1 if a boy lives in the i-th house or 0 if a girl lives in the i-th house.
The third line contains N integers, where the i-th number represents the favorite number Fi of the girl or the boy that lives in the i-th house.
The next N − 1 lines contain information about the roads and the i-th line contains two integers Ai and Bi which means that there exists a road between these two houses.
The following line contains an integer Q, the number of questions.
Each of the following Q lines represents a question and consists of two integers A and B.

Output

For each of the Q questions output a single number, the answer to the citizens’ questions.

Input Sample Output Sample

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

2

3