{"raw_statement":[{"iden":"statement","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 favorite number _f_. That means that the boy or girl that lives in the _i_\\-th house has favorite number equal to _f__i_.\n\nThe houses are numerated with numbers 1 to _n_.\n\nThe 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.\n\nA 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:\n\n*   _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_.\n\nHelp the dating agency to answer the questions and grow their business."},{"iden":"input","content":"The first line contains an integer _n_ (1 ≤ _n_ ≤ 105), the number of houses in the town.\n\nThe 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.\n\nThe 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.\n\nThe 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.\n\nThe following line contains an integer _q_ (1 ≤ _q_ ≤ 105), the number of queries.\n\nEach of the following _q_ lines represents a question and consists of two integers _a_ and _b_ (1 ≤ _a_, _b_ ≤ _n_)."},{"iden":"output","content":"For each of the _q_ questions output a single number, the answer to the citizens question."},{"iden":"example","content":"Input\n\n7\n1 0 0 1 0 1 0\n9 2 9 2 2 9 9\n2 6\n1 2\n4 2\n6 5\n3 6\n7 4\n2\n1 3\n7 5\n\nOutput\n\n2\n3"},{"iden":"note","content":"In the first question from house 1 to house 3, the potential couples are (1, 3) and (6, 3).\n\nIn the second question from house 7 to house 5, the potential couples are (7, 6), (4, 2) and (4, 5)."}],"translated_statement":[{"iden":"statement","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 - 1] 条双向道路相连，你可以从任意一座房子到达其他任何一座房子。任意两座房子之间恰好存在一条路径。\n\n一家新的约会机构在这一神秘的小镇开设了办公室，居民们非常兴奋。他们立即向该机构提出了 #cf_span[q] 个问题，每个问题的格式如下：\n\n请帮助约会机构回答这些问题，以促进其业务发展。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105])，表示小镇中的房子数量。\n\n第二行包含 #cf_span[n] 个整数，其中第 #cf_span[i] 个数为 #cf_span[1] 表示第 #cf_span[i] 座房子里住着男孩，为 #cf_span[0] 表示住着女孩。\n\n第三行包含 #cf_span[n] 个整数，其中第 #cf_span[i] 个数表示住在第 #cf_span[i] 座房子里的男孩或女孩的最爱数字 #cf_span[fi] (#cf_span[1 ≤ fi ≤ 109])。\n\n接下来的 #cf_span[n - 1] 行描述了道路信息，第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai, bi ≤ n])，表示这两座房子之间有一条道路。保证任意两座房子之间均可相互到达。\n\n下一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 105])，表示查询的数量。\n\n接下来的 #cf_span[q] 行每行代表一个问题，包含两个整数 #cf_span[a] 和 #cf_span[b] (#cf_span[1 ≤ a, b ≤ n])。\n\n对于每个问题，请输出一个数字，作为对居民问题的答案。\n\n第一个问题中，从房子 #cf_span[1] 到房子 #cf_span[3]，潜在的伴侣组合为 #cf_span[(1, 3)] 和 #cf_span[(6, 3)]。\n\n第二个问题中，从房子 #cf_span[7] 到房子 #cf_span[5]，潜在的伴侣组合为 #cf_span[(7, 6)]、#cf_span[(4, 2)] 和 #cf_span[(4, 5)]。"},{"iden":"input","content":"第一行包含一个整数 #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])。"},{"iden":"output","content":"对于每个问题，请输出一个数字，作为对居民问题的答案。"},{"iden":"note","content":"第一个问题中，从房子 #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)]。"}],"sample_group":[],"show_order":[],"formal_statement":"**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\\} $ (0 = girl, 1 = boy),  \n- A favorite number $ f_i \\in \\mathbb{Z}^+ $, $ 1 \\leq f_i \\leq 10^9 $.  \n\nLet $ q \\in \\mathbb{Z}^+ $ be the number of queries.  \nEach query is a pair $ (a, b) \\in V \\times V $, representing two houses.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq q \\leq 10^5 $  \n3. $ 1 \\leq f_i \\leq 10^9 $  \n4. $ G $ is a tree (connected, undirected, $ n-1 $ edges)  \n\n**Objective**  \nFor each query $ (a, b) $, let $ P $ be the unique simple path from $ a $ to $ b $ in $ G $.  \nCount the number of unordered pairs $ \\{u, v\\} $ such that:  \n- $ u, v \\in P $,  \n- $ u \\neq v $,  \n- $ g_u \\neq g_v $,  \n- $ f_u = f_v $.  \n\nOutput the count for each query.","simple_statement":null,"has_page_source":false}