English · Original
Chinese · Translation
Formal · Original
This story is happening in a town named BubbleLand. There are _n_ houses in BubbleLand. In each of these _n_ houses lives a boy or a girl. People there really love numbers and everyone has their favorite number _f_. That means that the boy or girl that lives in the _i_\-th house has favorite number equal to _f__i_.
The houses are numerated with numbers 1 to _n_.
The houses are connected with _n_ - 1 bidirectional 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 had agency opened their offices in this mysterious town and the citizens were very excited. They immediately sent _q_ questions to the agency and each question was of the following format:
* _a_ _b_ — asking how many ways are there to choose a couple (boy and girl) that have the same favorite number and live in one of the houses on the unique path from house _a_ to house _b_.
Help the dating agency to answer the questions and grow their business.
## Input
The first line contains an integer _n_ (1 ≤ _n_ ≤ 105), 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 _i_\-th house.
The third line contains _n_ integers, where the _i_\-th number represents the favorite number _f__i_ (1 ≤ _f__i_ ≤ 109) of the girl or 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 _a__i_ and _b__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_) which means that there exists road between those two houses. It is guaranteed that it's possible to reach any house from any other.
The following line contains an integer _q_ (1 ≤ _q_ ≤ 105), the number of queries.
Each of the following _q_ lines represents a question and consists of two integers _a_ and _b_ (1 ≤ _a_, _b_ ≤ _n_).
## Output
For each of the _q_ questions output a single number, the answer to the citizens question.
[samples]
## Note
In the first question from house 1 to house 3, the potential couples are (1, 3) and (6, 3).
In the second question from house 7 to house 5, the potential couples are (7, 6), (4, 2) and (4, 5).
这个故事发生在名为泡泡镇的地方。泡泡镇中有 #cf_span[n] 座房子，每座房子里住着一个男孩或一个女孩。镇上的人们非常热爱数字，每个人都有自己的最爱数字 #cf_span[f]。这意味着住在第 #cf_span[i] 座房子里的男孩或女孩，其最爱数字为 #cf_span[fi]。
房子的编号从 #cf_span[1] 到 #cf_span[n]。
这些房子通过 #cf_span[n - 1] 条双向道路相连，你可以从任意一座房子到达其他任何一座房子。任意两座房子之间恰好存在一条路径。
一家新的约会机构在这一神秘的小镇开设了办公室，居民们非常兴奋。他们立即向该机构提出了 #cf_span[q] 个问题，每个问题的格式如下：
请帮助约会机构回答这些问题，以促进其业务发展。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105])，表示小镇中的房子数量。
第二行包含 #cf_span[n] 个整数，其中第 #cf_span[i] 个数为 #cf_span[1] 表示第 #cf_span[i] 座房子里住着男孩，为 #cf_span[0] 表示住着女孩。
第三行包含 #cf_span[n] 个整数，其中第 #cf_span[i] 个数表示住在第 #cf_span[i] 座房子里的男孩或女孩的最爱数字 #cf_span[fi] (#cf_span[1 ≤ fi ≤ 109])。
接下来的 #cf_span[n - 1] 行描述了道路信息，第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai, bi ≤ n])，表示这两座房子之间有一条道路。保证任意两座房子之间均可相互到达。
下一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 105])，表示查询的数量。
接下来的 #cf_span[q] 行每行代表一个问题，包含两个整数 #cf_span[a] 和 #cf_span[b] (#cf_span[1 ≤ a, b ≤ n])。
对于每个问题，请输出一个数字，作为对居民问题的答案。
第一个问题中，从房子 #cf_span[1] 到房子 #cf_span[3]，潜在的伴侣组合为 #cf_span[(1, 3)] 和 #cf_span[(6, 3)]。
第二个问题中，从房子 #cf_span[7] 到房子 #cf_span[5]，潜在的伴侣组合为 #cf_span[(7, 6)]、#cf_span[(4, 2)] 和 #cf_span[(4, 5)]。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105])，表示小镇中的房子数量。第二行包含 #cf_span[n] 个整数，其中第 #cf_span[i] 个数为 #cf_span[1] 表示第 #cf_span[i] 座房子里住着男孩，为 #cf_span[0] 表示住着女孩。第三行包含 #cf_span[n] 个整数，其中第 #cf_span[i] 个数表示住在第 #cf_span[i] 座房子里的男孩或女孩的最爱数字 #cf_span[fi] (#cf_span[1 ≤ fi ≤ 109])。接下来的 #cf_span[n - 1] 行描述了道路信息，第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai, bi ≤ n])，表示这两座房子之间有一条道路。保证任意两座房子之间均可相互到达。下一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 105])，表示查询的数量。接下来的 #cf_span[q] 行每行代表一个问题，包含两个整数 #cf_span[a] 和 #cf_span[b] (#cf_span[1 ≤ a, b ≤ n])。
## Output
对于每个问题，请输出一个数字，作为对居民问题的答案。
[samples]
## Note
第一个问题中，从房子 #cf_span[1] 到房子 #cf_span[3]，潜在的伴侣组合为 #cf_span[(1, 3)] 和 #cf_span[(6, 3)]。第二个问题中，从房子 #cf_span[7] 到房子 #cf_span[5]，潜在的伴侣组合为 #cf_span[(7, 6)]、#cf_span[(4, 2)] 和 #cf_span[(4, 5)]。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of houses.
Let $ G = (V, E) $ be a tree with $ V = \{1, 2, \dots, n\} $, where each vertex $ i \in V $ has:
- A gender $ g_i \in \{0, 1\} $ (0 = girl, 1 = boy),
- A favorite number $ f_i \in \mathbb{Z}^+ $, $ 1 \leq f_i \leq 10^9 $.
Let $ q \in \mathbb{Z}^+ $ be the number of queries.
Each query is a pair $ (a, b) \in V \times V $, representing two houses.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 1 \leq q \leq 10^5 $
3. $ 1 \leq f_i \leq 10^9 $
4. $ G $ is a tree (connected, undirected, $ n-1 $ edges)
**Objective**
For each query $ (a, b) $, let $ P $ be the unique simple path from $ a $ to $ b $ in $ G $.
Count the number of unordered pairs $ \{u, v\} $ such that:
- $ u, v \in P $,
- $ u \neq v $,
- $ g_u \neq g_v $,
- $ f_u = f_v $.
Output the count for each query.
API Response (JSON)
{
"problem": {
"name": "I. Dating",
"description": {
"content": "This story is happening in a town named BubbleLand. There are _n_ houses in BubbleLand. In each of these _n_ houses lives a boy or a girl. People there really love numbers and everyone has their favor",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 65536
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF852I"
},
"statements": [
{
"statement_type": "Markdown",
"content": "This story is happening in a town named BubbleLand. There are _n_ houses in BubbleLand. In each of these _n_ houses lives a boy or a girl. People there really love numbers and everyone has their favor...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "这个故事发生在名为泡泡镇的地方。泡泡镇中有 #cf_span[n] 座房子，每座房子里住着一个男孩或一个女孩。镇上的人们非常热爱数字，每个人都有自己的最爱数字 #cf_span[f]。这意味着住在第 #cf_span[i] 座房子里的男孩或女孩，其最爱数字为 #cf_span[fi]。\n\n房子的编号从 #cf_span[1] 到 #cf_span[n]。\n\n这些房子通过 #cf_span[n - ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of houses. \nLet $ G = (V, E) $ be a tree with $ V = \\{1, 2, \\dots, n\\} $, where each vertex $ i \\in V $ has: \n- A gender $ g_i \\in \\{0, 1\\}...",
"is_translate": false,
"language": "Formal"
}
]
}