{"raw_statement":[{"iden":"statement","content":"给定一棵树，节点有颜色，在树上距离为 $2$ 的点连边（仍保留原来的边），求新图中颜色相同且连通的非空点集数量。由于答案可能非常大，您只需输出答案对 $10^9+7$ 取模的值。\n\n点集连通的定义：对于图 $G(V,E)$，$V$ 的一个子集 $V'$ 是连通点集，当且仅当 $G(V',E')$ 是一个连通图，其中边集 $E'=\\{(u,v)|(u,v)\\in E\\land u \\in V'\\land v\\in V'\\}$。"},{"iden":"input","content":"第一行一个正整数 $n$，表示节点个数。\n\n接下来一行 $n$ 个正整数，第 $i$ 个正整数 $c_i$ 表示第 $i$ 个节点的颜色。\n\n接下来 $n-1$ 行每行两个正整数 $u,v$ 表示原树有一条 $u$ 到 $v$ 的边。"},{"iden":"output","content":"一行一个整数，表示答案对 $10^9+7$ 取模的值。"},{"iden":"note","content":"样例 1 中，原树如下图所示：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/zmgrnwkh.png)\n\n树上距离为 $2$ 的点连边后，新图如下图所示：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/id3xc54a.png)\n\n则 $8$ 个颜色相同且连通的非空点集分别是：$\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{1,3\\},\\{1,4\\},\\{3,4\\},\\{1,3,4\\}$。\n\n**本题开启捆绑测试。**\n\n\n\n|$\\text{Subtask}$|分值|$n \\le$| 特殊性质 | 子任务依赖 |\n| :-----------: | :-------------:|:-----------: |:-----------: |:-----------: |\n|$0$|$5$|$10^5$| A | 无 |\n|$1$|$5$|$16$| 无 | 无 |\n|$2$|$5$|$10^5$| B | 无 |\n|$3$|$15$|$10^5$| C | 无 |\n|$4$|$20$|$10^5$| D | 无 |\n|$5$|$50$|$10^5$| 无 | $0\\sim4$ |\n\n- 特殊性质 A：所有节点的颜色不相同。\n- 特殊性质 B：给出的树是菊花，具体地，第 $i$ 条边连接节点 $1$ 和节点 $i+1$。\n- 特殊性质 C：给出的树是链，具体地，第 $i$ 条边连接节点 $i$ 和节点 $i+1$。\n- 特殊性质 D：所有节点的颜色相同。\n\n\n对于全部数据，满足 $2\\leq n\\leq 10^5$，$1\\leq c_i\\leq n$。"}],"translated_statement":null,"sample_group":[["4\n1 2 1 1\n1 2\n2 3\n2 4\n","8"],["6\n1 2 2 2 1 2\n5 3\n2 1\n4 5\n6 3\n3 1\n","14"],["16\n1 1 2 1 1 2 2 2 1 1 2 1 1 1 2 1\n12 8\n14 9\n10 8\n1 16\n7 12\n6 1\n14 8\n3 1\n12 5\n1 13\n12 2\n1 12\n15 8\n11 5\n4 12\n","442"],["16\n11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11\n4 14\n4 15\n12 13\n2 5\n7 15\n10 2\n15 8\n15 13\n9 11\n13 11\n3 15\n8 16\n6 13\n1 4\n10 4","27454"],["9\n3 3 2 3 2 4 2 3 3\n1 2\n2 3\n3 4\n4 5\n5 6\n6 7\n7 8\n8 9","16"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}